algorithm - 如何取两个非常大的数的模数？

Question

我需要一个 A mod B 的算法

1. A 是一个非常大的整数，它只包含数字 1(例如:1111、1111111111111111)
2. B 是一个非常大的整数(例如:1231、1231231823127312918923)

大，我的意思是 1000 位。

Answer 1

要计算一个模 n 的数，给定一个函数来计算除以 (n+1) 时的商和余数，首先要对该数加 1。然后，只要数字大于'n'，迭代:

number = (number div (n+1)) + (number mod (n+1))

最后在最后，减一。在开头加一并在结尾减一的替代方法是检查结果是否等于 n，如果是则返回零。

例如，给定一个除以 10 的函数，可以这样计算 12345678 mod 9:

12345679 -> 1234567 + 9 1234576 -> 123457 + 6  123463 -> 12346 + 3   12349 -> 1234 + 9    1243 -> 124 + 3     127 -> 12 + 7      19 -> 1 + 9      10 -> 1

减 1，结果为零。