Procedure to Multiply two polynomials.
There are few methods to multiply two polynomial…
the naive approach is to multiply each term of first polynomial with term of second polynomial and store the value in an array of size m+n-1, where m is the for first polynomial, n is for second polynomial.
Other method include divide and conquer approach in which the power of variable are divided by 2 recursively and then multiplication occur.
Another divide and conquer approach include FFT method which has best running time complexity till i know…
This link might be helpful which shows the implementation of these methods but still FFT implementation is not there.
2 Likes
@rashedcs, links to Naive approach have been provided by my fellow mates @chandyshot and @masudk.
Here is the Link to understand the Fastest approach to Multiply two polynomials…(Editorial of a Problem)
The divide and conquer + FFT method has been described brilliantly.
1 Like
for nlogn algorithm. here is very good tutorial on codeforces Tutorial on FFT/NTT — The tough made simple. ( Part 1 ) - Codeforces
1 Like