fn bit_reverse<T>(f: &mut [T])Examples found in repository?
crates/competitive/src/math/fast_fourier_transform.rs (line 85)
74 fn transform(t: Self::T, len: usize) -> Self::F {
75 let n = len.max(4).next_power_of_two();
76 let mut f = vec![Complex::zero(); n / 2];
77 for (i, t) in t.into_iter().enumerate() {
78 if i & 1 == 0 {
79 f[i / 2].re = t as f64;
80 } else {
81 f[i / 2].im = t as f64;
82 }
83 }
84 fft(&mut f);
85 bit_reverse(&mut f);
86 f[0] = Complex::new(f[0].re + f[0].im, f[0].re - f[0].im);
87 f[n / 4] = f[n / 4].conjugate();
88 let w = Complex::primitive_nth_root_of_unity(-(n as f64));
89 let mut wk = Complex::<f64>::one();
90 for k in 1..n / 4 {
91 wk *= w;
92 let c = wk.conjugate().transpose() + 1.;
93 let d = c * (f[k] - f[n / 2 - k].conjugate()) * 0.5;
94 f[k] -= d;
95 f[n / 2 - k] += d.conjugate();
96 }
97 f
98 }
99 fn inverse_transform(mut f: Self::F, len: usize) -> Self::T {
100 let n = len.max(4).next_power_of_two();
101 assert_eq!(f.len(), n / 2);
102 f[0] = Complex::new((f[0].re + f[0].im) * 0.5, (f[0].re - f[0].im) * 0.5);
103 f[n / 4] = f[n / 4].conjugate();
104 let w = Complex::primitive_nth_root_of_unity(n as f64);
105 let mut wk = Complex::<f64>::one();
106 for k in 1..n / 4 {
107 wk *= w;
108 let c = wk.transpose().conjugate() + 1.;
109 let d = c * (f[k] - f[n / 2 - k].conjugate()) * 0.5;
110 f[k] -= d;
111 f[n / 2 - k] += d.conjugate();
112 }
113 bit_reverse(&mut f);
114 ifft(&mut f);
115 let inv = 1. / (n / 2) as f64;
116 (0..len)
117 .map(|i| (inv * if i & 1 == 0 { f[i / 2].re } else { f[i / 2].im }).round() as i64)
118 .collect()
119 }