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.
1999851038793216 * 9651362928827216 ----------------------- 6*6 = 36 6*1 = 6 6*2 = 12 6*7 = 42 6*2 = 12 6*8 = 48 6*8 = 48 6*2 = 12 6*9 = 54 6*2 = 12 6*6 = 36 6*3 = 18 6*1 = 6 6*5 = 30 6*6 = 36 6*9 = 54 1*6 = 6 1*1 = 1 1*2 = 2 1*7 = 7 1*2 = 2 1*8 = 8 1*8 = 8 1*2 = 2 1*9 = 9 1*2 = 2 1*6 = 6 1*3 = 3 1*1 = 1 1*5 = 5 1*6 = 6 1*9 = 9 2*6 = 12 2*1 = 2 2*2 = 4 2*7 = 14 2*2 = 4 2*8 = 16 2*8 = 16 2*2 = 4 2*9 = 18 2*2 = 4 2*6 = 12 2*3 = 6 2*1 = 2 2*5 = 10 2*6 = 12 2*9 = 18 3*6 = 18 3*1 = 3 3*2 = 6 3*7 = 21 3*2 = 6 3*8 = 24 3*8 = 24 3*2 = 6 3*9 = 27 3*2 = 6 3*6 = 18 3*3 = 9 3*1 = 3 3*5 = 15 3*6 = 18 3*9 = 27 9*6 = 54 9*1 = 9 9*2 = 18 9*7 = 63 9*2 = 18 9*8 = 72 9*8 = 72 9*2 = 18 9*9 = 81 9*2 = 18 9*6 = 54 9*3 = 27 9*1 = 9 9*5 = 45 9*6 = 54 9*9 = 81 7*6 = 42 7*1 = 7 7*2 = 14 7*7 = 49 7*2 = 14 7*8 = 56 7*8 = 56 7*2 = 14 7*9 = 63 7*2 = 14 7*6 = 42 7*3 = 21 7*1 = 7 7*5 = 35 7*6 = 42 7*9 = 63 8*6 = 48 8*1 = 8 8*2 = 16 8*7 = 56 8*2 = 16 8*8 = 64 8*8 = 64 8*2 = 16 8*9 = 72 8*2 = 16 8*6 = 48 8*3 = 24 8*1 = 8 8*5 = 40 8*6 = 48 8*9 = 72 3*6 = 18 3*1 = 3 3*2 = 6 3*7 = 21 3*2 = 6 3*8 = 24 3*8 = 24 3*2 = 6 3*9 = 27 3*2 = 6 3*6 = 18 3*3 = 9 3*1 = 3 3*5 = 15 3*6 = 18 3*9 = 27 0*6 = 0 0*1 = 0 0*2 = 0 0*7 = 0 0*2 = 0 0*8 = 0 0*8 = 0 0*2 = 0 0*9 = 0 0*2 = 0 0*6 = 0 0*3 = 0 0*1 = 0 0*5 = 0 0*6 = 0 0*9 = 0 1*6 = 6 1*1 = 1 1*2 = 2 1*7 = 7 1*2 = 2 1*8 = 8 1*8 = 8 1*2 = 2 1*9 = 9 1*2 = 2 1*6 = 6 1*3 = 3 1*1 = 1 1*5 = 5 1*6 = 6 1*9 = 9 5*6 = 30 5*1 = 5 5*2 = 10 5*7 = 35 5*2 = 10 5*8 = 40 5*8 = 40 5*2 = 10 5*9 = 45 5*2 = 10 5*6 = 30 5*3 = 15 5*1 = 5 5*5 = 25 5*6 = 30 5*9 = 45 8*6 = 48 8*1 = 8 8*2 = 16 8*7 = 56 8*2 = 16 8*8 = 64 8*8 = 64 8*2 = 16 8*9 = 72 8*2 = 16 8*6 = 48 8*3 = 24 8*1 = 8 8*5 = 40 8*6 = 48 8*9 = 72 9*6 = 54 9*1 = 9 9*2 = 18 9*7 = 63 9*2 = 18 9*8 = 72 9*8 = 72 9*2 = 18 9*9 = 81 9*2 = 18 9*6 = 54 9*3 = 27 9*1 = 9 9*5 = 45 9*6 = 54 9*9 = 81 9*6 = 54 9*1 = 9 9*2 = 18 9*7 = 63 9*2 = 18 9*8 = 72 9*8 = 72 9*2 = 18 9*9 = 81 9*2 = 18 9*6 = 54 9*3 = 27 9*1 = 9 9*5 = 45 9*6 = 54 9*9 = 81 9*6 = 54 9*1 = 9 9*2 = 18 9*7 = 63 9*2 = 18 9*8 = 72 9*8 = 72 9*2 = 18 9*9 = 81 9*2 = 18 9*6 = 54 9*3 = 27 9*1 = 9 9*5 = 45 9*6 = 54 9*9 = 81 1*6 = 6 1*1 = 1 1*2 = 2 1*7 = 7 1*2 = 2 1*8 = 8 1*8 = 8 1*2 = 2 1*9 = 9 1*2 = 2 1*6 = 6 1*3 = 3 1*1 = 1 1*5 = 5 1*6 = 6 1*9 = 9 ----------------------- 19301288178985443537202816966656
1999851038793216 * 9651362928827216 ----------------------- z0 = 38793216 * 28827216 = 0 z1 = 38793216 + 19998510 * 28827216 + 96513629 - z0 - z2 = 0 z2 = 19998510 * 96513629 = 0 ----------------------- z2*10^(2*8) + z1*10^8 + z0 = 0
38793216 * 28827216 ----------------------- z0 = 3216 * 7216 = 0 z1 = 3216 + 3879 * 7216 + 2882 - z0 - z2 = 0 z2 = 3879 * 2882 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
3216 * 7216 ----------------------- 6*6 = 36 6*1 = 6 6*2 = 12 6*7 = 42 1*6 = 6 1*1 = 1 1*2 = 2 1*7 = 7 2*6 = 12 2*1 = 2 2*2 = 4 2*7 = 14 3*6 = 18 3*1 = 3 3*2 = 6 3*7 = 21 ----------------------- 23206656
7095 * 10098 ----------------------- 5*8 = 40 5*9 = 45 5*0 = 0 5*0 = 0 5*1 = 5 9*8 = 72 9*9 = 81 9*0 = 0 9*0 = 0 9*1 = 9 0*8 = 0 0*9 = 0 0*0 = 0 0*0 = 0 0*1 = 0 7*8 = 56 7*9 = 63 7*0 = 0 7*0 = 0 7*1 = 7 ----------------------- 71645310
3879 * 2882 ----------------------- 9*2 = 18 9*8 = 72 9*8 = 72 9*2 = 18 7*2 = 14 7*8 = 56 7*8 = 56 7*2 = 14 8*2 = 16 8*8 = 64 8*8 = 64 8*2 = 16 3*2 = 6 3*8 = 24 3*8 = 24 3*2 = 6 ----------------------- 11179278
58791726 * 125340845 ----------------------- z0 = 1726 * 845 = 0 z1 = 1726 + 5879 * 845 + 12534 - z0 - z2 = 0 z2 = 5879 * 12534 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
1726 * 845 ----------------------- 6*5 = 30 6*4 = 24 6*8 = 48 2*5 = 10 2*4 = 8 2*8 = 16 7*5 = 35 7*4 = 28 7*8 = 56 1*5 = 5 1*4 = 4 1*8 = 8 ----------------------- 1458470
7605 * 13379 ----------------------- 5*9 = 45 5*7 = 35 5*3 = 15 5*3 = 15 5*1 = 5 0*9 = 0 0*7 = 0 0*3 = 0 0*3 = 0 0*1 = 0 6*9 = 54 6*7 = 42 6*3 = 18 6*3 = 18 6*1 = 6 7*9 = 63 7*7 = 49 7*3 = 21 7*3 = 21 7*1 = 7 ----------------------- 101747295
5879 * 12534 ----------------------- 9*4 = 36 9*3 = 27 9*5 = 45 9*2 = 18 9*1 = 9 7*4 = 28 7*3 = 21 7*5 = 35 7*2 = 14 7*1 = 7 8*4 = 32 8*3 = 24 8*5 = 40 8*2 = 16 8*1 = 8 5*4 = 20 5*3 = 15 5*5 = 25 5*2 = 10 5*1 = 5 ----------------------- 73687386
19998510 * 96513629 ----------------------- z0 = 8510 * 3629 = 0 z1 = 8510 + 1999 * 3629 + 9651 - z0 - z2 = 0 z2 = 1999 * 9651 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
8510 * 3629 ----------------------- 0*9 = 0 0*2 = 0 0*6 = 0 0*3 = 0 1*9 = 9 1*2 = 2 1*6 = 6 1*3 = 3 5*9 = 45 5*2 = 10 5*6 = 30 5*3 = 15 8*9 = 72 8*2 = 16 8*6 = 48 8*3 = 24 ----------------------- 30882790
10509 * 13280 ----------------------- 9*0 = 0 9*8 = 72 9*2 = 18 9*3 = 27 9*1 = 9 0*0 = 0 0*8 = 0 0*2 = 0 0*3 = 0 0*1 = 0 5*0 = 0 5*8 = 40 5*2 = 10 5*3 = 15 5*1 = 5 0*0 = 0 0*8 = 0 0*2 = 0 0*3 = 0 0*1 = 0 1*0 = 0 1*8 = 8 1*2 = 2 1*3 = 3 1*1 = 1 ----------------------- 139559520
1999 * 9651 ----------------------- 9*1 = 9 9*5 = 45 9*6 = 54 9*9 = 81 9*1 = 9 9*5 = 45 9*6 = 54 9*9 = 81 9*1 = 9 9*5 = 45 9*6 = 54 9*9 = 81 1*1 = 1 1*5 = 5 1*6 = 6 1*9 = 9 ----------------------- 19292349