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!