JavaScript中大数的除法和余数

Question

我正在尝试获取一个大数的余数，例如：

1551690021432628813 % 64

但是我发现这个数字对于JavaScript来说太长了，即会被四舍五入为零。

除了使用一个26kb的库，例如BigInteger.js，是否有其他解决方法？

- Sean H

---

你是如何表示1551690021432628813的？作为字符串吗？ - John Coleman

@JohnColeman 是的 - Sean H

Answer 1

谢谢John Coleman

Javascript 版本:

    function calculateMod(str, mod) {
        var n = str.length;
        if (n <= 10) {
            return parseInt(str) % mod;
        }
        else {
            var first = str.substring(0, n - 10)
            var second = str.substring(n - 10)
            return (calculateMod(first, mod) * (Math.pow(10, 10) % mod) + parseInt(second) % mod) % mod;
        }
    }

- Fariborz Korevli

Answer 2

您可以将数字从右侧开始分成10位一组，并对这些组进行模算术运算，最后将结果合并：

1551690021432628813 = 155169002 * 10**10 + 1432628813

因此

1551690021432628813 % 64 = (155169002 % 64 * (10**10) % 64  + 1432628813 % 64) % 64

（等于 13 ）。

您可以编写一个实现这个思想的递归函数。以下是在Python中（我更加流利）编写的内容，但应该很容易翻译成JavaScript：

def remainder(s,m):
    #computes int(s) % m, while just using small numbers
    #s is a string and m is an integer

    n = len(s)
    if n <= 10:
        return int(s) % m
    else:
        first = s[:n-10] #first n-10 digits in s
        second = s[-10:] #last 10 digits
        return (remainder(first,m) * ((10**10) % m) + int(second) % m) % m

如果模数为64，那么有一种特别简单的方法：64可以整除10**6，所以绝对总是成立。

n % 64 == (last 6 digits of n) % 64

例如，

1551690021432628813 % 64 = 628813 % 64 = 13

当模数是2的幂时，类似的评论同样适用。

- John Coleman

Answer 3

您需要使用一个库（比如您找到的那个）。JavaScript 的数字（IEEE-754 双精度二进制浮点数）在该规模下不够准确，而这是 JavaScript 所有数字类型中唯一的一种。一旦超过 Number.MAX_SAFE_INTEGER + 1（9,007,199,254,740,992），JavaScript 的数字就无法再表示每一个整数（例如，无法表示 9,007,199,254,740,993）。

---

除了类型化数组的元素类型外，它们对您没有帮助，原因有两个：1. 没有Uint64类型化数组，最大整数是Uint32，2. 一旦您对条目执行数学运算，就会将其转换为标准数字。

- T.J. Crowder

---

谢谢您的解释。我不能使用那些我找到的如此庞大的库。我想一个好的解决方法是使用仅提供我需要操作的库，即余数。 - Sean H

@Seano：FWIW，bignumber.js "压缩后仅有8K"。在当今的大多数情况下，这并不算什么。（我从未使用过它，只是我知道的其中一个。） - T.J. Crowder

我很感激，但我不能使用gzip。即使是压缩后的文件大小仍然为26kb。 - Sean H

@Seano：你必须使用非常过时的技术才无法使用gzip；即时gzip是任何半好的Web服务器都具备的功能。但他们的网站已经过时了，或者这是一个打字错误；在我看来，缩小版本的大小为85k，压缩后在传输中为19k。在现代世界中，这仍然不算大——但也不是8k！ :-) - T.J. Crowder

Answer 4

// you can use the built-in BigInt object
console.log(Number(1551690021432628813n % 64n));

- pank

Answer 5

虽然有一些变通方法，但通常最简单的方法是使用一个库阅读更多

- K. Kirsz

---

上面的链接解释了如何手动实现“基于字符串的除法”。你考虑过这种方法吗？ - K. Kirsz

Answer 6

BigInt(1551690021432628813) % 64

大整数（1551690021432628813）% 64

- Nazeer Haidari

---

你的回答可以通过添加额外的支持信息得到改进。请[编辑]以添加更多细节，例如引文或文献，以便他人可以确认你的回答是否正确。你可以在 帮助中心 中找到更多有关如何编写良好答案的信息。 - Community