Karatsuba algorithm
Play around with the calculator and see how many steps does it take for the Karatsuba algorithm to multiply the selected numbers.
Note: for a side to side comparison of classic and Karatsuba algorithms you can view this page. The display length will somewhat reflect the overhead in Karatsuba’s algorithm.
For comparision multiplying these 16 digit numbers numbers with the classic
digit-by-digit algorithm would’ve required 256 single digit
multiplications. But here’s how Karatsuba’s algorithm would perform. The
display starts with calculating z0, z1 and z2 and using them to get the
final result. The multiplications invloved in z0, z1 and z2 are detailed
below. You can click on the orange expressions to highlight their
multiplication and scroll to it. Depending on values and the selected cutoff it
will either be computed using the classic multiplication or use another step
of Karatsuba’s algorithm.
6716538557774059 * 2979536697075794 ----------------------- z0 = 57774059 * 97075794 = 0 z1 = 57774059 + 67165385 * 97075794 + 29795366 - z0 - z2 = 0 z2 = 67165385 * 29795366 = 0 ----------------------- z2*10^(2*8) + z1*10^8 + z0 = 0
57774059 * 97075794 ----------------------- z0 = 4059 * 5794 = 0 z1 = 4059 + 5777 * 5794 + 9707 - z0 - z2 = 0 z2 = 5777 * 9707 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
4059 * 5794 ----------------------- 9*4 = 36 9*9 = 81 9*7 = 63 9*5 = 45 5*4 = 20 5*9 = 45 5*7 = 35 5*5 = 25 0*4 = 0 0*9 = 0 0*7 = 0 0*5 = 0 4*4 = 16 4*9 = 36 4*7 = 28 4*5 = 20 ----------------------- 23517846
9836 * 15501 ----------------------- 6*1 = 6 6*0 = 0 6*5 = 30 6*5 = 30 6*1 = 6 3*1 = 3 3*0 = 0 3*5 = 15 3*5 = 15 3*1 = 3 8*1 = 8 8*0 = 0 8*5 = 40 8*5 = 40 8*1 = 8 9*1 = 9 9*0 = 0 9*5 = 45 9*5 = 45 9*1 = 9 ----------------------- 152467836
5777 * 9707 ----------------------- 7*7 = 49 7*0 = 0 7*7 = 49 7*9 = 63 7*7 = 49 7*0 = 0 7*7 = 49 7*9 = 63 7*7 = 49 7*0 = 0 7*7 = 49 7*9 = 63 5*7 = 35 5*0 = 0 5*7 = 35 5*9 = 45 ----------------------- 56077339
124939444 * 126871160 ----------------------- z0 = 9444 * 1160 = 0 z1 = 9444 + 12493 * 1160 + 12687 - z0 - z2 = 0 z2 = 12493 * 12687 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
9444 * 1160 ----------------------- 4*0 = 0 4*6 = 24 4*1 = 4 4*1 = 4 4*0 = 0 4*6 = 24 4*1 = 4 4*1 = 4 4*0 = 0 4*6 = 24 4*1 = 4 4*1 = 4 9*0 = 0 9*6 = 54 9*1 = 9 9*1 = 9 ----------------------- 10955040
21937 * 13847 ----------------------- 7*7 = 49 7*4 = 28 7*8 = 56 7*3 = 21 7*1 = 7 3*7 = 21 3*4 = 12 3*8 = 24 3*3 = 9 3*1 = 3 9*7 = 63 9*4 = 36 9*8 = 72 9*3 = 27 9*1 = 9 1*7 = 7 1*4 = 4 1*8 = 8 1*3 = 3 1*1 = 1 2*7 = 14 2*4 = 8 2*8 = 16 2*3 = 6 2*1 = 2 ----------------------- 303761639
12493 * 12687 ----------------------- 3*7 = 21 3*8 = 24 3*6 = 18 3*2 = 6 3*1 = 3 9*7 = 63 9*8 = 72 9*6 = 54 9*2 = 18 9*1 = 9 4*7 = 28 4*8 = 32 4*6 = 24 4*2 = 8 4*1 = 4 2*7 = 14 2*8 = 16 2*6 = 12 2*2 = 4 2*1 = 2 1*7 = 7 1*8 = 8 1*6 = 6 1*2 = 2 1*1 = 1 ----------------------- 158498691
67165385 * 29795366 ----------------------- z0 = 5385 * 5366 = 0 z1 = 5385 + 6716 * 5366 + 2979 - z0 - z2 = 0 z2 = 6716 * 2979 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
5385 * 5366 ----------------------- 5*6 = 30 5*6 = 30 5*3 = 15 5*5 = 25 8*6 = 48 8*6 = 48 8*3 = 24 8*5 = 40 3*6 = 18 3*6 = 18 3*3 = 9 3*5 = 15 5*6 = 30 5*6 = 30 5*3 = 15 5*5 = 25 ----------------------- 28895910
12101 * 8345 ----------------------- 1*5 = 5 1*4 = 4 1*3 = 3 1*8 = 8 0*5 = 0 0*4 = 0 0*3 = 0 0*8 = 0 1*5 = 5 1*4 = 4 1*3 = 3 1*8 = 8 2*5 = 10 2*4 = 8 2*3 = 6 2*8 = 16 1*5 = 5 1*4 = 4 1*3 = 3 1*8 = 8 ----------------------- 100982845
6716 * 2979 ----------------------- 6*9 = 54 6*7 = 42 6*9 = 54 6*2 = 12 1*9 = 9 1*7 = 7 1*9 = 9 1*2 = 2 7*9 = 63 7*7 = 49 7*9 = 63 7*2 = 14 6*9 = 54 6*7 = 42 6*9 = 54 6*2 = 12 ----------------------- 20006964