这是karatsuba算法的伪代码:
procedure karatsuba(num1, num2)
if (num1 < 10) or (num2 < 10)
return num1*num2
/* calculates the size of the numbers */
m = max(size_base10(num1), size_base10(num2))
m2 = m/2
/* split the digit sequences about the middle */
high1, low1 = split_at(num1, m2)
high2, low2 = split_at(num2, m2)
/* 3 calls made to numbers approximately half the size */
z0 = karatsuba(low1, low2)
z1 = karatsuba((low1+high1), (low2+high2))
z2 = karatsuba(high1, high2)
return (z2*10^(2*m2)) + ((z1-z2-z0)*10^(m2)) + (z0)
我不明白"在中间拆分数字序列"的步骤,尤其是在查看了 python 实现之后 卡拉苏巴的算法
你能解释一下,我们到底应该如何拆分数字序列吗?
在每次迭代中,您按文本长度(以 10 为基数(将中间的数字分解。例如,六位数字123456
变为123
和456
.
对于不同长度的数量的情况,请注意,实现适用于两者的最大值。 给定12345678
和100
,这有效地用零填充较短的数字,以00000100
。 分成两个 4 位数字,然后继续。
请注意,作为一种算法,这表示简单的二项式展开:
(a + b) * (c + d) = ac + ad + bc + bd
在 8 位数字的情况下,我们的数字是
(1234*10^4 + 5678) * (0000*10^4 + 0100)
这有助于您的理解吗?
我已经为卡拉苏巴算法编写了一个非常简单的代码,你也可以试试这个......
import timeit
import math
#loading math and time module
start_time = timeit.default_timer()
# creating a start time count down initilise to 0
def karatsuba_multiplication(nu1,nu2): #defining a function
num1 = str(nu1) #converting inteager into string because object of type inteager has no lenght
num2 = str(nu2)
x = len(num1)
y = len(num2)
if x == 1 or y == 1:
print('----result----',nu1*nu2)
else:
if x >= y:
n = x
else:
n = y
if n % 2 == 0:
n = n
else:
n = n + 1
a = int(num1[0:math.floor(x/2)]) #slicing the numbers for ltiplication
b = int(num1[math.ceil(x/2):x])
c = int(num2[0:math.floor(y/2)])
d = int(num2[math.ceil(y/2):y])
print('----reslut----',int((10**n)*(a*c) + (10**(n/2))*(a*d + b*c) + b*d))
#formula of karatsuba
karatsuba_multiplication(9,1234)
karatsuba_multiplication(7,12345)
karatsuba_multiplication(213,1234)
karatsuba_multiplication(1234,5678)
karatsuba_multiplication(12345,987)
karatsuba_multiplication(314159265358979323846264338327950288419716939937510582097494
4592,2718281828459045235360287471352662497757247093699959574966967627)
stop = timeit.default_timer() #countdown ends here
print('program time--',stop)
可能是这段代码很长,但它很简单。