基础算法一：大整数模积运算

一、要求

1. 只能有加减位运算
2. 支持大数(64位)模积运算(a * b mod m)
3. 处理模加中的溢出问题 （如果 a + b = c 溢出，则 a + b mod m = c mod m + 2^64 mod m)
4. 在模数和被模数相差十分大时，快速算出 a mod m

二、实现原理

首先对于mod运算，有以下推导：

模运算转位运算：

1. 当b为2的整数次幂（即b=1< 例如：num % x¹⁰ 等于 num & ( x¹⁰ - 1 )

加法运算转位运算：

1. 获取a+b结果中需要进位的位置 : a&b
2. 获取a+b结果中不进位部分相加的结果 : a^b
3. 例如：a=010010, b=100111，
   0、每轮首先判断b是否为0，为0则结束，把a的值作为结果返回
   1、(a&b)=000010 得出a+b中需要进位的位置，(a&b)<<1 将进位的值全体左移一位后，表示进位部分进位后的值，a ^ b=110101，表示a+b不进位部分相加的结果。由于(a&b)<<1大于0，把a ^ b的值赋给a，此时a=110101,(a&b)<<1的值赋给b，此时b=000100
   2、上一步获取的a和b继续运算，a ^ b =110001，(a & b)<<1=001000。进位(a & b)<<1大于0，进入下一步，此时，a = a ^ b = 110001，b = (a & b)<<1 = 001000
   3、a ^ b = 111001，(a & b)<<1 = 000000（进位）进位等于0，结束
   最后结果：a = a ^ b = 111001

减法运算转位运算：

1. a - b = a + (-b) = = a + ~(b - 1) = a + (~b+1)
2. 然后调用加法运算即可

三、示例代码

#include
 
//2^64-1
static unsigned long long maxNum = -1;
//2^63
static unsigned long long smaxNum = (unsigned long long) 1 << 63;
 
//得到二进制下数a的第i位的值
unsigned long long bitof(unsigned long long a, unsigned long long i)
{
    return (a >> i) & 1;
}
 
//模运算
//a和m相差很大时，仍能较快算出 a mod m
unsigned long long mod(unsigned long long a, unsigned long long m)
{
    unsigned long long m1 = m;
    while (a >= m)
    {
        //m1 >= smaxNum 左移后会溢出
        while (m1 < smaxNum && m1 < a)
        {
            m1 = m1 << 1;
        }
        while (m1 > a && m1 > m)
        {
            m1 = m1 >> 1;
        }
        a -= m1;
    }
    return a;
}
 
 
//模加运算
//( a + b ) mod m = ( a mod m + b mod m ) mod m
//注意 a + b 的溢出
unsigned long long plusmod(unsigned long long a, unsigned long long b, unsigned long long m)
{
    a = mod(a,m);
    b = mod(b,m);
 
    unsigned long long sum = a + b;
 
    //a + b 何时发生溢出，很容易错！！
    while (a != 0 && b != 0 && b - 1 >= maxNum - a)
    {
        a = mod(sum,m);
        b = mod(maxNum,m) + mod(1,m);
        sum = a + b;
    }
 
    return mod(sum,m);
    
}
 
//模乘运算
// a * b mod m = a * (bnbn-1...b1) mod m
// = ( ∑ a * bi * 2^(i-1) mod m ) mod m
unsigned long long multimod(unsigned long long a, unsigned long long b , unsigned long long m)
{
    unsigned long long res = 0;
    int i = 1;
    for(; i < 64; ++i)
    {
        if(bitof(a,i) == 0) continue;
 
        int j = 0;
        unsigned long long b1 = b;
        for (; j < i; ++j)
        {
            b1 = plusmod(b1,b1,m);
        }
 
        res = plusmod(res,b1,m);
    }
    if(bitof(a,0) == 1) res = plusmod(res,b,m);
 
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

四、测试用例

#include 
#include 
#include 

uint64_t multimod(uint64_t, uint64_t, uint64_t);

void test(uint64_t a, uint64_t b, uint64_t m) {
  #define U64 "%" PRIu64
  printf(U64 " * " U64 " mod " U64 " = " U64 "\n", a, b, m, multimod(a, b, m));
}

int main() {
  test(123, 456, 789);
  test(123, 456, -1ULL);
  test(-2ULL, -2ULL, -1ULL); // should be 1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16