3 ms·

The Fast Fibonacci article links to an article on an algorithm called "karatsuba-multiplication". Oi - I just lost two hours of my life to reverse-engineering i

The Fast Fibonacci article links to an article on an algorithm called "karatsuba-multiplication". Oi - I just lost two hours of my life to reverse-engineering it. (But it was worth!). In case anyone else was wondering, here's what I got out of it. x*y = (x)(y) // fragment into binomials = (x/m*m + x%m)(y/m*m + y%m) // uses integer division // distribute binomials = (x/m*m)(y/m*m) + (x/m*m)(y%m) + (x%m)(y/m*m) + (x%m)(y%m) // extract modulus from each term = [(x/m)(y/m)]m^2 + [(x/m)(y%m) + (x%m)(y/m)]m + [(x%m)(y%m)] // rename terms = [A]m^2 + [B+C]m + [D] // where [A] is what nayuki calls (a), // [B+C] is what nayuki calls (a-b-c), and // [D] is what nayuki calls (c). Q.E.D. Geometrically, what we're doing is: 1) taking the area of two binomials; 2) shrinking Quadrant A by a factor of the modulus's perfect-square (e.g. 3^2); 3) shrinking Quadrant B and Quadrant C by a factor of the modulus per se (e.g. 3); and 4) leaving Quadrant D the same. [B B B D D] scaled by modulus [B D D] [A A A C C] ----------------> [A C C] [A A A C C] where m = 3 [A A A C C]

jordigh 12y ago
> I just lost two hours of my life to reverse-engineering it. I wouldn't call that "lost", myself. Good job. :-) There is also Strassen's algorithm for matrix multiplication. Something to keep in mind if you ever need to multiply really gigantic matrices. https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm
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.

jordigh 12y ago

> I just lost two hours of my life to reverse-engineering it. I wouldn't call that "lost", myself. Good job. :-) There is also Strassen's algorithm for matrix multiplication. Something to keep in mind if you ever need to multiply really gigantic matrices. https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm

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.