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.
3447056906147034 * 6585011214150724 ----------------------- 4*4 = 16 4*2 = 8 4*7 = 28 4*0 = 0 4*5 = 20 4*1 = 4 4*4 = 16 4*1 = 4 4*2 = 8 4*1 = 4 4*1 = 4 4*0 = 0 4*5 = 20 4*8 = 32 4*5 = 20 4*6 = 24 3*4 = 12 3*2 = 6 3*7 = 21 3*0 = 0 3*5 = 15 3*1 = 3 3*4 = 12 3*1 = 3 3*2 = 6 3*1 = 3 3*1 = 3 3*0 = 0 3*5 = 15 3*8 = 24 3*5 = 15 3*6 = 18 0*4 = 0 0*2 = 0 0*7 = 0 0*0 = 0 0*5 = 0 0*1 = 0 0*4 = 0 0*1 = 0 0*2 = 0 0*1 = 0 0*1 = 0 0*0 = 0 0*5 = 0 0*8 = 0 0*5 = 0 0*6 = 0 7*4 = 28 7*2 = 14 7*7 = 49 7*0 = 0 7*5 = 35 7*1 = 7 7*4 = 28 7*1 = 7 7*2 = 14 7*1 = 7 7*1 = 7 7*0 = 0 7*5 = 35 7*8 = 56 7*5 = 35 7*6 = 42 4*4 = 16 4*2 = 8 4*7 = 28 4*0 = 0 4*5 = 20 4*1 = 4 4*4 = 16 4*1 = 4 4*2 = 8 4*1 = 4 4*1 = 4 4*0 = 0 4*5 = 20 4*8 = 32 4*5 = 20 4*6 = 24 1*4 = 4 1*2 = 2 1*7 = 7 1*0 = 0 1*5 = 5 1*1 = 1 1*4 = 4 1*1 = 1 1*2 = 2 1*1 = 1 1*1 = 1 1*0 = 0 1*5 = 5 1*8 = 8 1*5 = 5 1*6 = 6 6*4 = 24 6*2 = 12 6*7 = 42 6*0 = 0 6*5 = 30 6*1 = 6 6*4 = 24 6*1 = 6 6*2 = 12 6*1 = 6 6*1 = 6 6*0 = 0 6*5 = 30 6*8 = 48 6*5 = 30 6*6 = 36 0*4 = 0 0*2 = 0 0*7 = 0 0*0 = 0 0*5 = 0 0*1 = 0 0*4 = 0 0*1 = 0 0*2 = 0 0*1 = 0 0*1 = 0 0*0 = 0 0*5 = 0 0*8 = 0 0*5 = 0 0*6 = 0 9*4 = 36 9*2 = 18 9*7 = 63 9*0 = 0 9*5 = 45 9*1 = 9 9*4 = 36 9*1 = 9 9*2 = 18 9*1 = 9 9*1 = 9 9*0 = 0 9*5 = 45 9*8 = 72 9*5 = 45 9*6 = 54 6*4 = 24 6*2 = 12 6*7 = 42 6*0 = 0 6*5 = 30 6*1 = 6 6*4 = 24 6*1 = 6 6*2 = 12 6*1 = 6 6*1 = 6 6*0 = 0 6*5 = 30 6*8 = 48 6*5 = 30 6*6 = 36 5*4 = 20 5*2 = 10 5*7 = 35 5*0 = 0 5*5 = 25 5*1 = 5 5*4 = 20 5*1 = 5 5*2 = 10 5*1 = 5 5*1 = 5 5*0 = 0 5*5 = 25 5*8 = 40 5*5 = 25 5*6 = 30 0*4 = 0 0*2 = 0 0*7 = 0 0*0 = 0 0*5 = 0 0*1 = 0 0*4 = 0 0*1 = 0 0*2 = 0 0*1 = 0 0*1 = 0 0*0 = 0 0*5 = 0 0*8 = 0 0*5 = 0 0*6 = 0 7*4 = 28 7*2 = 14 7*7 = 49 7*0 = 0 7*5 = 35 7*1 = 7 7*4 = 28 7*1 = 7 7*2 = 14 7*1 = 7 7*1 = 7 7*0 = 0 7*5 = 35 7*8 = 56 7*5 = 35 7*6 = 42 4*4 = 16 4*2 = 8 4*7 = 28 4*0 = 0 4*5 = 20 4*1 = 4 4*4 = 16 4*1 = 4 4*2 = 8 4*1 = 4 4*1 = 4 4*0 = 0 4*5 = 20 4*8 = 32 4*5 = 20 4*6 = 24 4*4 = 16 4*2 = 8 4*7 = 28 4*0 = 0 4*5 = 20 4*1 = 4 4*4 = 16 4*1 = 4 4*2 = 8 4*1 = 4 4*1 = 4 4*0 = 0 4*5 = 20 4*8 = 32 4*5 = 20 4*6 = 24 3*4 = 12 3*2 = 6 3*7 = 21 3*0 = 0 3*5 = 15 3*1 = 3 3*4 = 12 3*1 = 3 3*2 = 6 3*1 = 3 3*1 = 3 3*0 = 0 3*5 = 15 3*8 = 24 3*5 = 15 3*6 = 18 ----------------------- 22698908382793918627961381552616
3447056906147034 * 6585011214150724 ----------------------- z0 = 6147034 * 14150724 = 0 z1 = 6147034 + 34470569 * 14150724 + 65850112 - z0 - z2 = 0 z2 = 34470569 * 65850112 = 0 ----------------------- z2*10^(2*8) + z1*10^8 + z0 = 0
6147034 * 14150724 ----------------------- 4*4 = 16 4*2 = 8 4*7 = 28 4*0 = 0 4*5 = 20 4*1 = 4 4*4 = 16 4*1 = 4 3*4 = 12 3*2 = 6 3*7 = 21 3*0 = 0 3*5 = 15 3*1 = 3 3*4 = 12 3*1 = 3 0*4 = 0 0*2 = 0 0*7 = 0 0*0 = 0 0*5 = 0 0*1 = 0 0*4 = 0 0*1 = 0 7*4 = 28 7*2 = 14 7*7 = 49 7*0 = 0 7*5 = 35 7*1 = 7 7*4 = 28 7*1 = 7 4*4 = 16 4*2 = 8 4*7 = 28 4*0 = 0 4*5 = 20 4*1 = 4 4*4 = 16 4*1 = 4 1*4 = 4 1*2 = 2 1*7 = 7 1*0 = 0 1*5 = 5 1*1 = 1 1*4 = 4 1*1 = 1 6*4 = 24 6*2 = 12 6*7 = 42 6*0 = 0 6*5 = 30 6*1 = 6 6*4 = 24 6*1 = 6 ----------------------- 86984981552616
40617603 * 80000836 ----------------------- z0 = 7603 * 836 = 0 z1 = 7603 + 4061 * 836 + 8000 - z0 - z2 = 0 z2 = 4061 * 8000 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
7603 * 836 ----------------------- 3*6 = 18 3*3 = 9 3*8 = 24 0*6 = 0 0*3 = 0 0*8 = 0 6*6 = 36 6*3 = 18 6*8 = 48 7*6 = 42 7*3 = 21 7*8 = 56 ----------------------- 6356108
11664 * 8836 ----------------------- 4*6 = 24 4*3 = 12 4*8 = 32 4*8 = 32 6*6 = 36 6*3 = 18 6*8 = 48 6*8 = 48 6*6 = 36 6*3 = 18 6*8 = 48 6*8 = 48 1*6 = 6 1*3 = 3 1*8 = 8 1*8 = 8 1*6 = 6 1*3 = 3 1*8 = 8 1*8 = 8 ----------------------- 103063104
4061 * 8000 ----------------------- 1*0 = 0 1*0 = 0 1*0 = 0 1*8 = 8 6*0 = 0 6*0 = 0 6*0 = 0 6*8 = 48 0*0 = 0 0*0 = 0 0*0 = 0 0*8 = 0 4*0 = 0 4*0 = 0 4*0 = 0 4*8 = 32 ----------------------- 32488000
34470569 * 65850112 ----------------------- z0 = 569 * 112 = 0 z1 = 569 + 3447 * 112 + 6585 - z0 - z2 = 0 z2 = 3447 * 6585 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
569 * 112 ----------------------- 9*2 = 18 9*1 = 9 9*1 = 9 6*2 = 12 6*1 = 6 6*1 = 6 5*2 = 10 5*1 = 5 5*1 = 5 ----------------------- 63728
4016 * 6697 ----------------------- 6*7 = 42 6*9 = 54 6*6 = 36 6*6 = 36 1*7 = 7 1*9 = 9 1*6 = 6 1*6 = 6 0*7 = 0 0*9 = 0 0*6 = 0 0*6 = 0 4*7 = 28 4*9 = 36 4*6 = 24 4*6 = 24 ----------------------- 26895152
3447 * 6585 ----------------------- 7*5 = 35 7*8 = 56 7*5 = 35 7*6 = 42 4*5 = 20 4*8 = 32 4*5 = 20 4*6 = 24 4*5 = 20 4*8 = 32 4*5 = 20 4*6 = 24 3*5 = 15 3*8 = 24 3*5 = 15 3*6 = 18 ----------------------- 22698495