# Optimum multiplication alogrithm

Found this interesting.

Mathematicians Discover the Perfect Way to Multiply

2 Likes

One of the first things that got me interested in working with computers and writing software was doing calculations with many-digit numbers. Like, finding sqrt(2) to 50 digits. I once did that by hand with a calculator, doing in effect math in â€śbase 1000â€ť or maybe it was 10000, and Newtonâ€™s iteration. Fun for nerds! But in my professional life that sort of thing doesnâ€™t come up much. When it does, on those rare occasions, I write assembler code. The one essential trick you need is â€śADCâ€ť - add with carry. You can have integers with any number of bytes, say 256 of them, and add two of them easily in assembler. But try to do that in Pascal, BASIC or C! The languages donâ€™t give you any access to the carry bit. It would be interesting to know if Crystal has some way to deal with that, but I donâ€™t think so. Iâ€™ve seen no language above assembler level that could deal with carry bits.

Multiplying - itâ€™s a lot of shifting and adding, and multiplying individual â€śdigitsâ€ť which might be 64 bit ints (unsigned) or whatever chunk of bits you define. Then you have â€ścarry digitsâ€ť because two single digits multiplied give you a two-digit value. Looking a the shifting, multiplication can be seen as a convolution (like a certain type of integral you learned in calculus) and everyone (with a PhD in signal processing) knows that a convolution can be done by computing Fourier transforms, multiplying point by point (no cross-products), and inverse Fourier transforming. This is older technology, Iâ€™m not sure, maybe 1970s. It would be fun, given an empty Sunday afternoon, to try implementing this in Crystal.

How does one â€śuse [the fast Fourier transform] in a much more violent wayâ€ť? I downloaded the PDF, might play with this new technique when I have time. Using Crystal, of course!