算法 C/C++:用 n 和 d 32 或 64 位整数计算 (2^n)%d 的最快方法 [英] Algorithm C/C++ : Fastest way to compute (2^n)%d with a n and d 32 or 64 bit integers

问题描述

我正在寻找一种算法，允许我使用 n 和 d 32 位或 64 位整数计算 (2^n)%d>.

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 存储在内存中，但也许存在计算 (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(log(n)) 步.

Combine the method with Exponentiation by Squaring, and you can compute (2^n)%d in only O(log(n)) steps.

这是一个小例子: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

这篇关于算法 C/C++:用 n 和 d 32 或 64 位整数计算 (2^n)%d 的最快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！