Question about multiplying complex polynomials with FFT

Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

stefanbalaz2's blog

By stefanbalaz2, history, 6 years ago, In English

Is there a way to multiply 2 polynomials with complex coefficients by using only 1 FFT and 1 inverse FFT?

stefanbalaz2
6 years ago
6

Comments (6)

Write comment?

Rosetxdy

6 years ago, hide # |

← Rev. 2 →

If you want to calc $$$f(x) * g(x)$$$, you can simply calc $$$(f(x) + g(x)i)^2=f(x)^2 - g(x)^2 +2f(x)g(x)i$$$.

→ Reply

donaastor

6 years ago, hide # ^ |

How does that help? f(x)^2-g(x)^2 doesn't have to be real, so how would you extract that part and the part f(x)g(x)? Secondly, squaring is also a multiplication, so your oracle for multiplication uses multiplication...

→ Reply

box

6 years ago, hide # ^ |

Squaring can be done in one FFT and one IFFT.

I think that what Rosetxdy means is that if f(x) and g(x) have real coefficients, you can construct (f(x)+ig(x)), square it, and extract the complex part for the answer. I'm not aware of any method to multiply polynomials with non-real coefficients in only 1 FFT and IFFT.

→ Reply

Rosetxdy

6 years ago, hide # ^ |

FFT code

#include<cmath>
#include<cctype>
#include<cstdio>
#include<algorithm>
#define g getchar()
using namespace std;
const int N=1<<20|10;
const double PI=acos(-1);
template<class o> void qr(o &x) {
	char c=g;x=0;
	while(!isdigit(c))c=g;
	while(isdigit(c))x=x*10+c-'0',c=g;
}
void write(int x) {
	if(x/10) write(x/10);
	putchar(x%10+'0');
}
struct CP {
	double x, y;
	CP(double x=0,double y=0):x(x),y(y){}
	CP operator +(CP const &b) const {
		return CP(x+b.x,y+b.y);
	}
	CP operator -(CP const &b) const {
		return CP(x-b.x,y-b.y);
	}
	CP operator *(CP const &b) const {
		return CP(x*b.x-y*b.y,x*b.y+y*b.x);
	}
}f[N<<1];
int n,m,tr[N<<1];
void fft(CP *f,bool flag) {
	for(int i=0;i<n;i++)
		if(i<tr[i]) swap(f[i],f[tr[i]]);
	for(int p=2;p<=n;p<<=1) {
		int len=p>>1;
		CP tg(cos(PI/len),sin(PI/len));
		if(!flag) tg.y=-tg.y;
		for(int k=0;k<n;k+=p) {
			CP buf(1,0);
			for(int l=k;l<k+len;l++) {
				CP t=buf*f[len+l];
				f[len+l]=f[l]-t;
				f[l]=f[l]+t;
				buf=buf*tg;
			}
		}
	}
}
int main() {
	qr(n); qr(m);
	for(int i=0;i<=n;i++) qr(f[i].x);
	for(int i=0;i<=m;i++) qr(f[i].y);
	for(m+=n,n=1;n<=m;n<<=1);
	for(int i=0;i<n;i++)
		tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	fft(f,1);
	for(int i=0;i<n;i++) f[i]=f[i]*f[i];
	fft(f,0); n<<=1;
	for(int i=0;i<=m;i++)
		printf("%d ",(int)(f[i].y/n+0.5));
	return 0;
}

This's my ancient code.:)

→ Reply