大数相乘
编写两个任意位数得大数相乘的程序，给出计算结果。
题目描述： 输出两个不超过100位的大整数的乘积。
输入： 输入两个大整数，如1234567 和 123
输出： 输出乘积，如：151851741
分析
- 以上述为例，倘若手算的话，即把123的每一位都乘以1234567然后相加。下面我们来简单实现这种思路。
def test(x,y):
if x == 0 or y == 0:
return 0
import math
leny = int(math.log10(y))+1
res = 0
for i in range(leny-1,-1,-1):
res += int(str(y)[i])*x*10**(leny-1-i)
return res
x = 1234567
y = 123
print(test(x,y))
## 输出 151851741
- 改进上述方法
先不算任何的进位，也就是说，将每一位相乘，相加的结果保存到同一个位置，到最后才计算进位。
例如：计算98×21,步骤如下
9 8
× 2 1
-------------
(9)(8) <---- 第1趟: 98×1的每一位结果
(18)(16) <---- 第2趟: 98×2的每一位结果
-------------
(18)(25)(8) <---- 这里就是相对位的和，还没有累加进位
def test(x,y):
x = change(x,[])
y = change(y,[])
tmp = [0 for _ in range(len(x)+len(y))]
for i in range(len(x)):
for j in range(len(y)):
tmp[i+j] += x[i]*y[j]
carry = 0
for i in range(len(tmp)):
hh = (tmp[i]+carry)
tmp[i] = hh%10
carry = hh //10
res = 0
for i in range(len(tmp)):
res += tmp[i]*10**(i)
return res
def change(x,res):
# if x == 0:
# return
# res.append(x%10)
# change(x//10,res)
# return res
while x != 0:
res.append(x%10)
x = x//10
return res
x = 1234567
y = 123
print(test(x,y))
- Karatsuba算法
Karatsuba算法主要应用于两个大数的相乘，原理是将大数分成两段后变成较小的数位，然后做3次乘法，并附带少量的加法操作和移位操作。
现有两个大数，x，y。
首先将x，y分别拆开成为两部分，可得x1，x0，y1，y0。他们的关系如下：
x = x1 * 10^m + x0；
y = y1 * 10^m + y0。其中m为正整数，m < n，且x0，y0 小于 10^m。
那么 xy = (x1 * 10^m + x0)*(y1 * 10^m + y0) = z2 * 10^(2m) + z1 * 10^m + z0，其中：
z2 = x1 * y1；
z1 = x1 * y0 + x0 * y1；
z0 = x0 * y0。
此步骤共需4次乘法，但是由Karatsuba改进以后仅需要3次乘法。因为：
z1 = x1 * y0+ x0 * y1
z1 = (x1 + x0) * (y1 + y0) - x1 * y1 - x0 * y0，
故z1 便可以由一次乘法及加减法得到。
实例展示
设x = 12345，y=6789，令m=3。那么有：
12345 = 12 * 1000 + 345；
6789 = 6 * 1000 + 789。
下面计算：
z2 = 12 * 6 = 72；
z0 = 345 * 789 = 272205；
z1 = (12 + 345) * (6 + 789) - z2 - z0 = 11538。
然后我们按照移位公式（xy = z2 10^(2m) + z1 10^(m) + z0）可得：
xy = 72 * 10002 + 11538 * 1000 + 272205 = 83810205。
#### Python 递归有最大深度限制
def karatsuba(x,y):
import math
lenx = int(math.log10(x))
leny = int(math.log10(y))
m = min(lenx,leny)
if m==1:
return x*y
x1,x0 = x//(10**m),x%(10**m)
y1,y0 = y//(10**m),y%(10**m)
z2 = karatsuba(x1,y1)
z0 = karatsuba(x0,y0)
z1 = karatsuba((x1+x0),(y1+y0))-z2-z0
return z2*10**(2*m)+z1*10**m+z0
print(karatsuba(99,9999))