Thuật toán C/C++: Cách nhanh nhất để tính toán (2^n)% d với một và d 32 hoặc 64 bit số nguyên

Question

tôi đang tìm kiếm một thuật toán cho phép tôi để tính (2^n)%d với n và d 32 hoặc 64 bit số nguyên.

Vấn đề là không thể lưu trữ 2^n trong bộ nhớ ngay cả với thư viện đa năng, nhưng có thể tồn tại một mẹo để tính (2^n)%d chỉ sử dụng số nguyên 32 hoặc 64 bit.

Cảm ơn bạn rất nhiều.

Answer 1

Hãy xem Modular Exponentiation algorithm.

Ý tưởng không được tính 2^n. Thay vào đó, bạn giảm modulus d nhiều lần trong khi bạn đang bật nguồn. That keeps the number small.

Kết hợp phương thức với Exponentiation by Squaring và bạn có thể tính (2^n)%d chỉ trong O(log(n)) bước.

Dưới đây là một ví dụ nhỏ: 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