Question

Multiply the following base 10 numbers together and then show how the same result can be obtained via the DFT (fft). Explain your method.

823415 multiplied by 234671

Answer 1

we know , multiplication of the above two numbers , 832415 and 234671 gives us the value of 193,231,621,465 which is obtained from basic multiplication.

these numbers can be further written in polynomial form in base 10 as:

X=832415= 5*1+1*10+4*100+2*1000+3*10000+8*100000

and similarly

Y= 1*1+7*10+6*100+4*1000+3*10000+2*100000

These can be written as

Now , multiplying these two number written as polynomials can be carried out using Discrete Fourier Transforms (fft).

This expression is solved my using the butterfly concept of fast fourier transform where base of each number is multiplied with wieghts to obtain the final multiplication value.

Now, while carrying out the multiplication, let us consider c_i =a_i*b_i . Therefore, by applying convolution of above two numbers , we get

a=[5 1 4 3 2 8] where a₀= 5, a₁=1 .... and a₅=8

and similarly for b=[1 7 6 4 3 2]

now

c₀= a₀*b₀ = 5*1 = 5

c₁=a₀*b₁+a₁*b₀= 5*7+1*1 =36

c₂=a₀*b₂+a_1*b₁+a₂*b₀=4+30+7=41

similarly for solving all the variables

c₃=20+6+7+3=36

c₄=15+4+24+21+2=66

c₅=10+3+16+18+14+8=69

c₆=54+12+12+12=90

c₇=8+9+8+48=73

c₈=6+6+24=36

c₉=4+24=28

c₁₀=16

Now, by multiplying all the variables with the respective weights, we get

Z=X*Y=c₀*10⁰+c₁*10¹+.... c₁₀*10¹⁰

Therefore Z=5*1+36*10+41*100+36*1000+... +16*10000000000=193,231,621,465