Multiplying Big Numbers Using FFT

In summary, the conversation discusses the use of the Fast Fourier Transform (FFT) for multiplying large numbers and the confusion around the use of more complex algorithms when a simple one seems to work just as well. The proposed algorithm involves rewriting the numbers as polynomials and using the FFT and Convolution Theorem to compute the multiplication quickly. The complexity analysis shows that the algorithm has a complexity of m log(m) or log(d) log(log(d)). The conversation also mentions that the FFT is discussed in CLRS as a method for polynomial multiplication with a complexity of n log(n). The confusion around the use of roots of unity in the FFT is also mentioned.
  • #1
n+1
13
0
Multiplying big numbers is a very common application of the FFT, and as such, there are many papers on the subject available online.

However, these papers all use sophisticated algorithms where a simple one seems to work. My question is, what's wrong with the simple algorithm:

Multiplication of Two Big Numbers Algorithm:
Input: Two integers, a and b, stored in base B.
Step 1: Write a and b as polynomials in Z[B ], a(B) and b(B).Let m be the the larger of the two degrees.
Step 2: Rewrite a(B) and b(B) as 2m-dimensional vectors by padding with 0s. Denote these vectors by v_a and v_b.
Step 3: Use the FFT and Convolution Theorem to compute the Convolution of v_a and v_b quickly.
Step 4: Recover ab by reversing step 2 and 1.

Complexity Analysis
Let D = Max(a,b). Notice log(D) ~ m.
Step 1: 1. You're just reinterpreting what a list represents.
Step 2: m. You're at most adding 2m zeroes.
Step 3: m log(m).
Step 4: m. You're doing similar operations as in steps 1 and 2.
Conclusion: m log(m) or log(d) log(log(d)).
 
Technology news on Phys.org
  • #2
CLRS discusses polynomial multiplication (Chapter 32). They verify that polynomial multiplication using the FFT has complexity n log(n).

I guess my confusion stemmed from talk about "the interpolation of polynomials using roots of unity." Every paper I read talks about this. As far as I can tell, this is just a problem-specific description of the FFT. I don't know why the authors are so eager about adding this extraneous information -- but again, they know way more about the subject than I do. Oh well.
 

Related to Multiplying Big Numbers Using FFT

1. What is FFT?

FFT stands for Fast Fourier Transform, which is an algorithm used to efficiently compute the Discrete Fourier Transform (DFT) of a sequence or signal. It is commonly used in signal processing, data compression, and multiplying large numbers.

2. How does FFT help with multiplying big numbers?

FFT can be used to multiply large numbers by converting the numbers into their polynomial representations, multiplying the polynomials using FFT, and then converting the result back into the original number format. This method reduces the time complexity from O(n^2) to O(nlogn), making it much faster for multiplying big numbers.

3. Is FFT the only method for multiplying big numbers?

No, there are other methods for multiplying big numbers such as Karatsuba algorithm and Schönhage–Strassen algorithm. However, FFT is often the preferred method due to its simplicity and efficiency.

4. What are the limitations of using FFT for multiplying big numbers?

FFT is most effective for multiplying numbers with a large number of digits. If the numbers have a similar number of digits, FFT may not provide a significant improvement in speed compared to traditional multiplication methods. Additionally, implementing FFT for multiplying big numbers may require knowledge of signal processing and advanced mathematics.

5. Can FFT be used for multiplying decimal numbers?

No, FFT is typically used for multiplying integers and may not be suitable for multiplying decimal numbers. However, there are adaptations of FFT such as the Number Theoretic Transform (NTT) that can be used for multiplying decimal numbers.

Similar threads

  • Programming and Computer Science
Replies
9
Views
627
  • Programming and Computer Science
Replies
1
Views
1K
Replies
9
Views
1K
  • Programming and Computer Science
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
504
Replies
65
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
764
  • Programming and Computer Science
Replies
25
Views
4K
  • Engineering and Comp Sci Homework Help
Replies
33
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
1K
Back
Top