daily pastebin goal
25%
SHARE
TWEET

Untitled

a guest Jan 12th, 2018 49 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. int bitRev(int n, int len) {
  2.     int ans = 0;
  3.     for(int i = 0; i < len; i++) {
  4.         if((n >> i) & 1) {
  5.             ans |= (1 << (len - i - 1));
  6.         }
  7.     }
  8.     return ans;
  9. }
  10.  
  11. void vSort(vcd &a) {
  12.     int d, n = a.sz, len = log(n + .0) / log(2.0);
  13.     for(int i = 0; i < n; i++) {
  14.         d = bitRev(i, len);
  15.         if(d < i) {
  16.             swap(a[d], a[i]);
  17.         }
  18.     }
  19. }
  20.  
  21. void fft(vcd &a, bool inv) {
  22.     int n = a.sz;
  23.     vSort(a);
  24.  
  25.     for(int len = 1; len <= n; len <<= 1) {
  26.         double angle = 2 * PI / len * ((inv) ? -1 : 1);
  27.         vcd precalc(len);
  28.         cd w(1), tmp(cos(angle), sin(angle));
  29.  
  30.         for(int i = 0; i < len; i++) {
  31.             precalc[i] = w;
  32.             w *= tmp;
  33.         }
  34.        
  35.         for(int i = 0; i< n; i += len) {           
  36.             for(int j = 0; j < len/2; j++) {
  37.                 cd u = a[i + j], v = a[i + j +len / 2] * precalc[i + j + len/2];
  38.                 a[i + j] = u + v;
  39.                 a[i + j + len / 2] = u - v;
  40.             }
  41.         }
  42.     }
  43.  
  44.     if(inv) {
  45.         for(int i = 0; i < n; i++) {
  46.             a[i] /= n;
  47.         }
  48.     }
  49. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top