13

如果我在 Wolfram Alpha 中输入一个值，例如 1234567^98787878，它可以为我提供许多详细信息。这包括十进制近似值、总长度、最后一位数等。您如何评估如此大的数字？据我了解，编程语言必须具有特殊的数据类型才能存储数字，更不用说将其添加到其他内容中了。虽然我可以看到如何处理两个非常大的数字的相加，但我看不到评估的数字有多大。

10^2 可以通过重复相加计算得出。然而，像上面的例子这样的数字需要一个巨大的循环。有人可以解释如何评估如此大的数字吗？此外，例如，有人如何创建自定义大数据类型来支持 C# 中的大数字？

4

5 回答 5

13

嗯，这很容易，你可以自己做

  1. 位数可以通过对数获得：
since `A^B = 10 ^ (B * log(A, 10))`

(A = 1234567; B = 98787878)在我们的例子中，我们可以计算出

 `B * log(A, 10) = 98787878 * log(1234567, 10) = 601767807.4709646...`

integer part + 1( 601767807 + 1= 601767808 ) 是位数

  1. 首先，比如说，五位数字也可以通过对数得到；现在我们应该分析小数部分

    B * log(A, 10) = 98787878 * log(1234567, 10) = 601767807.4709646...

    f = 0.4709646...

    第一个数字是10^f（删除小数点）= 29577 ...

  2. 最后，比如说，五位数字可以作为相应的余数获得：

    最后五位数 =A^B rem 10^5

    A rem 10^5 = 1234567 rem 10^5 = 34567

    A^B rem 10^5 = ((A rem 10^5)^B) rem 10^5 = (34567^98787878) rem 10^5 = 45009

    后五位是45009

    您可能会发现BigInteger.ModPow(C#) 在这里非常有用

最后

1234567^98787878 = 29577...45009（601767808 位）

于 2013-08-20T12:27:18.487 回答
3

要计算有多少位，可以使用以下表达式：

decimal_digits(n) = 1 + floor(log_10(n))

这给出了：

decimal_digits(1234567^98787878) = 1 + floor(log_10(1234567^98787878))
                                 = 1 + floor(98787878 * log_10(1234567))
                                 = 1 + floor(98787878 * 6.0915146640862625)
                                 = 1 + floor(601767807.4709647)
                                 = 601767808

后面的 k 位是通过取幂 mod 10^k 计算的，这样可以防止中间结果变得太大。

近似值将使用（软件）浮点实现来计算，该实现有效地将 a^(98787878 log_a(1234567)) 评估为某个数字 a 的某个固定精度，这使得算术可以很好地工作（通常是 2 或 e 或 10）。这也避免了在任何时候实际处理数百万位数的需要。

于 2013-08-20T11:43:42.497 回答
3

通常有库为任意大的整数提供 bignum 数据类型（例如，将数字映射到重新定义算术运算k*n...(k+1)*n-1, k=0..<some m depending on n and number magnitude>大小的机器字）。n对于 c#，您可能对BigInteger感兴趣。

求幂可以递归分解：

pow(a,2*b)   = pow(a,b) * pow(a,b);
pow(a,2*b+1) = pow(a,b) * pow(a,b) * a;

还有一些数论结果产生了特殊的算法来确定大数的属性，而无需实际计算它们（准确地说：它们的完整十进制扩展）。

于 2013-08-20T11:40:39.127 回答
1

为此有很多库，并且在 python 的情况下，该功能是内置的。您似乎主要关心这些数字的大小以及进行诸如示例中的指数之类的计算可能需要的时间。所以我稍微解释一下。

表示 您可以使用数组来保存大数的所有数字。一种更有效的方法是使用 32 位无符号整数数组并存储大数的“32 位块”。您可以将这些块视为具有 2^32 个不同数字或字符的数字系统中的单个数字。那天我在 8 位 Atari800 上使用了一个字节数组来执行此操作。

做数学 您显然可以通过遍历所有数字并将一个数组的元素添加到另一个数组并跟踪进位来添加两个这样的数字。一旦你知道如何加法，你就可以编写代码来进行“手动”乘法，方法是将数字相乘并将结果放在正确的位置并进行大量加法 - 但软件会很快完成所有这些工作。还有比您在纸上手动使用的更快的乘法算法。纸乘法是 O(n^2)，而其他方法是 O(n*log(n))。至于指数，您当然可以乘以相同的数百万次，但每次乘法都将使用前面提到的函数进行乘法运算。有更快的求幂方法需要更少的乘法。

在实践 中尝试自己编写这些函数既有趣又具有教育意义，但在实践中，您将希望使用经过优化和验证的现有库。

于 2013-08-22T17:42:28.923 回答
-1

我认为部分答案在于问题本身:) 要存储这些表达式，您可以分别存储底数（或尾数）和指数，就像科学记数法一样。扩展到此，您不可能完全评估表达式并存储如此大的数字，尽管理论上您可以预测结果表达式的某些属性。我将带您了解您谈到的每个属性：

  1. 十进制近似值：可以通过评估简单的日志值来计算。
  2. 表达式 a^b 的总位数，可以通过公式 Digits = floor function (1 + Log10(a^b)) 计算，其中 floor function 是小于数字的最接近的整数。例如，10^5 中的位数是 6。
  3. 最后一位数字：这些可以通过线性递增指数的表达式形成算术级数这一事实来计算。例如在单位地点；7, 9, 3, 1 对 7^x 的指数重复。因此，您可以计算出如果 x%4 为 0，则最后一位为 1。有人可以为大数创建自定义数据类型，我不能说，但我敢肯定，不会评估和存储该数字。
于 2013-08-20T11:55:46.760 回答