这么大的数字如何计算？

Question

我现在自学 Pascal 一个月了，我遇到了一个我似乎无法解决的问题。基本上我有2个数字，N和M，其中N小于10^{100 000}，M小于10⁸，并且都大于0。我需要计算N mod M。

我不知道该怎么做，即使有

QWord

也不知道。我用

string

尝试过，但我不知道有什么好方法。它对我来说总是太复杂，因为我使用

for

函数，从字符串 N 和字符串 M 中获取最后一个数字，然后用两个

if

函数减去它们（其中 N 的最后一位数字 高于或等于 M

的最后一位数字，如果更低）。基本上我认为对于这个简单的问题来说它变得太复杂了。

Answer 1

有一些大数量的包裹漂浮在周围，例如。 g。 Wolfgang Erhardt 的开源包

MPArith。使用随附的演示计算器，您可以轻松超越时间限制：

D:\Xtools\MPArith>t_calc.exe
T_CALC using MPArith V1.26.05 (31/32 bit) [mp_calc]  (c) W.Ehrhardt 2006-2013
Karatsuba cutoffs:  mul/sqr = 16/32,   Toom-3 cutoffs: mul/sqr = 32/64
Burnikel/Ziegler div cutoff = 32,   MaxBit = 520093696,   MaxFact = 22623931
Type "?<enter>" to get some info about commands, "\q" or "quit" to end.

[D]:=> 10^100000 mod (10^8-1)
Result = 1
[D]:=> .
Time = 20.128 ms
[D]:=> 10^100000;
Result =  [>0, 332193 bits,  chksum=$CE01C341,  time=46.994 ms]

但是根据您的要求和示例，您甚至可以在没有大量软件包的情况下获得结果。 如果你想计算 ab mod n，你不计算 ab，然后在第二步中以 n 为模来减少它，但是你会减少循环中的每个乘积。 并且您应该使用快速二进制求幂，请参阅 e。 g。 维基百科关于模幂的文章中的描述和伪代码。

对于 10

8 阶的模块 n^{，您需要减少两个 31、32 位整数的乘积，因此您需要} int64

 左右来累积乘积（这对于您的 Pascal 版本来说应该不是问题有

QWord

）。
我想这样的程序会比 20 毫秒的 

MPArith

 大数字代码快得多。