Using Fourier Transforms To Multiply Numbers - Interactive Examples

2019-01-10 - By Robert Elder

The purpose of this article is to show you step-by-step examples of how to use the Fourier transform algorithm to multiply two numbers. The primary advantage of using fourier transforms to multiply numbers is that you can use the asymptotically much faster 'Fast Fourier Transform algorithm', to achieve better performance than one would get with the classical grade school multiplication algorithm. This article is actually just a more specific illustration of the ideas shown in overlap add and overlap save, which contains even more details than are provided here. Therefore, if you find that details are missing in this article, they are likely to be found in the previous one.

Various details in the format and namings used in this article have been left as similar as possible to those found in the more general article on overlap add and overlap save in order to make it easier for the reader to see the association between this article and the previous one. For example, the use of 'x' and 'h' that was used in the previous article to represent the signal and the filter can be understood to represent 'number a' and 'number b' in this article. Furthermore, the previous article presented the math for convolutions using the 'overlap add' and 'overlap save' algorithms which are actually two different approaches to achieving the same result (not two separate steps in a single calculation). Therefore, the calculation of number multiplication will be presented twice below, once for overlap add and once for overlap save in order to illustrate that either method arrives at the correct answer.

Also, the calculations presented here will rely on floating point math in the intermediary fourier transform calculations, so correctness of the result is not guranteed for every case that you can input here, but a later section of this article will discuss approaches that can eliminate floating math entirely.

Visit the non-AMP page for the Fourier Transform Multiplication Demo.

Multiplication Efficiency and Accuracy

As noted above, the algorithm presented here uses floating point math, however there is mathematical tool called the Number-theoretic Transform that can be used to avoid performing the calculation using floating point math.

In the above explanation, a single value of L was always chosen such that N would always be a power of two (as required by the fast Fourier transform). In general L could have been any power of two, and depending on how you chose it, it can have an effect on the asymptotic run-time.

Another thing worth noting: although the primary motivation for using the Fourier transform in this calculation was to use the fast fourier transform algorithm, if you check the source code for this page, you'll note that I was lazy and just used the slow fourier transform algorithm, but the results should still be the same.

If you liked this article, you may also be interested in some well-known algorithms that also use Fourier transforms related techniques:

Overlap Add, Overlap Save Visual Explanation Published 2018-02-10	$35.00 CAD Alan Turning, Ada Lovelace, Kurt Gödel Portaits	Endpoint Discontinuities and Spectral Leakage Published 2018-02-10	Fourier Transform Coefficients Of Real Valued Audio Signals Published 2018-02-10
The Regular Expression Visualizer, Simulator & Cross-Compiler Tool Published 2020-07-09	Why Is It so Hard to Detect Keyup Event on Linux? Published 2019-01-10	Myers Diff Algorithm - Code & Interactive Visualization Published 2017-06-07	Interfaces - The Most Important Software Engineering Concept Published 2016-02-01

Why Bother Subscribing?

Free Software/Engineering Content. I publish all of my educational content publicly for free so everybody can make use of it. Why bother signing up for a paid 'course', when you can just sign up for this email list?
Read about cool new products that I'm building. How do I make money? Glad you asked! You'll get some emails with examples of things that I sell. You might even get some business ideas of your own :)
People actually like this email list. I know that sounds crazy, because who actually subscribes to email lists these days, right? Well, some do, and if you end up not liking it, I give you permission to unsubscribe and mark it as spam.