我在寻找一种算法,让我计算的 (2 ^ n)的%D
是 n和第32天或64位整数
I am searching for an algorithm that allow me to compute (2^n)%d
with n and d 32 or 64 bits integers.
现在的问题是,这是不可能保存 2的n次方
,即使多precision库内存,但也许存在一个绝招来计算(2 ^ n)的%D
仅在使用32位或64位整数。
The problem is that it's impossible to store 2^n
in memory even with multiprecision libraries, but maybe there exist a trick to compute (2^n)%d
only using 32 or 64 bits integers.
非常感谢你。
看看的模幂算法。
我们的想法是不计算 2的n次方
。相反,可以减少模量 D
多次,而你开机。 这令小数目。
The idea is not to compute 2^n
. Instead, you reduce modulus d
multiple times while you are powering up. That keeps the number small.
通过平方相结合的方法,幂,你可以计算(2 ^ N) %D
仅 O(日志(N))
步骤。
下面是一个小例子: 2 ^ 130%123 = 40
2^1 % 123 = 2
2^2 % 123 = 2^2 % 123 = 4
2^4 % 123 = 4^2 % 123 = 16
2^8 % 123 = 16^2 % 123 = 10
2^16 % 123 = 10^2 % 123 = 100
2^32 % 123 = 100^2 % 123 = 37
2^65 % 123 = 37^2 * 2 % 123 = 32
2^130 % 123 = 32^2 % 123 = 40