0

我正在编写一个应该执行权力的函数，但只显示指定的最后 n 位。它工作得很好……主要是。出于某种原因，当我指定我想要的最后几个数字时，它一直运行良好，一直到并包括数字 12。任何超过 12 的数字量似乎给了我一个非常奇怪的数字。我知道我一定遗漏了一些明显的东西，但我真的没有看到。

这是代码：

function power(base, exponent, digits) {
total = base;
for(i = 1; i < exponent; i++) {
    total =  total * base;

    if(total.toString().length > digits)  {
        total = total.toString().substr(total.toString().length - digits, digits);
        }
    }

return total;
}

因此，对于一些示例（显示 12 位及更低的数字可以正常工作）：

如果我做 power(999, 999, 1) 我最终得到 => 9

如果我做 power(999, 999, 5) 我最终得到 => 98999

如果我做 power(999, 999, 12) 我最终得到 => 000499998999

这是它开始搞砸的地方：

如果我做 power(999, 999, 13) 我最终得到 => 5710054009000

如果我做 power(999, 999, 14) 我最终得到 => '79077027006000'

起初我以为我达到了某种整数限制，而科学记数法把事情搞砸了，但我不认为是这种情况，因为它应该可以达到 20 位数字。

我怀疑我在 if 语句中减少字符串的方式有问题。但我不确定为什么它不会在 13 位以下的计算中搞砸。

谢谢！

4

1 回答 1

2

您需要一个函数来计算 b^e (mod m)。一个好的算法被称为平方和乘法：

Algorithm PowerMod: Compute b^e (mod m) with b, e and m all positive integers.
1. [Initialize] Set r := 1.
2. [Terminate when finished] If e == 0, return r and stop.
3. [Multiply if odd] If e is odd, set r := r * b (mod n).
4. [Square and iterate] Set e := floor(e / 2). Set b := b * b (mod n). Go to Step 2.

然后进行计算，例如 PowerMod(999, 999, 10^14); 你应该得到 17000499998999。

于 2012-07-16T12:59:46.860 回答