3 ms·

You've left out the key observation that makes Karatsuba multiplication faster than naive multiplication: after having computed [A] and [D], we can compute the

by Chinjut 12y ago

You've left out the key observation that makes Karatsuba multiplication faster than naive multiplication: after having computed [A] and [D], we can compute the combined [B + C] with one multiplication rather than two. That is, to multiply two binomials of a given size, we only need three multiplications of binomials of half that size, rather than the naive four. This is what improves the runtime of Karatsuba multiplication to Ө(n^(log_2(3))) from the ordinary Ө(n^2). Why are we able to get away with only three recursive multiplications instead of four? The observation here is that in the product (Em + F)(Gm + H) = EGm^2 + (EH + FG)m + FH, after the first and last coefficients EG and FH have already been calculated, the middle coefficient (EH + FG) can be calculated using only the one new multiplication in (E + F)(G + H) - EG - FH, rather than the naive two in its definition.

Chinjut 12y ago
We can also view Karatsuba multiplication as a special case of a general class of polynomial multiplication algorithms (after all, numbers written in a particular base are just polynomials evaluated at that base). Naively, multiplying two polynomials of degree n takes (n + 1)^2 multiplications of coefficients, but a more clever approach would evaluate the two polynomials at a number of points, then multiply those values together, then fit a polynomial to the results. This involves only (2n + 1) multiplications (the number of values needed to determine the resulting polynomial). Thus, our clever binomial trick is the observation that multiplying two polynomials of degree 1 yields a polynomial of degree 2, so we need to pick 3 points for our evaluation; if we pick the points to be 0, 1, and "infinity" (in the sense of a value such that P("infinity") = the leading coefficient of P, just as P(0) equals the degree zero coefficient of P), then we get our Karatsuba trick: we break (Ex + F) down into F, E + F, and E, and similarly for (Gx + H), then multiply the corresponding values together (our three multiplications), and from those results reconstitute the polynomial product we are interested in. (And we can apply this recursively to break down the multiplication of polynomials of greater degree than 1) An even more clever approach notes that we can evaluate our polynomials at various roots of unity all at once very efficiently with the Fast Fourier Transform, which is what leads to the most efficient multiplication algorithms known.

by Chinjut 12y ago

Chinjut 12y ago

We can also view Karatsuba multiplication as a special case of a general class of polynomial multiplication algorithms (after all, numbers written in a particular base are just polynomials evaluated at that base). Naively, multiplying two polynomials of degree n takes (n + 1)^2 multiplications of coefficients, but a more clever approach would evaluate the two polynomials at a number of points, then multiply those values together, then fit a polynomial to the results. This involves only (2n + 1) multiplications (the number of values needed to determine the resulting polynomial). Thus, our clever binomial trick is the observation that multiplying two polynomials of degree 1 yields a polynomial of degree 2, so we need to pick 3 points for our evaluation; if we pick the points to be 0, 1, and "infinity" (in the sense of a value such that P("infinity") = the leading coefficient of P, just as P(0) equals the degree zero coefficient of P), then we get our Karatsuba trick: we break (Ex + F) down into F, E + F, and E, and similarly for (Gx + H), then multiply the corresponding values together (our three multiplications), and from those results reconstitute the polynomial product we are interested in. (And we can apply this recursively to break down the multiplication of polynomials of greater degree than 1) An even more clever approach notes that we can evaluate our polynomials at various roots of unity all at once very efficiently with the Fast Fourier Transform, which is what leads to the most efficient multiplication algorithms known.