3

我需要一些帮助来决定什么是更好的性能。我正在使用bigints （超过 500 万位），并且大部分计算（如果不是全部）都在将当前 bigint 加倍。所以我想知道是否最好将每个单元格（bigint 的一部分）乘以 2，然后对其进行修改，其余的你就知道了。或者将 bigint添加到自身是否更好。

我也在考虑实现的难易程度（添加 2 个 bigint 比乘以 2 更复杂），但我更关心性能，而不是代码的大小或实现的难易程度。

其他信息：我将用C++对其进行编码，我对 bigints 相当熟悉（只是从未遇到过这个问题）。我不需要任何源代码或类似的东西我只需要一个好的意见和解释/证明，因为我需要从一开始就做出一个好的决定，因为项目将相当大并且主要围绕这部分构建这在很大程度上取决于我现在选择的内容。

谢谢。

4

7 回答 7

9

尝试对每一位进行位移。这可能是最快的方法。当你将一个整数向左位移时，你将它加倍（乘以 2）。如果你有几个长整数在一个链中，那么你需要存储最高有效位，因为移动它之后它会消失，你需要将它用作下一个长整数的最低有效位。

这实际上并不重要。现代 64 位计算机可以在对它们进行位移的同时（1 个时钟周期）将两个整数相加，因此所需的时间也一样长。我建议你尝试不同的方法，如果有任何重大的时间差异，然后报告。这三种方法都应该很容易实现，生成一个 5mb 的数字也应该很容易，使用随机数生成器。

于 2009-08-11T15:18:20.033 回答
5

要存储一个 500 万位的整数，您需要相当多的位——如果您指的是二进制数字，则需要 500 万位，如果是十进制数字，则需要大约 1700 万位。假设这些数字以二进制表示形式存储，并且您的算术以某种大小的块进行，例如 32 位或 64 位。

  • 如果将数字添加到自身，则将每个块添加到自身以及添加前一个块的进位。为下一个块保留任何结转。这是一些附加操作，以及一些用于跟踪进位的簿记。

  • 如果通过左移乘以 2，则乘法为一次左移操作，一次右移操作 + 和 1 以获得进位。随身记账要简单一些。

从表面上看，shift 版本似乎稍微快一些。然而，将数量翻倍的总成本很大程度上受数量大小的影响。1700 万位数超过了 cpu 的 L1 缓存，处理时间可能会被内存提取操作所淹没。在现代 PC 硬件上，内存获取比加法和移位慢几个数量级。

有了这个，您可能想要选择一个更容易实现的。我倾向于左移版本。

于 2009-08-11T15:28:09.717 回答
1

左移一位与乘以二相同！
这个链接解释了机制并给出了例子。

int A = 10; //...01010 = 10
int B = A<<1; //..010100 = 20
于 2009-08-11T15:24:09.960 回答
1

你试过移位吗？
<< 乘以 2
>> 除以 2

于 2009-08-11T15:18:30.203 回答
0

大部分计算（如果不是全部）都是将当前 bigint 加倍的部分

如果您所有的计算都在将数字加倍，那么您为什么不保留一个不同的（以 2 为底）比例字段？然后只需添加一个比例，它可以只是一个普通的旧 int。这肯定会比任何几百万位的操作都要快。

IOW，使用大浮点数。

随机基准

use Math::GMP;
use Time::HiRes qw(clock_gettime CLOCK_REALTIME CLOCK_PROCESS_CPUTIME_ID);

my $n = Math::GMP->new(2);
$n = $n ** 1_000_000;

my $m = Math::GMP->new(2);
$m = $m ** 10_000;

my $str;
for ($bits = 1_000_000; $bits <= 2_000_000; $bits += 10_000) {
    my $start = clock_gettime(CLOCK_PROCESS_CPUTIME_ID);
    $str = "$n" for (1..3);
    my $stop = clock_gettime(CLOCK_PROCESS_CPUTIME_ID);
    print "$bits,@{[($stop-$start)/3]}\n";
    $n = $n * $m;
}

似乎表明 GMP 以某种方式在 O(n) 时间内进行转换（其中 n 是二进制数中的位数）。这可能是由于 1 后面跟着一百万（或两个）零的特殊情况；GNU MP 文档说它应该更慢（但仍然比 O(N^2) 好。

http://img197.imageshack.us/img197/6527/chartp.png

于 2009-08-11T15:50:33.667 回答
0

BigNums的良好实现乘法是 O(N log(N) log(log(N))。加法是 O(n)。因此，添加到自身应该比乘以 2 更快。但是，只有当你相乘时，这才是正确的两个任意大数；如果您的库知道您将大数乘以一个小整数，它可能能够优化到 O(n)。

正如其他人所指出的，位移也是一种选择。它也应该是 O(n) 但更快的恒定时间。但这只有在您的 bignum 库支持位移时才有效。

于 2009-08-11T16:01:09.493 回答
0

如果它真的很重要，您需要编写所有三种方法（包括位移！），并在各种输入上分析它们。（使用小数、大数和随机数，以避免结果出现偏差。）

对不起“自己动手”的答案，但这确实是最好的方法。没有人比你更关心这个结果，这只会让你成为解决这个问题的最佳人选。

于 2009-08-11T15:42:03.463 回答