算法C/C++：用n和d 32或64位整数计算(2 ^ n)％d的最快方法

发布时间：2020-12-16 03:20:24 所属栏目：百科来源：网络整理

导读：我正在寻找允许我用n和d 32或64位整数计算(2 ^ n)％d的算法. 问题是即使使用多精度库也不可能将2 ^ n存储在内存中,但也可能存在使用32或64位整数来计算(2 ^ n)％d的技巧. 非常感谢你. 解决方法看看 Modular Exponentiation algorithm. 这个想法不是计算2 ^

我正在寻找允许我用n和d 32或64位整数计算(2 ^ n)％d的算法.

问题是即使使用多精度库也不可能将2 ^ n存储在内存中,但也可能存在使用32或64位整数来计算(2 ^ n)％d的技巧.

非常感谢你.

解决方法

看看 Modular Exponentiation algorithm.

这个想法不是计算2 ^ n.而是在上电时减少模数d. That keeps the number small.

将方法与Exponentiation by Squaring组合,您只能在O(log(n))步骤中计算(2 ^ n)％d.

这里有一个小例子：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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!