大整数乘法

大整数乘法

大整数乘法采用分治法来解决这个问题：先把大整数分为两部分 A和B

例如123456789 = 12345 * 10410^4 + 6789;

image-20220429210627834

其中x和y不一定都是n为。这样X和Y的乘积：

XY = (A * 100.5n10^{0.5n} + B)(C * 100.5m10^{0.5m} + D) = A * C * 100.5n+0.5m10^{0.5n + 0.5m} + (AD * 100.5n10^{0.5n} + CB * 100.5m10^{0.5m} ) + BD

如果按照上面这个方式计算的话一共需要进行4次乘法最后的时间复杂度还是 2n2^n 因此我们还需要进行化简：

我们可以把(AD * 100.5n10^{0.5n} + CB * 100.5m10^{0.5m} ) 进行化简:

为了减少递归的次数我们可以将上面式子中的公共部分提取出来方便计算

步骤：

  1. 我们先判断一下0.5n 是否大于 0.5m
  2. 如果大于的话则提出0.5m
  3. 如果小于的话则提出0.5n

下面这种结果我们是用大于的哪一种情况

(AD * 100.5n10^{0.5n} + CB * 100.5m10^{0.5m} ) = （ (A * 100.5n−0.5m10^{0.5n-0.5m} - B)(D - C ) + A * C * 100.5n−0.5m10^{0.5n - 0.5m} + BD ）* 100.5m10 ^ {0.5m}

最后化简完之后的式子为：

XY = A * C * 100.5n+0.5m10^{0.5n + 0.5m} + （ (A * 100.5n−0.5m10^{0.5n-0.5m} - B)(D - C ) + A * C * 100.5n−0.5m10^{0.5n - 0.5m} + BD ）* 100.5m10 ^ {0.5m} + BD

这里面有三个乘法 最后的时间复杂度为O(n1.59n^{1.59})

代码为：

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
import time
import math
# 大整数相乘
def multi(x, y):
    # 判断一下x的长度
    len_x = getNumLen(x)
    # 判断一下y的长度
    len_y = getNumLen(y)

    # 如果他们之间有一个小于1的话那就直接返回这两个数据的乘法即可
    if len_x <= 1 or len_y <= 1:
        return x*y

    # 获取x的第一部分的长度
    branch_x1 = int(len_x/2)
    # 获取x的第二部分的长度 
    branch_x2 = len_x-branch_x1

    # 获取y的第一部分的长度
    branch_y1 = int(len_y/2)
    # 获取y的第二部分的长度
    branch_y2 = len_y-branch_y1
    

    # 获取x第一部分的数据
    x1 = int(x/pow(10,branch_x2))
    # 获取x第二部分的数据
    x2 = x%pow(10,branch_x2)
    
    # 获取y第一部分的数据
    y1 = int(y/pow(10,branch_y2))
    # 获取y第二部分的数据
    y2 = y%pow(10,branch_y2)
    
    
    # 获取第一部分的乘法的结果
    temp_x1_y1 = multi(x1, y1) 
    x1_y1 = temp_x1_y1 * math.pow(10, branch_x2 + branch_y2)
    # 获取第二部分乘法的结果
    x2_y2 = multi(x2, y2)

    # 下面就是对两个乘法化为一个乘法的过程
    # 先判断一下0.5n 是否大于0.5m
    # 如果大于的话
    if branch_x2 > branch_y2:
        # 获取两者之差
        pow_num = branch_x2-branch_y2
        # 依次获取公式中第 1 2 3 4部分
        A = x1*math.pow(10, pow_num)-x2
        B = y2 - y1
        C = temp_x1_y1*math.pow(10, pow_num)
        D = x2_y2

        # 排除乘法中的负数，如果有负数的话，在上面计算的时候会麻烦很多
        if A >= 0 and B >= 0:
            mid = (multi(A, B) + C + D)*math.pow(10, branch_y2)
        elif A >= 0 and B < 0:
            B = -B
            mid = (-multi(A, B) + C + D)*math.pow(10, branch_y2)
        elif A < 0 and B >= 0:
            A = -A
            mid = (-multi(A, B) + C + D)*math.pow(10, branch_y2)
        else:
            A = -A
            B = -B
            mid = (multi(A, B) + C + D)*math.pow(10, branch_y2)
    else:
        pow_num = branch_y2-branch_x2
        A = x1-x2
        B = y2 - y1*math.pow(10, pow_num)
        C = temp_x1_y1*math.pow(10, pow_num)
        D = x2_y2
        if A >= 0 and B >= 0:
            mid = (multi(A, B) + C + D)*math.pow(10, branch_x2)
        elif A >= 0 and B < 0:
            B = -B
            mid = (-multi(A, B) + C + D)*math.pow(10,branch_x2)
        elif A < 0 and B >= 0:
            A = -A
            mid = (-multi(A, B) + C + D)*math.pow(10, branch_x2)
        else:
            A = -A
            B = -B
            mid = (multi(A, B) + C + D)*math.pow(10, branch_x2)
    
    
    return x1_y1 + mid + x2_y2

def getNumLen(num):
    x = 0
    while(num/10 != 0):
        x += 1
        num = int(num/10)
    return x

endnum = str(multi(123456789987654321,987654321123456789))
print(endnum)
print(123456789987654321*987654321123456789)