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.

Number A:

Number B:

Number A Corresponding Polynomial:

Number B Corresponding Polynomial:

Number A x[n] (time domain): 3, -1, 0, 3, 2, 0, 1, 2, 1

Number B h[n] (time domain): 1, -1, 1

M = len(h[x]) =

L = (Chosen so that N is a power of two in order to use Fast Fourier Transform)

N = L + M - 1 =

Output Length = len(x[x]) + len(h[x]) -1 =

Output Polynomial Corresponding to Final Answer =

Final answer =

The first step in using fast convolution to perform multiplication involves creating polynomials that represent the two numbers we wish to multiply (shown above).

Multiplication Using Overlap Add

Below, you will see the partitioning step of the overlap add algorithm:

Now that the polynomial representing our number has been partitioned into intervals labeled x_i[n], we can use the Fourier transform to calculate the convolution. Note that in the previous article, the matrix version of overlap add is literally just the gradeschool multiplication algorithm.

Now that the contribution of each interval has been calculated as y_i[n], we can add them together to calculate the polynomial corresponding to our answer, y[n]:

As you can see above, the result y[n] represents the coefficients of a polynomial that corresponds to the result of multiplying the two input numbers together. Note that evaluating the resulting polynomial in a given base can be done without using any multiplication by adding, shifting and carrying digits.

This concludes the calculation of multiplying the two input numbers using 'overlap add' with the final answer being presented in red above.

Multiplication Using Overlap Save

For details on the differences between 'overlap add' and 'overlap save', see the previous article..

Below, you will observe that the red 'overlap' elements are 'scraped' or set to zero. This could be a useful alternative to 'overlap add' if you need to avoid extra additions in your algorithm.

This concludes the calculation of multiplying the two input numbers using 'overlap save' with the final answer being presented in red above.

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 Turing, 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.