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.
7677860717296506 * 7015185529966590 ----------------------- z0 = 17296506 * 29966590 = 0 z1 = 17296506 + 76778607 * 29966590 + 70151855 - z0 - z2 = 0 z2 = 76778607 * 70151855 = 0 ----------------------- z2*10^(2*8) + z1*10^8 + z0 = 0
17296506 * 29966590 ----------------------- z0 = 6506 * 6590 = 0 z1 = 6506 + 1729 * 6590 + 2996 - z0 - z2 = 0 z2 = 1729 * 2996 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
6506 * 6590 ----------------------- 6*0 = 0 6*9 = 54 6*5 = 30 6*6 = 36 0*0 = 0 0*9 = 0 0*5 = 0 0*6 = 0 5*0 = 0 5*9 = 45 5*5 = 25 5*6 = 30 6*0 = 0 6*9 = 54 6*5 = 30 6*6 = 36 ----------------------- 42874540
8235 * 9586 ----------------------- 5*6 = 30 5*8 = 40 5*5 = 25 5*9 = 45 3*6 = 18 3*8 = 24 3*5 = 15 3*9 = 27 2*6 = 12 2*8 = 16 2*5 = 10 2*9 = 18 8*6 = 48 8*8 = 64 8*5 = 40 8*9 = 72 ----------------------- 78940710
1729 * 2996 ----------------------- 9*6 = 54 9*9 = 81 9*9 = 81 9*2 = 18 2*6 = 12 2*9 = 18 2*9 = 18 2*2 = 4 7*6 = 42 7*9 = 63 7*9 = 63 7*2 = 14 1*6 = 6 1*9 = 9 1*9 = 9 1*2 = 2 ----------------------- 5180084
94075113 * 100118445 ----------------------- z0 = 5113 * 8445 = 0 z1 = 5113 + 9407 * 8445 + 10011 - z0 - z2 = 0 z2 = 9407 * 10011 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
5113 * 8445 ----------------------- 3*5 = 15 3*4 = 12 3*4 = 12 3*8 = 24 1*5 = 5 1*4 = 4 1*4 = 4 1*8 = 8 1*5 = 5 1*4 = 4 1*4 = 4 1*8 = 8 5*5 = 25 5*4 = 20 5*4 = 20 5*8 = 40 ----------------------- 43179285
14520 * 18456 ----------------------- 0*6 = 0 0*5 = 0 0*4 = 0 0*8 = 0 0*1 = 0 2*6 = 12 2*5 = 10 2*4 = 8 2*8 = 16 2*1 = 2 5*6 = 30 5*5 = 25 5*4 = 20 5*8 = 40 5*1 = 5 4*6 = 24 4*5 = 20 4*4 = 16 4*8 = 32 4*1 = 4 1*6 = 6 1*5 = 5 1*4 = 4 1*8 = 8 1*1 = 1 ----------------------- 267981120
9407 * 10011 ----------------------- 7*1 = 7 7*1 = 7 7*0 = 0 7*0 = 0 7*1 = 7 0*1 = 0 0*1 = 0 0*0 = 0 0*0 = 0 0*1 = 0 4*1 = 4 4*1 = 4 4*0 = 0 4*0 = 0 4*1 = 4 9*1 = 9 9*1 = 9 9*0 = 0 9*0 = 0 9*1 = 9 ----------------------- 94173477
76778607 * 70151855 ----------------------- z0 = 8607 * 1855 = 0 z1 = 8607 + 7677 * 1855 + 7015 - z0 - z2 = 0 z2 = 7677 * 7015 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
8607 * 1855 ----------------------- 7*5 = 35 7*5 = 35 7*8 = 56 7*1 = 7 0*5 = 0 0*5 = 0 0*8 = 0 0*1 = 0 6*5 = 30 6*5 = 30 6*8 = 48 6*1 = 6 8*5 = 40 8*5 = 40 8*8 = 64 8*1 = 8 ----------------------- 15965985
16284 * 8870 ----------------------- 4*0 = 0 4*7 = 28 4*8 = 32 4*8 = 32 8*0 = 0 8*7 = 56 8*8 = 64 8*8 = 64 2*0 = 0 2*7 = 14 2*8 = 16 2*8 = 16 6*0 = 0 6*7 = 42 6*8 = 48 6*8 = 48 1*0 = 0 1*7 = 7 1*8 = 8 1*8 = 8 ----------------------- 144439080
7677 * 7015 ----------------------- 7*5 = 35 7*1 = 7 7*0 = 0 7*7 = 49 7*5 = 35 7*1 = 7 7*0 = 0 7*7 = 49 6*5 = 30 6*1 = 6 6*0 = 0 6*7 = 42 7*5 = 35 7*1 = 7 7*0 = 0 7*7 = 49 ----------------------- 53854155