0
$\begingroup$

I suppose most of us are familiar with multiplication algorithms for decimals numbers we learn in primary school. 13*13 = 3*13 + 10*13 = 169 what actually is performed in this case (but of course they don't tell the kids) is a convolution, thirteen "moves around" and is multiplied with a new digit at each new position and then everything is summed up. Although it can not be a "pure" convolution, since we must regard carry, which occurs if any number in the convolution becomes larger than 9.

So I guess my question would be, what more mathematics would we need to put these algorithms the kids learn into the language of convolutions and Fourier Transforms?


My own work so far is limited to just calculating divisions, sums and modulo 10 on the digits after the convolution. I do not know how to "translate" these operations into any more enlightening operations. I have learned some very basic abstract algebra, but I don't know how to use it in this context ( if it is applicable ).

$\endgroup$
  • 1
    $\begingroup$ Some of the fastest integer multiplication algorithms for very large integers use Fourier transforms (or Number-theoretic transforms, which are algebraically similar). Wikipedia has a pretty complete article about it here: en.wikipedia.org/wiki/… $\endgroup$ – James Hanson Dec 1 '15 at 19:57
  • $\begingroup$ Ah thank you! I knew there existed algorithms for approximating $\pi$ by using Fourier Transforms to speed up multiplications. That was around some time when that was a popular method to measure CPU speed I think. I will give it a try although my number theoretic skills are a bit limited :) $\endgroup$ – mathreadler Dec 1 '15 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.