如何计算一个这么大的数字？

Question

我现在正在学习Pascal一个月了,我遇到了一个似乎无法解决的问题.基本上我有2号,Ñ和中号,其中Ñ小于10 ^{100 000}和中号小于10 ⁸两者都是大于0我需要计算Ñ模中号.

我无法弄清楚如何做到这一点,甚至没有QWord.我尝试过,string但我不知道一个好方法.它总是对我来说太复杂了,因为我使用了一个for函数,我从字符串N和字符串M中得到最后一个数字然后我用两个if函数减去它们(其中N的最后一个数字高于或等于M的最后一个数字,如果它更低).基本上,我觉得这个简单的问题太复杂了.

Answer 1

有一些 bignum 包，例如来自http://www.wolfgang-ehrhardt.de/mp_intro.html的开源 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]

但根据您的要求和示例，您甚至可以在 没有bignum 包的情况下获得结果。如果你想计算，a ^ b mod n你不会计算 a ^ b然后mod n在第二步中减少，而是减少循环中的每个乘积。您应该使用快速二进制求幂，请参阅http://en.wikipedia.org/wiki/Modular_exponentiation中的描述和伪代码。对于 10^8 阶的模块 n，您需要减少两个 31/32 位整数的乘积，因此您需要int64大约累加乘积（对于具有 的 Pascal 版本来说，这不应该是问题QWord）。我想这样的程序会比 MPArith bignum 代码快得多，它需要 20 毫秒。