C ++中大数的模乘 [英] modular multiplication of large numbers in c++

问题描述

我有三个整数 A，B (小于10 ^ 12)和 C (小于10 ^ 15).我想计算(A * B)％C .我知道

I have three integers A, B (less than 10^12) and C (less than 10^15). I want to calculate (A * B) % C. I know that

(A * B) % C = ((A % C) * (B % C)) % C

但是说，如果 A = B = 10 ^ 11 ，那么上面的表达式将导致整数溢出.对于上述情况，是否有任何简单的解决方案，或者我必须使用快速乘法算法.

but say if A = B = 10^11 then above expression will cause an integer overflow. Is there any simple solution for above case or I have to use fast multiplication algorithms.

如果我必须使用快速乘法算法，那我应该使用哪种算法.

If I have to use fast multiplication algorithm then which algorithm I should use.

编辑:我已经在 C ++ 中尝试了上述问题(不会引起溢出，不确定原因) ，但答案不应该是零吗?

I have tried above problem in C++ (which does not cause overflow, not sure why), but isn't the answer should be zero?

提前谢谢.

推荐答案

给出您的公式和以下变体:

Given your formula and a the following variation:

(A + B) mod C = ((A mod C) + (B mod C)) mod C 

您可以使用分而治之的方法来开发既简单又快速的算法:

You can use the divide and conquer approach to develope an algorithm that is both easy and fast:

#include <iostream>

long bigMod(long  a, long  b, long c) {
    if (a == 0 || b == 0) {
        return 0;
    }
    if (a == 1) {
        return b;
    }
    if (b == 1) {
        return a;
    } 

    // Returns: (a * b/2) mod c
    long a2 = bigMod(a, b / 2, c);

    // Even factor
    if ((b & 1) == 0) {
        // [((a * b/2) mod c) + ((a * b/2) mod c)] mod c
        return (a2 + a2) % c;
    } else {
        // Odd exponent
        // [(a mod c) + ((a * b/2) mod c) + ((a * b/2) mod c)] mod c
        return ((a % c) + (a2 + a2)) % c;
    }
}

int main() { 
    // Use the min(a, b) as the second parameter
    // This prints: 27
    std::cout << bigMod(64545, 58971, 144) << std::endl;
    return 0;
}

哪个是O(log N)

这篇关于C ++中大数的模乘的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！