fork(5) download
copy 
  1. #include <algorithm>
  2. #include<iostream>
  3. #include <cstdio>
  4. #include <ctime>
  5. #include <vector>
  6. #include <complex>
  7. using namespace std;
  8. #define cd complex<double>
  9. #define vcd vector<cd>
  10. #define si(n) scanf("%d",&n)
  11. #define f(i,a,b) for(int i=a;i<b;i++)
  12. #define pb push_back
  13.  
  14. vcd fft(const vcd &as) {
  15.   int n = as.size();
  16.   int k = 0;
  17.   while ((1 << k) < n) k++;
  18.   vector<int> rev(n);
  19.   rev[0] = 0;
  20.   int high1 = -1;
  21.   for (int i = 1; i < n; i++) {
  22.     if ((i & (i - 1)) == 0)
  23.       high1++;
  24.     rev[i] = rev[i ^ (1 << high1)];
  25.     rev[i] |= (1 << (k - high1 - 1));
  26.   }
  27.  
  28.   vcd roots(n);
  29.   for (int i = 0; i < n; i++) {
  30.     double alpha = 2 * M_PI * i / n;
  31.     roots[i] = cd(cos(alpha), sin(alpha));
  32.   }
  33.  
  34.   vcd cur(n);
  35.   for (int i = 0; i < n; i++)
  36.     cur[i] = as[rev[i]];
  37.  
  38.   for (int len = 1; len < n; len <<= 1) {
  39.     vcd ncur(n);
  40.     int rstep = roots.size() / (len * 2);
  41.     for (int pdest = 0; pdest < n;) {
  42.       int p1 = pdest;
  43.       for (int i = 0; i < len; i++) {
  44.         cd val = roots[i * rstep] * cur[p1 + len];
  45.         ncur[pdest] = cur[p1] + val;
  46.         ncur[pdest + len] = cur[p1] - val;
  47.         pdest++, p1++;
  48.       }
  49.       pdest += len;
  50.     }
  51.     cur.swap(ncur);
  52.   }
  53.   return cur;
  54. }
  55.  
  56. vcd fft_rev(const vcd &as) {
  57.   vcd res = fft(as);
  58.   for (int i = 0; i < (int)res.size(); i++) res[i] /= as.size();
  59.   reverse(res.begin() + 1, res.end());
  60.   return res;
  61. }
  62. //the coeffeciets of input polynomial are stored in a vector-> vcd
  63. int power(int num,int n)
  64. {
  65.     if(n==1) return num;
  66.     int p= power(num,n/2);
  67.     p= (p*p);
  68.     if(n%2!=0)
  69.     {
  70.         p=(p*num);
  71.     }
  72.     return p;
  73. }
  74.  
  75. int main()
  76. {
  77.     //cout<<ceil(log2(5))<<"\n";
  78.     cout<<"Input the degree of polynomials to be multiplied\n";
  79.     int n,a;
  80.     si(n);
  81.     vcd P,Q;
  82.     cout<<"Enter first polynomial coeffecients\n";
  83.     f(i,0,n+1)
  84.     {
  85.         si(a);
  86.         P.pb(cd(a,0));
  87.     }
  88.     cout<<"Enter second polynomial coeffecients\n";
  89.     f(i,0,n+1)
  90.     {
  91.         si(a);
  92.         P.pb(cd(a,0));
  93.     }
  94.     int t;
  95.     t=n*2;
  96.     int p=ceil(log2(t));
  97.     t=power(2,p);
  98.     f(i,n+1,t+1)
  99.     {
  100.         P.pb(0);
  101.         Q.pb(0);
  102.     }
  103.     vcd P1,Q1;
  104.     P1= fft(P);
  105.     Q1= fft(Q);
  106.     vcd E;
  107.     f(i,0,t+1)
  108.     {
  109.         E.pb(P1[i]*Q1[i]);
  110.     }
  111.     vcd Res;
  112.     Res= fft_rev(E);
  113.     cout<<"the final product coeffeciets are: \n";
  114.     f(i,0,t+1)
  115.     {
  116.         cout<<Res[i]<<" ";
  117.     }
  118.     cout<<"\n";
  119.     return 0;
  120. }
  121.  
Runtime error #stdin #stdout 0.02s 2688KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PFNIKm
language:
C++ (gcc 8.3)
created:
11 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!