File: polymult.e

package info (click to toggle)
euler 1.61.0-12
  • links: PTS, VCS
  • area: main
  • in suites: bookworm, bullseye, forky, sid, trixie
  • size: 5,164 kB
  • sloc: ansic: 24,761; sh: 8,314; makefile: 141; cpp: 47; php: 1
file content (13 lines) | stat: -rw-r--r-- 278 bytes parent folder | download | duplicates (8) 
1
2
3
4
5
6
7
8
9
10
11
12
13
 
comment
Multiplies two complex polynomials with FFT very fast
endcomment

function polymultfft (p,q)
	n=cols(p)-1; m=cols(q)-1; nm=n*m+1;
	k=2^(floor(log(nm)/log(2))+1);
	p1=fft(p|zeros(1,k-(n+1)));
	q1=fft(q|zeros(1,k-(m+1)));
	res=ifft(p1*q1);
	return res[1:nm];
endfunction