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.
1781432626072619 * 9391888762999408 ----------------------- 9*8 = 72 9*0 = 0 9*4 = 36 9*9 = 81 9*9 = 81 9*9 = 81 9*2 = 18 9*6 = 54 9*7 = 63 9*8 = 72 9*8 = 72 9*8 = 72 9*1 = 9 9*9 = 81 9*3 = 27 9*9 = 81 1*8 = 8 1*0 = 0 1*4 = 4 1*9 = 9 1*9 = 9 1*9 = 9 1*2 = 2 1*6 = 6 1*7 = 7 1*8 = 8 1*8 = 8 1*8 = 8 1*1 = 1 1*9 = 9 1*3 = 3 1*9 = 9 6*8 = 48 6*0 = 0 6*4 = 24 6*9 = 54 6*9 = 54 6*9 = 54 6*2 = 12 6*6 = 36 6*7 = 42 6*8 = 48 6*8 = 48 6*8 = 48 6*1 = 6 6*9 = 54 6*3 = 18 6*9 = 54 2*8 = 16 2*0 = 0 2*4 = 8 2*9 = 18 2*9 = 18 2*9 = 18 2*2 = 4 2*6 = 12 2*7 = 14 2*8 = 16 2*8 = 16 2*8 = 16 2*1 = 2 2*9 = 18 2*3 = 6 2*9 = 18 7*8 = 56 7*0 = 0 7*4 = 28 7*9 = 63 7*9 = 63 7*9 = 63 7*2 = 14 7*6 = 42 7*7 = 49 7*8 = 56 7*8 = 56 7*8 = 56 7*1 = 7 7*9 = 63 7*3 = 21 7*9 = 63 0*8 = 0 0*0 = 0 0*4 = 0 0*9 = 0 0*9 = 0 0*9 = 0 0*2 = 0 0*6 = 0 0*7 = 0 0*8 = 0 0*8 = 0 0*8 = 0 0*1 = 0 0*9 = 0 0*3 = 0 0*9 = 0 6*8 = 48 6*0 = 0 6*4 = 24 6*9 = 54 6*9 = 54 6*9 = 54 6*2 = 12 6*6 = 36 6*7 = 42 6*8 = 48 6*8 = 48 6*8 = 48 6*1 = 6 6*9 = 54 6*3 = 18 6*9 = 54 2*8 = 16 2*0 = 0 2*4 = 8 2*9 = 18 2*9 = 18 2*9 = 18 2*2 = 4 2*6 = 12 2*7 = 14 2*8 = 16 2*8 = 16 2*8 = 16 2*1 = 2 2*9 = 18 2*3 = 6 2*9 = 18 6*8 = 48 6*0 = 0 6*4 = 24 6*9 = 54 6*9 = 54 6*9 = 54 6*2 = 12 6*6 = 36 6*7 = 42 6*8 = 48 6*8 = 48 6*8 = 48 6*1 = 6 6*9 = 54 6*3 = 18 6*9 = 54 2*8 = 16 2*0 = 0 2*4 = 8 2*9 = 18 2*9 = 18 2*9 = 18 2*2 = 4 2*6 = 12 2*7 = 14 2*8 = 16 2*8 = 16 2*8 = 16 2*1 = 2 2*9 = 18 2*3 = 6 2*9 = 18 3*8 = 24 3*0 = 0 3*4 = 12 3*9 = 27 3*9 = 27 3*9 = 27 3*2 = 6 3*6 = 18 3*7 = 21 3*8 = 24 3*8 = 24 3*8 = 24 3*1 = 3 3*9 = 27 3*3 = 9 3*9 = 27 4*8 = 32 4*0 = 0 4*4 = 16 4*9 = 36 4*9 = 36 4*9 = 36 4*2 = 8 4*6 = 24 4*7 = 28 4*8 = 32 4*8 = 32 4*8 = 32 4*1 = 4 4*9 = 36 4*3 = 12 4*9 = 36 1*8 = 8 1*0 = 0 1*4 = 4 1*9 = 9 1*9 = 9 1*9 = 9 1*2 = 2 1*6 = 6 1*7 = 7 1*8 = 8 1*8 = 8 1*8 = 8 1*1 = 1 1*9 = 9 1*3 = 3 1*9 = 9 8*8 = 64 8*0 = 0 8*4 = 32 8*9 = 72 8*9 = 72 8*9 = 72 8*2 = 16 8*6 = 48 8*7 = 56 8*8 = 64 8*8 = 64 8*8 = 64 8*1 = 8 8*9 = 72 8*3 = 24 8*9 = 72 7*8 = 56 7*0 = 0 7*4 = 28 7*9 = 63 7*9 = 63 7*9 = 63 7*2 = 14 7*6 = 42 7*7 = 49 7*8 = 56 7*8 = 56 7*8 = 56 7*1 = 7 7*9 = 63 7*3 = 21 7*9 = 63 1*8 = 8 1*0 = 0 1*4 = 4 1*9 = 9 1*9 = 9 1*9 = 9 1*2 = 2 1*6 = 6 1*7 = 7 1*8 = 8 1*8 = 8 1*8 = 8 1*1 = 1 1*9 = 9 1*3 = 3 1*9 = 9 ----------------------- 16731017062851956599965662009552
1781432626072619 * 9391888762999408 ----------------------- z0 = 26072619 * 62999408 = 0 z1 = 26072619 + 17814326 * 62999408 + 93918887 - z0 - z2 = 0 z2 = 17814326 * 93918887 = 0 ----------------------- z2*10^(2*8) + z1*10^8 + z0 = 0
26072619 * 62999408 ----------------------- z0 = 2619 * 9408 = 0 z1 = 2619 + 2607 * 9408 + 6299 - z0 - z2 = 0 z2 = 2607 * 6299 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
2619 * 9408 ----------------------- 9*8 = 72 9*0 = 0 9*4 = 36 9*9 = 81 1*8 = 8 1*0 = 0 1*4 = 4 1*9 = 9 6*8 = 48 6*0 = 0 6*4 = 24 6*9 = 54 2*8 = 16 2*0 = 0 2*4 = 8 2*9 = 18 ----------------------- 24639552
5226 * 15707 ----------------------- 6*7 = 42 6*0 = 0 6*7 = 42 6*5 = 30 6*1 = 6 2*7 = 14 2*0 = 0 2*7 = 14 2*5 = 10 2*1 = 2 2*7 = 14 2*0 = 0 2*7 = 14 2*5 = 10 2*1 = 2 5*7 = 35 5*0 = 0 5*7 = 35 5*5 = 25 5*1 = 5 ----------------------- 82084782
2607 * 6299 ----------------------- 7*9 = 63 7*9 = 63 7*2 = 14 7*6 = 42 0*9 = 0 0*9 = 0 0*2 = 0 0*6 = 0 6*9 = 54 6*9 = 54 6*2 = 12 6*6 = 36 2*9 = 18 2*9 = 18 2*2 = 4 2*6 = 12 ----------------------- 16421493
43886945 * 156918295 ----------------------- z0 = 6945 * 8295 = 0 z1 = 6945 + 4388 * 8295 + 15691 - z0 - z2 = 0 z2 = 4388 * 15691 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
6945 * 8295 ----------------------- 5*5 = 25 5*9 = 45 5*2 = 10 5*8 = 40 4*5 = 20 4*9 = 36 4*2 = 8 4*8 = 32 9*5 = 45 9*9 = 81 9*2 = 18 9*8 = 72 6*5 = 30 6*9 = 54 6*2 = 12 6*8 = 48 ----------------------- 57608775
11333 * 23986 ----------------------- 3*6 = 18 3*8 = 24 3*9 = 27 3*3 = 9 3*2 = 6 3*6 = 18 3*8 = 24 3*9 = 27 3*3 = 9 3*2 = 6 3*6 = 18 3*8 = 24 3*9 = 27 3*3 = 9 3*2 = 6 1*6 = 6 1*8 = 8 1*9 = 9 1*3 = 3 1*2 = 2 1*6 = 6 1*8 = 8 1*9 = 9 1*3 = 3 1*2 = 2 ----------------------- 271833338
4388 * 15691 ----------------------- 8*1 = 8 8*9 = 72 8*6 = 48 8*5 = 40 8*1 = 8 8*1 = 8 8*9 = 72 8*6 = 48 8*5 = 40 8*1 = 8 3*1 = 3 3*9 = 27 3*6 = 18 3*5 = 15 3*1 = 3 4*1 = 4 4*9 = 36 4*6 = 24 4*5 = 20 4*1 = 4 ----------------------- 68852108
17814326 * 93918887 ----------------------- z0 = 4326 * 8887 = 0 z1 = 4326 + 1781 * 8887 + 9391 - z0 - z2 = 0 z2 = 1781 * 9391 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
4326 * 8887 ----------------------- 6*7 = 42 6*8 = 48 6*8 = 48 6*8 = 48 2*7 = 14 2*8 = 16 2*8 = 16 2*8 = 16 3*7 = 21 3*8 = 24 3*8 = 24 3*8 = 24 4*7 = 28 4*8 = 32 4*8 = 32 4*8 = 32 ----------------------- 38445162
6107 * 18278 ----------------------- 7*8 = 56 7*7 = 49 7*2 = 14 7*8 = 56 7*1 = 7 0*8 = 0 0*7 = 0 0*2 = 0 0*8 = 0 0*1 = 0 1*8 = 8 1*7 = 7 1*2 = 2 1*8 = 8 1*1 = 1 6*8 = 48 6*7 = 42 6*2 = 12 6*8 = 48 6*1 = 6 ----------------------- 111623746
1781 * 9391 ----------------------- 1*1 = 1 1*9 = 9 1*3 = 3 1*9 = 9 8*1 = 8 8*9 = 72 8*3 = 24 8*9 = 72 7*1 = 7 7*9 = 63 7*3 = 21 7*9 = 63 1*1 = 1 1*9 = 9 1*3 = 3 1*9 = 9 ----------------------- 16725371