 robertelder.org Go back Open original

# Using Fourier Transforms To Multiply Numbers - Interactive Examples

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 =

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

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: