为什么这"to the power of" Javascript 算法会因大数字而失败？

Question

问题

找到数字 nn 的最后 k 位数字。保证数 nn 的长度不小于 k。

Example
For n = 5, k = 3, the result should be "125"
5^5 = 3125, last 3 digits is "125"
Input / Output
[input] integer n
1 ≤ N ≤ 10^9
[input] integer k
1 ≤ k ≤ 9
[output] a string
string of length k ---> last k digits of n^n

我的代码

function n2n(n, k) {

let a = Math.pow(n, n);
let b = Array.from(a.toString()).map(Number);
return b.slice((b.length-k),).join('');
}
console.log(n2n(5, 25));
console.log(n2n(5, 3));
console.log(n2n(1, 1));
console.log(n2n(5,4));
console.log(n2n(43, 7));
console.log(n2n(999, 9));

此代码似乎适用于较小的数字，但随后对大数字失败。

我的理论是，这是因为当数字变得非常大时，它不再是一个典型的数字，而是变成5345354 + e9325或类似的东西。

你同意我的代码有效吗？有没有办法防止某些数字的 bing 进程作为 NaN。

我的代码中的控制台日志提供：

3125
125
1
3125
268NaNNaN70
NaN

Answer 1

您应该将数字转换为BigInt以防止结果太大而导致精度损失：

function n2n(n, k) {
let a = BigInt(n) ** BigInt(n);
let b = Array.from(a.toString()).map(Number);
return b.slice((b.length-k),).join('');
}
console.log(n2n(5, 25));
console.log(n2n(5, 3));
console.log(n2n(1, 1));
console.log(n2n(5, 4));
console.log(n2n(43, 7));
console.log(n2n(999, 9));

Answer 2

其他人建议使用 BigInt 进行暴力破解解决方案，但它不适合这个问题，在最大n = 10^9上，n^n的数量太大而无法放入内存。

相反，这个问题可以用模算法来解决：

• 请注意，获取某个数字模10^k会给出该数字的最后k位数字

• 所以现在我们需要找到n^n mod 10^k这是一个众所周知的问题

• 我们可以不使用Math.pow()而是实现自己的使用模块化算术的pow

• 像这样的东西：(这个算法被称为二进制幂，如果不清楚发生了什么，你可以在网上查找(

function powMod(n, power, mod) {
if( power == 0) return 1 % mod;
if( power %2 == 1) return BigInt(n) * BigInt(powMod(n, power-1, mod)) % mod;
return powMod(BigInt(n)*BigInt(n) % mod, power/2, mod);
}

• 现在问题只需输出即可解决powMod(n, n, 10 ** k)

Answer 3

你需要使用BigInt，这可以通过调用BigInt(n)来完成。

此外，您可以使用.substr( <negative value X> )从字符串中获取最后X个字符。

方法如下：

function n2n(n, k) {  
let a = BigInt(n) ** BigInt(n);
return a.toString().substr(-k);
}
console.log(n2n(5, 25));
console.log(n2n(5, 3));
console.log(n2n(1, 1));
console.log(n2n(5, 4));
console.log(n2n(43, 7));
console.log(n2n(999, 9));
console.log(n2n(999, 19));
console.log(n2n(999, 29));
console.log(n2n(999, 39));
console.log(n2n(999, 99999999));

另外 ->我之前创建了一个与所有这些相关的答案，可以提供更多背景：https://stackoverflow.com/a/53518106/1220550

Answer 4

通过使用BigInt，你可以取一个数字子集来获得数字类型的通缉重用。

这种方法只为每次乘法取下一个乘法的最后(有效(数字。只要可以与所需值相乘，结果就有效。

function n2n(n, k) {
const bigN = BigInt(n);
let i = n,
p = '1';
while (i--) p = (BigInt(p) * bigN).toString().slice(-k);
return p;
}
console.log(n2n(5, 25));
console.log(n2n(5, 3));
console.log(n2n(1, 1));
console.log(n2n(5, 4));
console.log(n2n(43, 7));
console.log(n2n(999, 9));

Answer 5

在函数中，您键入了Math.pow(n, n)而不是Math.pow(n, k)。

这是旧代码：

function n2n(n, k) {

let a = Math.pow(n, n);
let b = Array.from(a.toString()).map(Number);
return b.slice((b.length-k),).join('');
}
console.log(n2n(5, 25));
console.log(n2n(5, 3));
console.log(n2n(1, 1));
console.log(n2n(5,4));
console.log(n2n(43, 7));
console.log(n2n(999, 9));

这是新代码：

function n2n(n, k) {

let a = Math.pow(n, k);
let b = Array.from(a.toString()).map(Number);
return b.slice((b.length-k),).join('');
}
console.log(n2n(5, 25));
console.log(n2n(5, 3));
console.log(n2n(1, 1));
console.log(n2n(5,4));
console.log(n2n(43, 7));
console.log(n2n(999, 9));

请确保运行代码以查看差异。