Recursive Algorithm and Recurrence Relations Instructor:Sheng Zhong December 9,2020 1 Karatsuba Algorithm:One Example of Recursive Algorithms We learned multiplication in primary school.When we do 12 x 34,we essentially calculate 1 x 2 x 100+(2 x 3+1×4)×l0+2×4.In general,.we use the formula 2n-2 =01=0 where b=10 for decimal calculations,while b is often equal to some power of 2 in computers.This naive algorithm needs to do(2n-1)(n-1)"basic"multiplications (i.e.,multiplications over [0,b-1])in order to multiply two number from0-1].Naturally,one might suspect this is the best we could do,because there seems no obvious way to do it faster. Surprisingly,Russian mathematician Anatoly Karatsuba proposed a counter-intuitive algorithm that easily beats the naive algorithm for multiplication.The idea is quite simple:when you do 12 x 34,you should not waste your time doing two "basic"multiplications for(2 x 3+1 x 4).In stead,you should just calculate (1+2)×(3+4)-1×4-2×3,which is identical to(2×3+1×4).Noticing that you have to calculate 1 x 4 and 2x 3 for other parts of the expression anyway,for this specific part you just need to do one "basic" multiplication!Therefore,we have reduced the total amount of work. Below we present a straightforward recursive algorithm based on Karatsuba's idea. Algorithm karatsuba(,y) if (x <2)or (y 20) return xy; split in the middle and get (h,l); split y in the middle and get (hy,ly); ro karatsuba(lz,ly); r1=karatsuba((l+hz),(ly +hy)); r2 karatsuba(h,hy); return the number r2·22b+(r1-T2-ro）.2b+ro:Recursive Algorithm and Recurrence Relations Instructor: Sheng Zhong December 9, 2020 1 Karatsuba Algorithm: One Example of Recursive Algorithms We learned multiplication in primary school. When we do 12 × 34, we essentially calculate 1 × 2 × 100 + (2 × 3 + 1 × 4) × 10 + 2 × 4. In general, we use the formula ( nX−1 i=0 xi · b i ) · ( nX−1 i=0 yi · b i ) = 2 Xn−2 i=0 ( X i j=0 xjyi−j ) · b i , where b = 10 for decimal calculations, while b is often equal to some power of 2 in computers. This naive algorithm needs to do (2n − 1)(n − 1) “basic”multiplications (i.e., multiplications over [0, b − 1]) in order to multiply two number from [0, bn−1 − 1]. Naturally, one might suspect this is the best we could do, because there seems no obvious way to do it faster. Surprisingly, Russian mathematician Anatoly Karatsuba proposed a counter-intuitive algorithm that easily beats the naive algorithm for multiplication. The idea is quite simple: when you do 12 × 34, you should not waste your time doing two “basic” multiplications for (2 × 3 + 1 × 4). In stead, you should just calculate (1 + 2) × (3 + 4) − 1 × 4 − 2 × 3, which is identical to (2 × 3 + 1 × 4). Noticing that you have to calculate 1 × 4 and 2 × 3 for other parts of the expression anyway, for this specific part you just need to do one “basic” multiplication! Therefore, we have reduced the total amount of work. Below we present a straightforward recursive algorithm based on Karatsuba’s idea. Algorithm karatsuba(x, y) if (x < 2 b ) or (y < 2 b ) return xy; split x in the middle and get (hx, lx); split y in the middle and get (hy, ly); r0 = karatsuba(lx, ly); r1 = karatsuba((lx + hx),(ly + hy)); r2 = karatsuba(hx, hy); return the number r2 · 2 2b + (r1 − r2 − r0) · 2 b + r0. 1