FFT Polynomial Multiplication

A C implementation of polynomial multiplication with $O(n \log n)$ time complexity using the Fast Fourier Transform (FFT). This is an educational project and is not optimized for high performance.

Compilation

To compile the project, use the provided Makefile:

make all

Usage

Run the program using the following command:

./FFT [options]

Options

Flag	Description
-i <path>	Read input from a specific file (default: stdin).
-o <path>	Write output to a specific file (default: stdout).
-r <length>	Generate two random polynomials of the specified length.
-R	Generate only real numbers (used with -r).

Input Format

Input polynomials are expected in coefficient representation.

• Coefficients should be separated by spaces.
• The two polynomials must be separated by a newline.
• Complex numbers are supported (e.g., 3+4i, -2i, 5).

Example

Input:

1 3+i 3 -2
12 -3

This corresponds to multiplying:

1. $P(x) = 1 + (3+i)x + 3x^2 - 2x^3$
2. $Q(x) = 12 - 3x$