Karatsuba vs classic
Compare the Karatsuba algorithm to the classic digit-by-digit multiplication. This page is intended to compare the lengths of both approaches. If you are only interested in investigating the Karatsuba algorithm, head to a more responsive page here.
Note: The responsivity on this page is not that polished, you might want to zoom out in some cases.
Side to side comparison is useful for estimating the total complexity. The line counters track the number of single digit multiplications and you can often observe that small cutoff values produce less multiplications in the Karatsuba algorithm. But the total length of calculation also reflects the number of other actions (recursion, calculating intermediate results) that gets longer when decreasing the cutoff. This overhead is why the Karatsuba algorithm is not that useful for small number multiplications.
5623330091268960 * 5596883476039042 ----------------------- 0*2 = 0 0*4 = 0 0*0 = 0 0*9 = 0 0*3 = 0 0*0 = 0 0*6 = 0 0*7 = 0 0*4 = 0 0*3 = 0 0*8 = 0 0*8 = 0 0*6 = 0 0*9 = 0 0*5 = 0 0*5 = 0 6*2 = 12 6*4 = 24 6*0 = 0 6*9 = 54 6*3 = 18 6*0 = 0 6*6 = 36 6*7 = 42 6*4 = 24 6*3 = 18 6*8 = 48 6*8 = 48 6*6 = 36 6*9 = 54 6*5 = 30 6*5 = 30 9*2 = 18 9*4 = 36 9*0 = 0 9*9 = 81 9*3 = 27 9*0 = 0 9*6 = 54 9*7 = 63 9*4 = 36 9*3 = 27 9*8 = 72 9*8 = 72 9*6 = 54 9*9 = 81 9*5 = 45 9*5 = 45 8*2 = 16 8*4 = 32 8*0 = 0 8*9 = 72 8*3 = 24 8*0 = 0 8*6 = 48 8*7 = 56 8*4 = 32 8*3 = 24 8*8 = 64 8*8 = 64 8*6 = 48 8*9 = 72 8*5 = 40 8*5 = 40 6*2 = 12 6*4 = 24 6*0 = 0 6*9 = 54 6*3 = 18 6*0 = 0 6*6 = 36 6*7 = 42 6*4 = 24 6*3 = 18 6*8 = 48 6*8 = 48 6*6 = 36 6*9 = 54 6*5 = 30 6*5 = 30 2*2 = 4 2*4 = 8 2*0 = 0 2*9 = 18 2*3 = 6 2*0 = 0 2*6 = 12 2*7 = 14 2*4 = 8 2*3 = 6 2*8 = 16 2*8 = 16 2*6 = 12 2*9 = 18 2*5 = 10 2*5 = 10 1*2 = 2 1*4 = 4 1*0 = 0 1*9 = 9 1*3 = 3 1*0 = 0 1*6 = 6 1*7 = 7 1*4 = 4 1*3 = 3 1*8 = 8 1*8 = 8 1*6 = 6 1*9 = 9 1*5 = 5 1*5 = 5 9*2 = 18 9*4 = 36 9*0 = 0 9*9 = 81 9*3 = 27 9*0 = 0 9*6 = 54 9*7 = 63 9*4 = 36 9*3 = 27 9*8 = 72 9*8 = 72 9*6 = 54 9*9 = 81 9*5 = 45 9*5 = 45 0*2 = 0 0*4 = 0 0*0 = 0 0*9 = 0 0*3 = 0 0*0 = 0 0*6 = 0 0*7 = 0 0*4 = 0 0*3 = 0 0*8 = 0 0*8 = 0 0*6 = 0 0*9 = 0 0*5 = 0 0*5 = 0 0*2 = 0 0*4 = 0 0*0 = 0 0*9 = 0 0*3 = 0 0*0 = 0 0*6 = 0 0*7 = 0 0*4 = 0 0*3 = 0 0*8 = 0 0*8 = 0 0*6 = 0 0*9 = 0 0*5 = 0 0*5 = 0 3*2 = 6 3*4 = 12 3*0 = 0 3*9 = 27 3*3 = 9 3*0 = 0 3*6 = 18 3*7 = 21 3*4 = 12 3*3 = 9 3*8 = 24 3*8 = 24 3*6 = 18 3*9 = 27 3*5 = 15 3*5 = 15 3*2 = 6 3*4 = 12 3*0 = 0 3*9 = 27 3*3 = 9 3*0 = 0 3*6 = 18 3*7 = 21 3*4 = 12 3*3 = 9 3*8 = 24 3*8 = 24 3*6 = 18 3*9 = 27 3*5 = 15 3*5 = 15 3*2 = 6 3*4 = 12 3*0 = 0 3*9 = 27 3*3 = 9 3*0 = 0 3*6 = 18 3*7 = 21 3*4 = 12 3*3 = 9 3*8 = 24 3*8 = 24 3*6 = 18 3*9 = 27 3*5 = 15 3*5 = 15 2*2 = 4 2*4 = 8 2*0 = 0 2*9 = 18 2*3 = 6 2*0 = 0 2*6 = 12 2*7 = 14 2*4 = 8 2*3 = 6 2*8 = 16 2*8 = 16 2*6 = 12 2*9 = 18 2*5 = 10 2*5 = 10 6*2 = 12 6*4 = 24 6*0 = 0 6*9 = 54 6*3 = 18 6*0 = 0 6*6 = 36 6*7 = 42 6*4 = 24 6*3 = 18 6*8 = 48 6*8 = 48 6*6 = 36 6*9 = 54 6*5 = 30 6*5 = 30 5*2 = 10 5*4 = 20 5*0 = 0 5*9 = 45 5*3 = 15 5*0 = 0 5*6 = 30 5*7 = 35 5*4 = 20 5*3 = 15 5*8 = 40 5*8 = 40 5*6 = 30 5*9 = 45 5*5 = 25 5*5 = 25 ----------------------- 31473123268136360149128282736320
5623330091268960 * 5596883476039042 ----------------------- z0 = 91268960 * 76039042 = 0 z1 = 91268960 + 56233300 * 76039042 + 55968834 - z0 - z2 = 0 z2 = 56233300 * 55968834 = 0 ----------------------- z2*10^(2*8) + z1*10^8 + z0 = 0
91268960 * 76039042 ----------------------- z0 = 8960 * 9042 = 0 z1 = 8960 + 9126 * 9042 + 7603 - z0 - z2 = 0 z2 = 9126 * 7603 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
8960 * 9042 ----------------------- 0*2 = 0 0*4 = 0 0*0 = 0 0*9 = 0 6*2 = 12 6*4 = 24 6*0 = 0 6*9 = 54 9*2 = 18 9*4 = 36 9*0 = 0 9*9 = 81 8*2 = 16 8*4 = 32 8*0 = 0 8*9 = 72 ----------------------- 81016320
18086 * 16645 ----------------------- 6*5 = 30 6*4 = 24 6*6 = 36 6*6 = 36 6*1 = 6 8*5 = 40 8*4 = 32 8*6 = 48 8*6 = 48 8*1 = 8 0*5 = 0 0*4 = 0 0*6 = 0 0*6 = 0 0*1 = 0 8*5 = 40 8*4 = 32 8*6 = 48 8*6 = 48 8*1 = 8 1*5 = 5 1*4 = 4 1*6 = 6 1*6 = 6 1*1 = 1 ----------------------- 301041470
9126 * 7603 ----------------------- 6*3 = 18 6*0 = 0 6*6 = 36 6*7 = 42 2*3 = 6 2*0 = 0 2*6 = 12 2*7 = 14 1*3 = 3 1*0 = 0 1*6 = 6 1*7 = 7 9*3 = 27 9*0 = 0 9*6 = 54 9*7 = 63 ----------------------- 69384978
147502260 * 132007876 ----------------------- z0 = 2260 * 7876 = 0 z1 = 2260 + 14750 * 7876 + 13200 - z0 - z2 = 0 z2 = 14750 * 13200 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
2260 * 7876 ----------------------- 0*6 = 0 0*7 = 0 0*8 = 0 0*7 = 0 6*6 = 36 6*7 = 42 6*8 = 48 6*7 = 42 2*6 = 12 2*7 = 14 2*8 = 16 2*7 = 14 2*6 = 12 2*7 = 14 2*8 = 16 2*7 = 14 ----------------------- 17799760
17010 * 21076 ----------------------- 0*6 = 0 0*7 = 0 0*0 = 0 0*1 = 0 0*2 = 0 1*6 = 6 1*7 = 7 1*0 = 0 1*1 = 1 1*2 = 2 0*6 = 0 0*7 = 0 0*0 = 0 0*1 = 0 0*2 = 0 7*6 = 42 7*7 = 49 7*0 = 0 7*1 = 7 7*2 = 14 1*6 = 6 1*7 = 7 1*0 = 0 1*1 = 1 1*2 = 2 ----------------------- 358502760
14750 * 13200 ----------------------- 0*0 = 0 0*0 = 0 0*2 = 0 0*3 = 0 0*1 = 0 5*0 = 0 5*0 = 0 5*2 = 10 5*3 = 15 5*1 = 5 7*0 = 0 7*0 = 0 7*2 = 14 7*3 = 21 7*1 = 7 4*0 = 0 4*0 = 0 4*2 = 8 4*3 = 12 4*1 = 4 1*0 = 0 1*0 = 0 1*2 = 2 1*3 = 3 1*1 = 1 ----------------------- 194700000
56233300 * 55968834 ----------------------- z0 = 3300 * 8834 = 0 z1 = 3300 + 5623 * 8834 + 5596 - z0 - z2 = 0 z2 = 5623 * 5596 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
3300 * 8834 ----------------------- 0*4 = 0 0*3 = 0 0*8 = 0 0*8 = 0 0*4 = 0 0*3 = 0 0*8 = 0 0*8 = 0 3*4 = 12 3*3 = 9 3*8 = 24 3*8 = 24 3*4 = 12 3*3 = 9 3*8 = 24 3*8 = 24 ----------------------- 29152200
8923 * 14430 ----------------------- 3*0 = 0 3*3 = 9 3*4 = 12 3*4 = 12 3*1 = 3 2*0 = 0 2*3 = 6 2*4 = 8 2*4 = 8 2*1 = 2 9*0 = 0 9*3 = 27 9*4 = 36 9*4 = 36 9*1 = 9 8*0 = 0 8*3 = 24 8*4 = 32 8*4 = 32 8*1 = 8 ----------------------- 128758890
5623 * 5596 ----------------------- 3*6 = 18 3*9 = 27 3*5 = 15 3*5 = 15 2*6 = 12 2*9 = 18 2*5 = 10 2*5 = 10 6*6 = 36 6*9 = 54 6*5 = 30 6*5 = 30 5*6 = 30 5*9 = 45 5*5 = 25 5*5 = 25 ----------------------- 31466308