如何在 Swift 中对大数进行模块化算术?

How to do modular arithmetics on big numbers in Swift?

提问人:Parth 提问时间:11/14/2023 最后编辑:relent95Parth 更新时间:11/14/2023 访问量:106

问:

当通过减去字符的旧权重并为新字符添加新权重来评估字符串的滚动哈希时,会出现这种情况。

Python 有无限长的数字,能够存储如此大的数字:

num = -56061846576641933068511861128435847024473459936647893758520084401988341
div = 10**9 + 7
mod = num % div #504892002

但是在 Swift 中,当我不断进行计算时,我失去了精度,误差越来越大。例如,在我的计算中的某个时刻,上面的数字具有以下值:

var num = Double("-5.606184657664193e+70")
var div = pow(Double(10), 9) + 7
var mod = num!.truncatingRemainder(dividingBy: div)
mod = mod < 0 ? mod + div : mod //215272131.0

我研究了 Decimal,但它不支持 mod 操作。而 Int64 对于这样的数字来说也太小了。在不添加便利扩展的情况下,是否有其他本机选项?

另外,如何使用 NSDecimalNumber 获得除法的整数和模数 (mod) 也无济于事。它建议扩展或具有不处理大数字的示例。

Swift Biginteger 模块化算术

评论

2赞 President James K. Polk 11/14/2023
-5.606184657664193e+70怎么可能正好等于-56061846576641933068511861128435847024473459936647893758520084401988341?
1赞 Mad Physicist 11/14/2023
我同意你的问题现在好多了。你能举个例子来说明你是如何得到你所拥有的号码的吗?我怀疑你可以边走边做模运算,永远不会超过 1e9+7
1赞 Mad Physicist 11/14/2023
看看这个: en.wikipedia.org/wiki/Modular_exponentiation.这个想法是以一种不会溢出的方式实现。当您可以使用整数数学时,它比浮点数更好。pow(base, len - 1) mod div
1赞 relent95 11/15/2023
詹姆士会长,我错过了。谢谢。OP 需要编辑问题。这是一个XY问题。他不需要一个大的整数 API 来达到这个目的。
1赞 relent95 11/16/2023
请参阅节省内存的方法。设 m = 10000000007。想想这些:r_1 = (m-26) % m,r_2 = (r_1 * 26) % m,r_3 = (r_2 * 26) % m,...r_49 = (r_48 * 26) % 米。r_i *26 不会溢出,因为 r_i < m,r_i * 26 < m * 26 < 2^63-1。

答: 暂无答案