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.
2626692990596856 * 8523869626748727 ----------------------- z0 = 90596856 * 26748727 = 0 z1 = 90596856 + 26266929 * 26748727 + 85238696 - z0 - z2 = 0 z2 = 26266929 * 85238696 = 0 ----------------------- z2*10^(2*8) + z1*10^8 + z0 = 0
90596856 * 26748727 ----------------------- z0 = 6856 * 8727 = 0 z1 = 6856 + 9059 * 8727 + 2674 - z0 - z2 = 0 z2 = 9059 * 2674 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
6856 * 8727 ----------------------- 6*7 = 42 6*2 = 12 6*7 = 42 6*8 = 48 5*7 = 35 5*2 = 10 5*7 = 35 5*8 = 40 8*7 = 56 8*2 = 16 8*7 = 56 8*8 = 64 6*7 = 42 6*2 = 12 6*7 = 42 6*8 = 48 ----------------------- 59832312
15915 * 11401 ----------------------- 5*1 = 5 5*0 = 0 5*4 = 20 5*1 = 5 5*1 = 5 1*1 = 1 1*0 = 0 1*4 = 4 1*1 = 1 1*1 = 1 9*1 = 9 9*0 = 0 9*4 = 36 9*1 = 9 9*1 = 9 5*1 = 5 5*0 = 0 5*4 = 20 5*1 = 5 5*1 = 5 1*1 = 1 1*0 = 0 1*4 = 4 1*1 = 1 1*1 = 1 ----------------------- 181446915
9059 * 2674 ----------------------- 9*4 = 36 9*7 = 63 9*6 = 54 9*2 = 18 5*4 = 20 5*7 = 35 5*6 = 30 5*2 = 10 0*4 = 0 0*7 = 0 0*6 = 0 0*2 = 0 9*4 = 36 9*7 = 63 9*6 = 54 9*2 = 18 ----------------------- 24223766
116863785 * 111987423 ----------------------- z0 = 3785 * 7423 = 0 z1 = 3785 + 11686 * 7423 + 11198 - z0 - z2 = 0 z2 = 11686 * 11198 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
3785 * 7423 ----------------------- 5*3 = 15 5*2 = 10 5*4 = 20 5*7 = 35 8*3 = 24 8*2 = 16 8*4 = 32 8*7 = 56 7*3 = 21 7*2 = 14 7*4 = 28 7*7 = 49 3*3 = 9 3*2 = 6 3*4 = 12 3*7 = 21 ----------------------- 28096055
15471 * 18621 ----------------------- 1*1 = 1 1*2 = 2 1*6 = 6 1*8 = 8 1*1 = 1 7*1 = 7 7*2 = 14 7*6 = 42 7*8 = 56 7*1 = 7 4*1 = 4 4*2 = 8 4*6 = 24 4*8 = 32 4*1 = 4 5*1 = 5 5*2 = 10 5*6 = 30 5*8 = 40 5*1 = 5 1*1 = 1 1*2 = 2 1*6 = 6 1*8 = 8 1*1 = 1 ----------------------- 288085491
11686 * 11198 ----------------------- 6*8 = 48 6*9 = 54 6*1 = 6 6*1 = 6 6*1 = 6 8*8 = 64 8*9 = 72 8*1 = 8 8*1 = 8 8*1 = 8 6*8 = 48 6*9 = 54 6*1 = 6 6*1 = 6 6*1 = 6 1*8 = 8 1*9 = 9 1*1 = 1 1*1 = 1 1*1 = 1 1*8 = 8 1*9 = 9 1*1 = 1 1*1 = 1 1*1 = 1 ----------------------- 130859828
26266929 * 85238696 ----------------------- z0 = 6929 * 8696 = 0 z1 = 6929 + 2626 * 8696 + 8523 - z0 - z2 = 0 z2 = 2626 * 8523 = 0 ----------------------- z2*10^(2*4) + z1*10^4 + z0 = 0
6929 * 8696 ----------------------- 9*6 = 54 9*9 = 81 9*6 = 54 9*8 = 72 2*6 = 12 2*9 = 18 2*6 = 12 2*8 = 16 9*6 = 54 9*9 = 81 9*6 = 54 9*8 = 72 6*6 = 36 6*9 = 54 6*6 = 36 6*8 = 48 ----------------------- 60254584
9555 * 17219 ----------------------- 5*9 = 45 5*1 = 5 5*2 = 10 5*7 = 35 5*1 = 5 5*9 = 45 5*1 = 5 5*2 = 10 5*7 = 35 5*1 = 5 5*9 = 45 5*1 = 5 5*2 = 10 5*7 = 35 5*1 = 5 9*9 = 81 9*1 = 9 9*2 = 18 9*7 = 63 9*1 = 9 ----------------------- 164527545
2626 * 8523 ----------------------- 6*3 = 18 6*2 = 12 6*5 = 30 6*8 = 48 2*3 = 6 2*2 = 4 2*5 = 10 2*8 = 16 6*3 = 18 6*2 = 12 6*5 = 30 6*8 = 48 2*3 = 6 2*2 = 4 2*5 = 10 2*8 = 16 ----------------------- 22381398