有没有快速的方法来确定n ^ n上的前k个数字

Question

我正在编写一个程序,我只需知道第一个k(k可以是1-5之间的任何位置)的另一个大数字的数字,可以表示为n ^ n,其中n是一个非常大的数字.

目前我实际上正在计算n ^ n,然后将其解析为字符串.我想知道是否存在更快更好的方法.

Answer 1

有两种可能性.

如果你想要前k个前导数字(如:12345的前导数字是1),那么你可以使用这样的事实:

n^n = 10^(n*Log10(n))

所以你计算出小数部分f的n*Log10(n),然后的前k位10^f将是你的结果.如果使用双精度,则在舍入错误开始之前,这适用于最大约10 ^ 10的数字.例如,对于n = 2^20,f = 0.57466709...,10^f = 3.755494...所以你的前5位为37554.为n = 4,f = 0.4082...,10^f = 2.56那么你的第一个数字是2.

如果你想要前k个尾随数字(如:12345的尾随数字是5),那么你可以使用模运算.我会使用平方法:

factor = n mod 10^k
result = 1
while (n != 0) 
    if (n is odd) then result = (result * factor) mod 10^k
    factor = (factor * factor) mod 10^k
    n >>= 1

再以n = 2 ^ 20为例,我们发现了result = 88576.对于n = 4,我们有factor = 1, 4, 6,result = 1, 1, 6所以答案是6.