fork(15) download 
  1. /**
  2.     This program used to to multiply two polynomials A and B have the same (M/2-1)-degree ( M is power of 2 )
  3.     @result C is a polynomial with M-1 degree ( M is power of 2 )
  4. */
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <cmath>
  8. #include <complex>
  9. using namespace std;
  10. const long double PI = acos(-1);
  11. const int M = (1<<3);
  12. typedef long double ld;
  13.  
  14. complex<ld> getPrimitiveRootOfUnity(int gen) {
  15.     return complex<ld>(cos(2*PI/gen), sin(2*PI/gen));
  16. }
  17. class Polynomial {
  18. private:
  19.     int sz;
  20. public:
  21.     complex<ld> *f;
  22.     Polynomial(int sz) {
  23.         this->sz = sz;
  24.         this->f = new complex<ld>[this->sz];
  25.         for(int i = 0; i < this->sz; i++) this->f[i] = complex<ld>(0,0);
  26.     }
  27. };
  28. inline Polynomial FFT(Polynomial A, int m, complex<ld> w)
  29. {
  30.     if (m==1) return A;
  31.  
  32.     Polynomial A_even(m/2);
  33.     Polynomial A_odd(m/2);
  34.     for(int i = 0; i < m; i+=2) {
  35.         A_even.f[i/2] = A.f[i];
  36.         A_odd.f[i/2] = A.f[i+1];
  37.     }
  38.     Polynomial F_even = FFT(A_even, m/2, w*w);    //w^2 is a primitive m/2-th root of unity
  39.     Polynomial F_odd = FFT(A_odd, m/2, w*w);
  40.     Polynomial F(m);
  41.     complex<ld> x(1,0);
  42.     for (int j=0; j < m/2; ++j) {
  43.       F.f[j] = F_even.f[j] + x*F_odd.f[j];
  44.       F.f[j+m/2] = F_even.f[j] - x*F_odd.f[j];
  45.       x = x * w;
  46.     }
  47.     return F;
  48. }
  49. int main() {
  50.     Polynomial A(M/2), B(M/2);
  51.     // enter polynomial A and B both with M/2 degree
  52.     enterPolynomial_A;
  53.     enterPolynomial_B;
  54.     complex<ld> w = getPrimitiveRootOfUnity(M);
  55.     Polynomial F_A = FFT(A, M, w);
  56.     Polynomial F_B = FFT(B, M, w);
  57.     Polynomial F_C(M);
  58.     for(int i = 0; i < M; i++) F_C.f[i] = F_A.f[i] * F_B.f[i];
  59.     // w_ = w^{-1}
  60.     complex<ld> w_(1,0);
  61.     for(int i = 0; i < M-1; i++) w_ *= w;
  62.     // 2 last statement to compute result polynomial, result going to be located in C
  63.     Polynomial C = FFT(F_C, M, w_);
  64.     for(int i = 0; i < M; i++) C.f[i] *= (ld)1.0/M;
  65. 	return 0;
  66. }
  67.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp: In function 'int main()':
prog.cpp:52:5: error: 'enterPolynomial_A' was not declared in this scope
     enterPolynomial_A;
     ^
prog.cpp:53:5: error: 'enterPolynomial_B' was not declared in this scope
     enterPolynomial_B;
     ^
stdout 
Standard output is empty
https://ideone.com/jR993P
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!