Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.lang.Math;
- class Complex{
- double re;
- double im;
- public Complex(double real, double imag) {
- re = real;
- im = imag;
- }
- public String toString() {
- double tRe = (double)Math.round(re * 100000) / 100000;
- double tIm = (double)Math.round(im * 100000) / 100000;
- if (tIm == 0) return tRe + "";
- if (tRe == 0) return tIm + "i";
- if (tIm < 0) return tRe + "-" + (-tIm) + "i";
- return tRe + "+" + tIm + "i";
- }
- public Complex conj() {
- return new Complex(re, -im);
- }
- // sestevanje
- public Complex plus(Complex b) {
- Complex a = this;
- double real = a.re + b.re;
- double imag = a.im + b.im;
- return new Complex(real, imag);
- }
- // odstevanje
- public Complex minus(Complex b) {
- Complex a = this;
- double real = a.re - b.re;
- double imag = a.im - b.im;
- return new Complex(real, imag);
- }
- // mnozenje z drugim kompleksnim stevilo
- public Complex times(Complex b) {
- Complex a = this;
- double real = a.re * b.re - a.im * b.im;
- double imag = a.re * b.im + a.im * b.re;
- return new Complex(real, imag);
- }
- // mnozenje z realnim stevilom
- public Complex times(double alpha) {
- return new Complex(alpha * re, alpha * im);
- }
- // reciprocna vrednost kompleksnega stevila
- public Complex reciprocal() {
- double scale = re*re + im*im;
- return new Complex(re / scale, -im / scale);
- }
- // deljenje
- public Complex divides(Complex b) {
- Complex a = this;
- return a.times(b.reciprocal());
- }
- // e^this
- public Complex exp() {
- return new Complex(Math.exp(re) * Math.cos(im), Math.exp(re) * Math.sin(im));
- }
- //potenca komplesnega stevila
- public Complex pow(int k) {
- Complex c = new Complex(1,0);
- for (int i = 0; i <k ; i++) {
- c = c.times(this);
- }
- return c;
- }
- }
- public class i8{
- public static void printArray( double[] array ){
- int len = array.length;
- System.out.print( array[0] );
- for (int i = 1; i < len; i++ ){
- System.out.print( " " + array[i] );
- }
- System.out.println();
- return;
- }
- public static void printComplexArray( Complex[] array ){
- int len = array.length;
- System.out.print( array[0].toString() );
- for (int i = 1; i < len; i++ ){
- System.out.print( " " + array[i].toString() );
- }
- System.out.println();
- return;
- }
- public static Complex[] recursiveFFT(double[] vhod ){
- int len = vhod.length;
- if (len==1){
- Complex res = new Complex( 1.0*vhod[0] , 0.0 );
- Complex[] resitev = new Complex[1];
- resitev[0] = res;
- return resitev;
- }
- double[] novSod = new double[len/2];
- double[] novLih = new double[len/2];
- for ( int i = 0; i < len/2; i++){
- novSod[i] = vhod[2*i];
- novLih[i] = vhod[2*i+1];
- }
- Complex[] sodC = new Complex[len/2];
- Complex[] lihC = new Complex[len/2];
- sodC = recursiveFFT(novSod);
- lihC = recursiveFFT(novLih);
- Complex compI = new Complex(0.0,1.0);
- Complex exponent = compI.times(Math.PI*2.0/len);
- Complex w = exponent.exp();
- Complex wk = new Complex(1.0,0.0);
- Complex[] y = new Complex[len];
- for ( int k = 0; k < len/2; k++ ){
- y[k] = sodC[k].plus( wk.times(lihC[k]));
- y[k + len/2 ] = sodC[k].minus(wk.times(lihC[k]));
- wk = wk.times(w);
- }
- printComplexArray(y);
- return y;
- }
- public static Complex[] recursiveFFTInverse(Complex[] vhod ){
- int len = vhod.length;
- if (len==1) return vhod;
- Complex[] novSod = new Complex[len/2];
- Complex[] novLih = new Complex[len/2];
- for (int i = 0; i < len/2; i++){
- novSod[i] = vhod[2*i];
- novLih[i] = vhod[2*i+1];
- }
- Complex[] vmesSodo = recursiveFFTInverse(novSod);
- Complex[] vmesLiho = recursiveFFTInverse(novLih);
- Complex compI = new Complex(0.0,1.0); // to je i.
- Complex exponent = compI.times(Math.PI*2.0/len);
- Complex w = exponent.exp();
- w=w.reciprocal();
- Complex wk = new Complex(1.0,0.0);
- Complex[] resitev = new Complex[len];
- for ( int k = 0; k < len/2; k++ ){
- resitev[k] = vmesSodo[k].plus( wk.times(vmesLiho[k]));
- resitev[k+len/2] = vmesSodo[k].minus(wk.times(vmesLiho[k]));
- wk = wk.times(w);
- }
- printComplexArray(resitev);
- return resitev;
- }
- public static void main( String[] args ){
- Scanner sc = new Scanner( System.in );
- int n = sc.nextInt();
- int stTock = (int)(Math.pow(2,(int)Math.ceil(Math.log(2*n - 1)/Math.log(2))));
- double[] koefPrviPolinom = new double[stTock];
- double[] koefDrugiPolinom = new double[stTock];
- for ( int i = 0; i < n; i++ ) koefPrviPolinom[i] = 1.0*sc.nextInt();
- for ( int i = 0; i < n; i++ ) koefDrugiPolinom[i] = 1.0*sc.nextInt();
- Complex[] vrednostiPrvi = recursiveFFT(koefPrviPolinom);
- Complex[] vrednostiDrugi = recursiveFFT(koefDrugiPolinom);
- Complex[] arrayZmnozkov = new Complex[stTock];
- for ( int i = 0; i < stTock; i++ ){
- arrayZmnozkov[i] = vrednostiPrvi[i].times( vrednostiDrugi[i] );
- }
- Complex[] y = recursiveFFTInverse(arrayZmnozkov);
- Complex _n = new Complex(stTock,0);
- for(int i=0;i<stTock;i++) y[i] = y[i].divides(_n);
- printComplexArray(y);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement