Karatsuba Multiplications

Q1： 请计算：$x=1234$, $y=5678$, $x\ast y=?$

这个问题其实我们在三年级的时候就学过，用乘法竖式进行运算。但是有没有其他的方法，或者说，如果 $x,y$ 非常大的时候，我们有没有什么办法可以有效的缩短运算时间呢？

这就引出 Karatsuba 乘法算法

首先，举例来看 Karatsuba 乘法算法 是怎么做的 $x\ast y$

思考，Karatsuba这么做的数学原理是什么？

---

Karatsuba 数学原理

Recursive 递归

Karatsuba不断的将乘数分成两个部分，从而实现降维的乘法。
然后不断的通过递归的方式得到将降维后的乘数的结果。

当然，如果想要理解 Karatsuba 乘法原理 不得不首先理解 递归 Recursive 的概念，若读者已知递归，可直接跳到最后的 python程序部分。

---

递归 & 斐波那契数列

对于递归的介绍，我将通过一个经典的案例，即 斐波那契数列 Fibonacci sequence 来介绍。

首先，形如：1 1 2 3 5 8 13 21 … 被称为斐波那契数列。
很明显，斐波那契数列从第三项开始都为前两项的和，即 2=1+1, 3=2+1, … 21=13+8,…
试问第100项为多少？

code

'''About Recursive and FibonacciCreate by Hongduo at 6.Oct.2022
'''def Fibonacci(x):if(x == 1 or x == 2):return 1else:return Fibonacci(x-1) + Fibonacci(x-2)print(Fibonacci(100))

通过递归

$Fib(100)=Fib(99)+Fib(98)$
$Fib(99)=Fib(98)+Fib(97)$
$...$
$Fib(3)=Fib(2)+Fib(1)$

–

python & Karatsuba

def karatsuba(num1,num2):n_max = max(len(str(int(num1))), len(str(int(num2))))if n_max == 1:return int(num1*num2)n = n_max + n_max%2a = num1//10**(n/2)b = num1%10**(n/2)c = num2//10**(n/2)d = num2%10**(n/2)t1 = karatsuba(a,c)t3 = karatsuba(b,d)t2 = karatsuba(a+b,c+d) - t1 - t3return int(t1*10**n + t2*10**(n/2) + t3)print(karatsuba(123456789,123456789))