Multiplying 41*37 with Fast Fourier Transform by hand

For large numbers, the elementary method of multiplication (convolution method) is FAR too slow.

Instead, using the rule that time domain convolution is equivalent to frequency domain point-wise multiplication, by travelling to the frequency domain and using point-wise multiplication, we can utilize the Fast Fourier Transform which removes redundant aliasing calculations.

1. The extra zeros to begin allow for tens column to overflow once multiplication occurs. More generally, tacking on zeros prior to convolution is known as zero-padding for a linear convolution. Without zeros, calculations will overflow into the next period and has a name as well: circular convolution.
2. I keep saying half cycle/second twiddle factor. Technically, its half cycle vs unit frequency period but you can intuitively imagine twiddle factor tracing the unit circle over a unit 1 sec time frame so I say that...
3. Half cycle/unit frequency period twiddle factor condenses because of conjugate symmetry of powers of 2. If not radix 2 transform, no symmetry exists and the twiddle factor generalizes to 1 cycle/unit frequency period where the frequency period first is periodically extended to the size of the upsample.

This video passes over intricacies of the FFT. You may find hefty tutorials at my Facebook Tutorial Website:
Math Music Tutorials (mrpolygon37)

[jaysonbunnell]

this was so awesome, and its the first video i’ve watched that made total sense

[yooos]

Brilliant! Gives the intuition behind FFT algorithm.

[JeevanjeetDash]

Could you please explain how to multiply two polynomials using FFT ? if we assume the above number as a polynomial i dont thnk this gives the correct answer after applying IFFT

[josephmargaryan]

Holy shit i have never seen methods like these before as I am not studying math, but now I am in a project where I need to work out matrix multiplication using FFT and circulant matrices

[StevenSiew]

So to multiply a 2 digit decimal number, you need a sample size of 4. So maybe you should multiple a 5 digit number which would require a sample size of 10. Division by 10 is a lot easier to calculate in decimal

[peterSobieraj]

I still don't understand how to do it.
But I will return to this video when I have more theory knowledge.
It seem like good example.

[MasterMindmars]

Good explanation.
Could you explain FFT with circular convolution? It is with modulo N.

[ishaanballal]

How is the time complexity of the algorithm O(n * logn * log(logn) )?

[kunalmohta]

Can you also do 1234 x 4321 using this method?

[StevenSiew]

Oh my god, you have to do division at the end? Division is hard, what if the number is huge, how do you do division with 20000 digits