计算机如何评估巨大的数字？

Question

如果我在Wolfram中输入一个值，例如1234567^98787878，它可以向我提供一些详细信息。这包括十进制近似，总长度，最后一位数等。你如何评价这么大的数字？据我所知，编程语言必须有一个特殊的数据类型才能存储数字，更不用说将它添加到其他东西中了。虽然我可以看到一个人如何接近两个非常大的数字的加法，但我看不出有多大的数字被计算出来。

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

Answer 1

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

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位数)

Answer 2

通常有库为任意大整数提供一个大型数据类型(例如。将数字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;

还有一些数论结果产生了特殊的算法来确定大数的性质，而不需要实际计算它们(准确地说，是它们的全十进制展开)。

Answer 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位数是通过模10^k进行幂运算来计算的，这样可以避免中间结果变得太大。

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