当前位置：文江博客话题详情

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

发布于 2024-12-28 03:43:56 字数 215 浏览 0 评论 0原文

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

问题在于，即使使用多精度库，也不可能将 2^n 存储在内存中，但也许存在仅使用 32 计算 (2^n)%d 的技巧或 64 位整数。

非常感谢。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

裸钻 2025-01-04 03:43:56

查看模幂算法。

这个想法不是计算2^n。相反，您可以在通电时多次减小模d。这可以使数字保持较小。

将该方法与平方求幂，您可以计算(2^n)%d 只需 O(log(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

Take a look at the Modular Exponentiation algorithm.

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.

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

Here's a small example: 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

回复收藏 0 原文

~没有更多了~