# 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.

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.

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 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:

# Software Engineering

Why Is It so Hard to Detect Keyup Event on Linux?Published 2019-01-10 | ## Subscribe to New Posts | FIFO, LIFO Considered HarmfulPublished 2017-09-24 | @RobertElderSoft On Twitter |

Myers Diff Algorithm - Code & Interactive VisualizationPublished 2017-06-07 | Facebook Page | Silently Corrupting an Eclipse Workspace: The Ultimate PrankPublished 2017-03-23 | Amazon Cloud Servers For Beginners: Console VS Command-LinePublished 2017-03-20 |

An Overview Of Computer Science Concepts For EngineersPublished 2017-03-05 | Coming Full Circle On Code DuplicationPublished 2016-05-10 | Stories & Tips: 50+ Interviews With Facebook, Twitter, Amazon & OthersPublished 2016-03-22 | Interfaces - The Most Important Software Engineering ConceptPublished 2016-02-01 |

Virtual Memory With 256 Bytes of RAM - Interactive DemoPublished 2016-01-10 |