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

问题描述

我在寻找一种算法，让我计算的 （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

这篇关于算法C / C ++：最快速的方法来计算（2 ^ n）的％D与和D 32位或64位整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！