4

最常见的方法是对二进制数的每个非零位置求 2 的幂，然后将它们相加。当二进制数很大时，这不可行，例如，

10000...0001 //1000000 个位置

不可能让计算机计算 pow(2,1000000)。所以传统的方式是行不通的。

其他方式来做到这一点？

有人可以给出一个关于如何计算的算术方法，而不是库吗？

4

6 回答 6

3

正如happydave 所说，这种类型的东西有现有的库（例如GMP）。如果您出于某种原因需要自己动手，这里有一个相当有效的方法的大纲。您将需要 bigint 减法、比较和乘法。

以二进制格式缓存 10^(2^n) 的值，直到下一个值大于二进制数。这将允许您通过执行以下操作快速生成 10 的幂：

Select the largest value in your cache smaller than your remaining number, store this
in a working variable.
do{
  Multiply it by the next largest value in your cache and store the result in a
  temporary value.
  If the new value is still smaller, set your working value to this number (swapping 
  references here rather than allocating new memory is a good idea),
  Keep a counter to see which digit you're at. If this changes by more than one
  between instances of the outer loop, you need to pad with zeros
} Until you run out of cache
This is your next base ten value in binary, subtract it from your binary number while
the binary number is larger than your digit, the number of times you do this is the 
decimal digit -- you can cheat a little here by comparing the most significant bits
and finding a lower bound before trying subtraction.
Repeat until your binary number is 0

就二进制位数而言，这大约是 O(n^4)，就内存而言，这大约是 O(nlog(n))。通过使用更复杂的乘法算法，您可以使 n^4 更接近 n^3。

于 2012-05-11T03:31:34.033 回答
1

您可以编写自己的类来处理任意大的整数（您可以将其表示为整数数组，或者任何最有意义的东西），并自己实现操作（*、pow 等）。或者你可以谷歌“C++ 大整数库”，找到其他已经实现它的人。

于 2012-05-11T02:06:10.640 回答
1

不可能让计算机计算 pow(2,1000000)。所以传统的方式是行不通的。

这并非不可能。例如，Python 可以立即进行算术计算，并在大约两秒内转换为十进制数（在我的机器上）。Python 内置了处理超过机器字大小的大整数的功能。

在 C++（和 C）中，大整数库的一个不错的选择是GMP。它是健壮的、经过良好测试的和积极维护的。它包括一个C++ 包装器，它使用运算符重载来提供一个很好的接口（除了该操作没有 C++ 运算符pow()）。

这是一个使用 GMP 的 C++ 示例：

#include <iostream>
#include <gmpxx.h>

int main(int, char *[])
{
    mpz_class a, b;
    a = 2;
    mpz_pow_ui(b.get_mpz_t(), a.get_mpz_t(), 1000000);
    std::string s = b.get_str();
    std::cout << "length is " << s.length() << std::endl;
    return 0;
}

上面的输出是

长度为 301030

在我的机器上执行 0.18 秒。

于 2012-05-11T03:12:13.803 回答
1

“就二进制位数而言，这大约是 O(n^4)，而就内存而言，这大约是 O(nlog(n))”。您可以执行 O(n^(2 + epsilon)) 操作（其中 n 是二进制位数）和 O(n) 内存，如下所示：设 N 是二进制长度为 n 的巨大数。计算余数 mod 2（容易；抓住低位）和 mod 5（不容易但不可怕；将二进制字符串分成连续的四位字符串；计算每个这样的 4 元组的余数 mod 5，并将它们相加就像将 9 用于十进制数一样。）。通过计算余数 mod 2 和 5，您可以读出低位十进制数字。减去这个；除以 10（互联网记录了这样做的方法），然后重复以获得下一个最小的数字。

于 2017-05-30T19:06:34.153 回答
0

我在 Smalltalk 中计算了 2 ** 1000000 并在 9.3 秒内将其转换为十进制，所以这并非不可能。Smalltalk 内置了大型整数库。

2 raisedToInteger: 1000000

正如另一个答案中提到的，您需要一个处理任意精度整数的库。一旦你有了它，你就可以对其进行 MOD 10 和 DIV 10 操作，以相反的顺序计算十进制数字（从最低有效到最高有效）。

粗略的想法是这样的：

LargeInteger *a;
char *string;


while (a != 0) {
    int remainder;
    LargeInteger *quotient;

    remainder = a % 10.
    *string++ = remainder + 48.
    quotient = a / 10.
    }

这里有很多关于类型转换、内存管理和对象分配的细节缺失（或错误），但它旨在展示一般技术。

于 2012-05-11T03:06:40.180 回答
0

使用Gnu Multiprecision Library非常简单。不幸的是，我无法测试这个程序，因为似乎我需要在编译器升级后重建我的库。但是没有太大的错误空间！

#include "gmpxx.h"
#include <iostream>

int main() {
    mpz_class megabit( "1", 10 );
    megabit <<= 1000000;
    megabit += 1;
    std::cout << megabit << '\n';
}
于 2012-05-11T03:25:47.010 回答