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.
9777540788109290 * 2667165258367476 ----------------------- z0 = 88109290 * 58367476 = 0 z1 = 88109290 + 97775407 * 58367476 + 26671652 - z0 - z2 = 0 z2 = 97775407 * 26671652 = 0 ----------------------- z2*10^(2*8) + z1*10^8 + z0 = 0
88109290 * 58367476 ----------------------- z0 = 9290 * 7476 = 0 z1 = 9290 + 8810 * 7476 + 5836 - z0 - z2 = 0 z2 = 8810 * 5836 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
9290 * 7476 ----------------------- 0*6 = 0 0*7 = 0 0*4 = 0 0*7 = 0 9*6 = 54 9*7 = 63 9*4 = 36 9*7 = 63 2*6 = 12 2*7 = 14 2*4 = 8 2*7 = 14 9*6 = 54 9*7 = 63 9*4 = 36 9*7 = 63 ----------------------- 69452040
18100 * 13312 ----------------------- 0*2 = 0 0*1 = 0 0*3 = 0 0*3 = 0 0*1 = 0 0*2 = 0 0*1 = 0 0*3 = 0 0*3 = 0 0*1 = 0 1*2 = 2 1*1 = 1 1*3 = 3 1*3 = 3 1*1 = 1 8*2 = 16 8*1 = 8 8*3 = 24 8*3 = 24 8*1 = 8 1*2 = 2 1*1 = 1 1*3 = 3 1*3 = 3 1*1 = 1 ----------------------- 240947200
8810 * 5836 ----------------------- 0*6 = 0 0*3 = 0 0*8 = 0 0*5 = 0 1*6 = 6 1*3 = 3 1*8 = 8 1*5 = 5 8*6 = 48 8*3 = 24 8*8 = 64 8*5 = 40 8*6 = 48 8*3 = 24 8*8 = 64 8*5 = 40 ----------------------- 51415160
185884697 * 85039128 ----------------------- z0 = 4697 * 9128 = 0 z1 = 4697 + 18588 * 9128 + 8503 - z0 - z2 = 0 z2 = 18588 * 8503 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
4697 * 9128 ----------------------- 7*8 = 56 7*2 = 14 7*1 = 7 7*9 = 63 9*8 = 72 9*2 = 18 9*1 = 9 9*9 = 81 6*8 = 48 6*2 = 12 6*1 = 6 6*9 = 54 4*8 = 32 4*2 = 8 4*1 = 4 4*9 = 36 ----------------------- 42874216
23285 * 17631 ----------------------- 5*1 = 5 5*3 = 15 5*6 = 30 5*7 = 35 5*1 = 5 8*1 = 8 8*3 = 24 8*6 = 48 8*7 = 56 8*1 = 8 2*1 = 2 2*3 = 6 2*6 = 12 2*7 = 14 2*1 = 2 3*1 = 3 3*3 = 9 3*6 = 18 3*7 = 21 3*1 = 3 2*1 = 2 2*3 = 6 2*6 = 12 2*7 = 14 2*1 = 2 ----------------------- 410537835
18588 * 8503 ----------------------- 8*3 = 24 8*0 = 0 8*5 = 40 8*8 = 64 8*3 = 24 8*0 = 0 8*5 = 40 8*8 = 64 5*3 = 15 5*0 = 0 5*5 = 25 5*8 = 40 8*3 = 24 8*0 = 0 8*5 = 40 8*8 = 64 1*3 = 3 1*0 = 0 1*5 = 5 1*8 = 8 ----------------------- 158053764
97775407 * 26671652 ----------------------- z0 = 5407 * 1652 = 0 z1 = 5407 + 9777 * 1652 + 2667 - z0 - z2 = 0 z2 = 9777 * 2667 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
5407 * 1652 ----------------------- 7*2 = 14 7*5 = 35 7*6 = 42 7*1 = 7 0*2 = 0 0*5 = 0 0*6 = 0 0*1 = 0 4*2 = 8 4*5 = 20 4*6 = 24 4*1 = 4 5*2 = 10 5*5 = 25 5*6 = 30 5*1 = 5 ----------------------- 8932364
15184 * 4319 ----------------------- 4*9 = 36 4*1 = 4 4*3 = 12 4*4 = 16 8*9 = 72 8*1 = 8 8*3 = 24 8*4 = 32 1*9 = 9 1*1 = 1 1*3 = 3 1*4 = 4 5*9 = 45 5*1 = 5 5*3 = 15 5*4 = 20 1*9 = 9 1*1 = 1 1*3 = 3 1*4 = 4 ----------------------- 65579696
9777 * 2667 ----------------------- 7*7 = 49 7*6 = 42 7*6 = 42 7*2 = 14 7*7 = 49 7*6 = 42 7*6 = 42 7*2 = 14 7*7 = 49 7*6 = 42 7*6 = 42 7*2 = 14 9*7 = 63 9*6 = 54 9*6 = 54 9*2 = 18 ----------------------- 26075259