monarch_butterfly/
lib.rs

1#![doc = include_str!("../README.md")]
2
3#![allow(clippy::excessive_precision)]
4#![forbid(unsafe_code)]
5#![no_std]
6
7use num_complex::Complex;
8use num_traits::{Float, FloatConst};
9
10const SQRT_3: f64 = 1.7320508075688772;
11const SQRT_3_DIV_2: f64 = SQRT_3 / 2.0;
12
13monarch_derive::generate_switch!();
14monarch_derive::generate_powers_of_two!();
15monarch_derive::generate_coprimes!();
16monarch_derive::generate_mixed_radix!();
17monarch_derive::generate_primes!();
18monarch_derive::generate_iffts!();
19
20fn _compute_twiddle<T: Float + FloatConst>(index: usize, fft_len: usize) -> Complex<T> {
21    let constant = T::from(-2.0).unwrap() * T::PI() / T::from(fft_len).unwrap();
22    // index * -2PI / fft_len
23    let angle = constant * T::from(index).unwrap();
24
25    Complex::new(angle.cos(), angle.sin())
26}
27
28#[doc = concat!("Inner FFT")]
29#[inline(always)]
30pub fn fft3<T: Float + FloatConst, A: AsRef<[Complex<T>]>>(input: A) -> [Complex<T>; 3] {
31    let n = 3;
32    let x = input.as_ref();
33    assert_eq!(n, x.len());
34
35    let twiddle: Complex<T> = Complex::new(T::from(-0.5).unwrap(), -T::from(SQRT_3_DIV_2).unwrap());
36
37    let xp = x[1] + x[2];
38    let xn = x[1] - x[2];
39    let sum = x[0] + xp;
40
41    let temp_a = x[0]
42        + Complex {
43            re: twiddle.re * xp.re,
44            im: twiddle.re * xp.im,
45        };
46    let temp_b = Complex {
47        re: -twiddle.im * xn.im,
48        im: twiddle.im * xn.re,
49    };
50
51    [sum, temp_a + temp_b, temp_a - temp_b]
52}
53
54#[doc = concat!("Inner FFT")]
55#[inline(always)]
56pub fn fft9<T: Float + FloatConst, A: AsRef<[Complex<T>]>>(input: A) -> [Complex<T>; 9] {
57    let n = 9;
58    let x = input.as_ref();
59    assert_eq!(n, x.len());
60
61    let twiddle1: Complex<T> = Complex::new(
62        T::from(0.76604444311897801).unwrap(),
63        T::from(-0.64278760968653925).unwrap(),
64    );
65    let twiddle2: Complex<T> = Complex::new(
66        T::from(0.17364817766693041).unwrap(),
67        T::from(-0.98480775301220802).unwrap(),
68    );
69    let twiddle4: Complex<T> = Complex::new(
70        T::from(-0.93969262078590832).unwrap(),
71        T::from(-0.34202014332566888).unwrap(),
72    );
73
74    let first = fft3([x[0], x[3], x[6]]);
75    let second = fft3([x[1], x[4], x[7]]);
76    let third = fft3([x[2], x[5], x[8]]);
77
78    let row0 = fft3([first[0], second[0], third[0]]);
79    let row1 = fft3([first[1], second[1] * twiddle1, third[1] * twiddle2]);
80    let row2 = fft3([first[2], second[2] * twiddle2, third[2] * twiddle4]);
81
82    [
83        row0[0], row1[0], row2[0], row0[1], row1[1], row2[1], row0[2], row1[2], row2[2],
84    ]
85}
86
87#[doc = concat!("Inner FFT")]
88#[inline(always)]
89pub fn fft18<T: Float + FloatConst, A: AsRef<[Complex<T>]>>(input: A) -> [Complex<T>; 18] {
90    let n = 18;
91    let x = input.as_ref();
92    assert_eq!(n, x.len());
93
94    let twiddle0 = Complex::new(T::from(1.0).unwrap(), T::from(0.0).unwrap());
95    let twiddle1 = Complex::new(T::from(1.0).unwrap(), T::from(0.0).unwrap());
96    let twiddle2 = Complex::new(T::from(1.0).unwrap(), T::from(0.0).unwrap());
97    let twiddle3 = Complex::new(T::from(1.0).unwrap(), T::from(0.0).unwrap());
98    let twiddle4 = Complex::new(T::from(1.0).unwrap(), T::from(0.0).unwrap());
99    let twiddle5 = Complex::new(T::from(1.0).unwrap(), T::from(0.0).unwrap());
100    let twiddle6 = Complex::new(T::from(1.0).unwrap(), T::from(0.0).unwrap());
101    let twiddle7 = Complex::new(
102        T::from(0.93969262078590842).unwrap(),
103        T::from(-0.34202014332566871).unwrap(),
104    );
105    let twiddle8 = Complex::new(
106        T::from(0.76604444311897801).unwrap(),
107        T::from(-0.64278760968653925).unwrap(),
108    );
109    let twiddle9 = Complex::new(T::from(0.5).unwrap(), T::from(-0.8660254037844386).unwrap());
110    let twiddle10 = Complex::new(
111        T::from(0.17364817766693041).unwrap(),
112        T::from(-0.98480775301220802).unwrap(),
113    );
114    let twiddle11 = Complex::new(
115        T::from(-0.1736481776669303).unwrap(),
116        T::from(-0.98480775301220802).unwrap(),
117    );
118    let twiddle12 = Complex::new(T::from(1.0).unwrap(), T::from(0.0).unwrap());
119    let twiddle13 = Complex::new(
120        T::from(0.76604444311897801).unwrap(),
121        T::from(-0.64278760968653925).unwrap(),
122    );
123    let twiddle14 = Complex::new(
124        T::from(0.17364817766693041).unwrap(),
125        T::from(-0.98480775301220802).unwrap(),
126    );
127    let twiddle15 = Complex::new(
128        T::from(-0.5).unwrap(),
129        T::from(-0.86602540378443881).unwrap(),
130    );
131    let twiddle16 = Complex::new(
132        T::from(-0.93969262078590832).unwrap(),
133        T::from(-0.34202014332566888).unwrap(),
134    );
135    let twiddle17 = Complex::new(
136        T::from(-0.93969262078590842).unwrap(),
137        T::from(0.34202014332566866).unwrap(),
138    );
139
140    let row0 = fft6([x[0], x[3], x[6], x[9], x[12], x[15]]);
141    let row1 = fft6([x[1], x[4], x[7], x[10], x[13], x[16]]);
142    let row2 = fft6([x[2], x[5], x[8], x[11], x[14], x[17]]);
143
144    let col0 = fft3([row0[0] * twiddle0, row1[0] * twiddle6, row2[0] * twiddle12]);
145    let col1 = fft3([row0[1] * twiddle1, row1[1] * twiddle7, row2[1] * twiddle13]);
146    let col2 = fft3([row0[2] * twiddle2, row1[2] * twiddle8, row2[2] * twiddle14]);
147    let col3 = fft3([row0[3] * twiddle3, row1[3] * twiddle9, row2[3] * twiddle15]);
148    let col4 = fft3([row0[4] * twiddle4, row1[4] * twiddle10, row2[4] * twiddle16]);
149    let col5 = fft3([row0[5] * twiddle5, row1[5] * twiddle11, row2[5] * twiddle17]);
150
151    [
152        col0[0], col1[0], col2[0], col3[0], col4[0], col5[0], col0[1], col1[1], col2[1], col3[1],
153        col4[1], col5[1], col0[2], col1[2], col2[2], col3[2], col4[2], col5[2],
154    ]
155}
156
157#[doc = concat!("Inner FFT")]
158#[inline(always)]
159pub fn fft27<T: Float + FloatConst, A: AsRef<[Complex<T>]>>(input: A) -> [Complex<T>; 27] {
160    let n = 27;
161    let x = input.as_ref();
162    assert_eq!(n, x.len());
163
164    let row0 = fft9([x[0], x[3], x[6], x[9], x[12], x[15], x[18], x[21], x[24]]);
165    let row1 = fft9([x[1], x[4], x[7], x[10], x[13], x[16], x[19], x[22], x[25]]);
166    let row2 = fft9([x[2], x[5], x[8], x[11], x[14], x[17], x[20], x[23], x[26]]);
167
168    let twiddle0 = Complex::new(
169        T::from(0.97304487057982381).unwrap(),
170        T::from(-0.23061587074244017).unwrap(),
171    );
172    let twiddle1 = Complex::new(
173        T::from(0.89363264032341228).unwrap(),
174        T::from(-0.44879918020046217).unwrap(),
175    );
176    let twiddle2 = Complex::new(
177        T::from(0.76604444311897801).unwrap(),
178        T::from(-0.64278760968653925).unwrap(),
179    );
180    let twiddle3 = Complex::new(
181        T::from(0.59715859170278618).unwrap(),
182        T::from(-0.80212319275504373).unwrap(),
183    );
184    let twiddle4 = Complex::new(
185        T::from(0.3960797660391569).unwrap(),
186        T::from(-0.918216106880274).unwrap(),
187    );
188    let twiddle5 = Complex::new(
189        T::from(0.17364817766693041).unwrap(),
190        T::from(-0.98480775301220802).unwrap(),
191    );
192    let twiddle6 = Complex::new(
193        T::from(-0.058144828910475774).unwrap(),
194        T::from(-0.99830815827126817).unwrap(),
195    );
196    let twiddle7 = Complex::new(
197        T::from(-0.28680323271109021).unwrap(),
198        T::from(-0.9579895123154889).unwrap(),
199    );
200    let twiddle8 = Complex::new(
201        T::from(-0.68624163786873338).unwrap(),
202        T::from(-0.72737364157304896).unwrap(),
203    );
204    let twiddle9 = Complex::new(
205        T::from(-0.93969262078590832).unwrap(),
206        T::from(-0.34202014332566888).unwrap(),
207    );
208    let twiddle10 = Complex::new(
209        T::from(-0.99323835774194302).unwrap(),
210        T::from(0.11609291412523012).unwrap(),
211    );
212    let twiddle11 = Complex::new(
213        T::from(-0.83548781141293649).unwrap(),
214        T::from(0.54950897807080601).unwrap(),
215    );
216
217    let col0 = fft3([row0[0], row1[0], row2[0]]);
218    let col1 = fft3([row0[1], row1[1] * twiddle0, row2[1] * twiddle1]);
219    let col2 = fft3([row0[2], row1[2] * twiddle1, row2[2] * twiddle3]);
220    let col3 = fft3([row0[3], row1[3] * twiddle2, row2[3] * twiddle5]);
221    let col4 = fft3([row0[4], row1[4] * twiddle3, row2[4] * twiddle7]);
222    let col5 = fft3([row0[5], row1[5] * twiddle4, row2[5] * twiddle8]);
223    let col6 = fft3([row0[6], row1[6] * twiddle5, row2[6] * twiddle9]);
224    let col7 = fft3([row0[7], row1[7] * twiddle6, row2[7] * twiddle10]);
225    let col8 = fft3([row0[8], row1[8] * twiddle7, row2[8] * twiddle11]);
226
227    [
228        col0[0], col1[0], col2[0], col3[0], col4[0], col5[0], col6[0], col7[0], col8[0], col0[1],
229        col1[1], col2[1], col3[1], col4[1], col5[1], col6[1], col7[1], col8[1], col0[2], col1[2],
230        col2[2], col3[2], col4[2], col5[2], col6[2], col7[2], col8[2],
231    ]
232}
233
234#[doc = concat!("Inner FFT")]
235#[inline(always)]
236pub fn fft125<T: Float + FloatConst, A: AsRef<[Complex<T>]>>(input: A) -> [Complex<T>; 125] {
237    let n = 125;
238    let x = input.as_ref();
239    assert_eq!(n, x.len());
240
241    let twiddle0 = Complex::new(T::from(1).unwrap(), T::from(-0).unwrap());
242    let twiddle1 = Complex::new(T::from(1).unwrap(), T::from(-0).unwrap());
243    let twiddle2 = Complex::new(T::from(1).unwrap(), T::from(-0).unwrap());
244    let twiddle3 = Complex::new(T::from(1).unwrap(), T::from(-0).unwrap());
245    let twiddle4 = Complex::new(
246        T::from(0.9685831611286311).unwrap(),
247        T::from(-0.2486898871648548).unwrap(),
248    );
249    let twiddle5 = Complex::new(
250        T::from(0.8763066800438636).unwrap(),
251        T::from(-0.4817536741017153).unwrap(),
252    );
253    let twiddle6 = Complex::new(
254        T::from(0.7289686274214116).unwrap(),
255        T::from(-0.6845471059286887).unwrap(),
256    );
257    let twiddle7 = Complex::new(
258        T::from(0.5358267949789965).unwrap(),
259        T::from(-0.8443279255020151).unwrap(),
260    );
261    let twiddle8 = Complex::new(
262        T::from(0.8763066800438636).unwrap(),
263        T::from(-0.4817536741017153).unwrap(),
264    );
265    let twiddle9 = Complex::new(
266        T::from(0.5358267949789965).unwrap(),
267        T::from(-0.8443279255020151).unwrap(),
268    );
269    let twiddle10 = Complex::new(
270        T::from(0.0627905195293133).unwrap(),
271        T::from(-0.9980267284282716).unwrap(),
272    );
273    let twiddle11 = Complex::new(
274        T::from(-0.4257792915650727).unwrap(),
275        T::from(-0.9048270524660195).unwrap(),
276    );
277    let twiddle12 = Complex::new(
278        T::from(0.7289686274214116).unwrap(),
279        T::from(-0.6845471059286887).unwrap(),
280    );
281    let twiddle13 = Complex::new(
282        T::from(0.0627905195293133).unwrap(),
283        T::from(-0.9980267284282716).unwrap(),
284    );
285    let twiddle14 = Complex::new(
286        T::from(-0.6374239897486897).unwrap(),
287        T::from(-0.7705132427757893).unwrap(),
288    );
289    let twiddle15 = Complex::new(
290        T::from(-0.9921147013144779).unwrap(),
291        T::from(-0.1253332335643041).unwrap(),
292    );
293    let twiddle16 = Complex::new(
294        T::from(0.5358267949789965).unwrap(),
295        T::from(-0.8443279255020151).unwrap(),
296    );
297    let twiddle17 = Complex::new(
298        T::from(-0.4257792915650727).unwrap(),
299        T::from(-0.9048270524660195).unwrap(),
300    );
301    let twiddle18 = Complex::new(
302        T::from(-0.9921147013144779).unwrap(),
303        T::from(-0.1253332335643041).unwrap(),
304    );
305    let twiddle19 = Complex::new(
306        T::from(-0.6374239897486895).unwrap(),
307        T::from(0.7705132427757894).unwrap(),
308    );
309    let twiddle20 = Complex::new(T::from(1).unwrap(), T::from(-0).unwrap());
310    let twiddle21 = Complex::new(T::from(1).unwrap(), T::from(-0).unwrap());
311    let twiddle22 = Complex::new(T::from(1).unwrap(), T::from(-0).unwrap());
312    let twiddle23 = Complex::new(T::from(1).unwrap(), T::from(-0).unwrap());
313    let twiddle24 = Complex::new(
314        T::from(0.9987369566060175).unwrap(),
315        T::from(-0.050244318179769556).unwrap(),
316    );
317    let twiddle25 = Complex::new(
318        T::from(0.9949510169813002).unwrap(),
319        T::from(-0.1003617148512149).unwrap(),
320    );
321    let twiddle26 = Complex::new(
322        T::from(0.9886517447379141).unwrap(),
323        T::from(-0.15022558912075706).unwrap(),
324    );
325    let twiddle27 = Complex::new(
326        T::from(0.9798550523842469).unwrap(),
327        T::from(-0.19970998051440703).unwrap(),
328    );
329    let twiddle28 = Complex::new(
330        T::from(0.9949510169813002).unwrap(),
331        T::from(-0.1003617148512149).unwrap(),
332    );
333    let twiddle29 = Complex::new(
334        T::from(0.9798550523842469).unwrap(),
335        T::from(-0.19970998051440703).unwrap(),
336    );
337    let twiddle30 = Complex::new(
338        T::from(0.954864544746643).unwrap(),
339        T::from(-0.2970415815770349).unwrap(),
340    );
341    let twiddle31 = Complex::new(
342        T::from(0.9202318473658704).unwrap(),
343        T::from(-0.3913736668372024).unwrap(),
344    );
345    let twiddle32 = Complex::new(
346        T::from(0.9886517447379141).unwrap(),
347        T::from(-0.15022558912075706).unwrap(),
348    );
349    let twiddle33 = Complex::new(
350        T::from(0.954864544746643).unwrap(),
351        T::from(-0.2970415815770349).unwrap(),
352    );
353    let twiddle34 = Complex::new(
354        T::from(0.8994052515663711).unwrap(),
355        T::from(-0.4371157666509329).unwrap(),
356    );
357    let twiddle35 = Complex::new(
358        T::from(0.8235325976284275).unwrap(),
359        T::from(-0.5672689491267565).unwrap(),
360    );
361    let twiddle36 = Complex::new(
362        T::from(0.9798550523842469).unwrap(),
363        T::from(-0.19970998051440703).unwrap(),
364    );
365    let twiddle37 = Complex::new(
366        T::from(0.9202318473658704).unwrap(),
367        T::from(-0.3913736668372024).unwrap(),
368    );
369    let twiddle38 = Complex::new(
370        T::from(0.8235325976284275).unwrap(),
371        T::from(-0.5672689491267565).unwrap(),
372    );
373    let twiddle39 = Complex::new(
374        T::from(0.6936533058128049).unwrap(),
375        T::from(-0.7203090248879068).unwrap(),
376    );
377    let twiddle40 = Complex::new(
378        T::from(0.9685831611286311).unwrap(),
379        T::from(-0.2486898871648548).unwrap(),
380    );
381    let twiddle41 = Complex::new(
382        T::from(0.8763066800438636).unwrap(),
383        T::from(-0.4817536741017153).unwrap(),
384    );
385    let twiddle42 = Complex::new(
386        T::from(0.7289686274214116).unwrap(),
387        T::from(-0.6845471059286887).unwrap(),
388    );
389    let twiddle43 = Complex::new(
390        T::from(0.5358267949789965).unwrap(),
391        T::from(-0.8443279255020151).unwrap(),
392    );
393    let twiddle44 = Complex::new(
394        T::from(0.954864544746643).unwrap(),
395        T::from(-0.2970415815770349).unwrap(),
396    );
397    let twiddle45 = Complex::new(
398        T::from(0.8235325976284275).unwrap(),
399        T::from(-0.5672689491267565).unwrap(),
400    );
401    let twiddle46 = Complex::new(
402        T::from(0.6178596130903343).unwrap(),
403        T::from(-0.7862884321366189).unwrap(),
404    );
405    let twiddle47 = Complex::new(
406        T::from(0.35641187871325075).unwrap(),
407        T::from(-0.934328942456612).unwrap(),
408    );
409    let twiddle48 = Complex::new(
410        T::from(0.9387338576538741).unwrap(),
411        T::from(-0.34464292317451706).unwrap(),
412    );
413    let twiddle49 = Complex::new(
414        T::from(0.7624425110114479).unwrap(),
415        T::from(-0.6470559615694443).unwrap(),
416    );
417    let twiddle50 = Complex::new(
418        T::from(0.49272734154829156).unwrap(),
419        T::from(-0.8701837546695257).unwrap(),
420    );
421    let twiddle51 = Complex::new(
422        T::from(0.1626371651948835).unwrap(),
423        T::from(-0.986685944207868).unwrap(),
424    );
425    let twiddle52 = Complex::new(
426        T::from(0.9202318473658704).unwrap(),
427        T::from(-0.3913736668372024).unwrap(),
428    );
429    let twiddle53 = Complex::new(
430        T::from(0.6936533058128049).unwrap(),
431        T::from(-0.7203090248879068).unwrap(),
432    );
433    let twiddle54 = Complex::new(
434        T::from(0.35641187871325075).unwrap(),
435        T::from(-0.934328942456612).unwrap(),
436    );
437    let twiddle55 = Complex::new(
438        T::from(-0.037690182669934576).unwrap(),
439        T::from(-0.9992894726405892).unwrap(),
440    );
441    let twiddle56 = Complex::new(
442        T::from(0.8994052515663711).unwrap(),
443        T::from(-0.4371157666509329).unwrap(),
444    );
445    let twiddle57 = Complex::new(
446        T::from(0.6178596130903343).unwrap(),
447        T::from(-0.7862884321366189).unwrap(),
448    );
449    let twiddle58 = Complex::new(
450        T::from(0.21200710992205452).unwrap(),
451        T::from(-0.9772681235681935).unwrap(),
452    );
453    let twiddle59 = Complex::new(
454        T::from(-0.23649899702372465).unwrap(),
455        T::from(-0.971631732914674).unwrap(),
456    );
457    let twiddle60 = Complex::new(
458        T::from(0.8763066800438636).unwrap(),
459        T::from(-0.4817536741017153).unwrap(),
460    );
461    let twiddle61 = Complex::new(
462        T::from(0.5358267949789965).unwrap(),
463        T::from(-0.8443279255020151).unwrap(),
464    );
465    let twiddle62 = Complex::new(
466        T::from(0.0627905195293133).unwrap(),
467        T::from(-0.9980267284282716).unwrap(),
468    );
469    let twiddle63 = Complex::new(
470        T::from(-0.4257792915650727).unwrap(),
471        T::from(-0.9048270524660195).unwrap(),
472    );
473    let twiddle64 = Complex::new(
474        T::from(0.8509944817946918).unwrap(),
475        T::from(-0.5251746299612957).unwrap(),
476    );
477    let twiddle65 = Complex::new(
478        T::from(0.44838321609003223).unwrap(),
479        T::from(-0.8938414241512638).unwrap(),
480    );
481    let twiddle66 = Complex::new(
482        T::from(-0.0878511965507432).unwrap(),
483        T::from(-0.9961336091431725).unwrap(),
484    );
485    let twiddle67 = Complex::new(
486        T::from(-0.5979049830575189).unwrap(),
487        T::from(-0.8015669848708765).unwrap(),
488    );
489    let twiddle68 = Complex::new(
490        T::from(0.8235325976284275).unwrap(),
491        T::from(-0.5672689491267565).unwrap(),
492    );
493    let twiddle69 = Complex::new(
494        T::from(0.35641187871325075).unwrap(),
495        T::from(-0.934328942456612).unwrap(),
496    );
497    let twiddle70 = Complex::new(
498        T::from(-0.23649899702372465).unwrap(),
499        T::from(-0.971631732914674).unwrap(),
500    );
501    let twiddle71 = Complex::new(
502        T::from(-0.7459411454241821).unwrap(),
503        T::from(-0.6660118674342517).unwrap(),
504    );
505    let twiddle72 = Complex::new(
506        T::from(0.7939903986478354).unwrap(),
507        T::from(-0.6079302976946054).unwrap(),
508    );
509    let twiddle73 = Complex::new(
510        T::from(0.260841506289897).unwrap(),
511        T::from(-0.9653816388332739).unwrap(),
512    );
513    let twiddle74 = Complex::new(
514        T::from(-0.3797790955218012).unwrap(),
515        T::from(-0.925077206834458).unwrap(),
516    );
517    let twiddle75 = Complex::new(
518        T::from(-0.8639234171928353).unwrap(),
519        T::from(-0.5036232016357609).unwrap(),
520    );
521    let twiddle76 = Complex::new(
522        T::from(0.7624425110114479).unwrap(),
523        T::from(-0.6470559615694443).unwrap(),
524    );
525    let twiddle77 = Complex::new(
526        T::from(0.1626371651948835).unwrap(),
527        T::from(-0.986685944207868).unwrap(),
528    );
529    let twiddle78 = Complex::new(
530        T::from(-0.5144395337815065).unwrap(),
531        T::from(-0.8575266561936522).unwrap(),
532    );
533    let twiddle79 = Complex::new(
534        T::from(-0.9470983049947443).unwrap(),
535        T::from(-0.32094360980720926).unwrap(),
536    );
537    let twiddle80 = Complex::new(
538        T::from(0.7289686274214116).unwrap(),
539        T::from(-0.6845471059286887).unwrap(),
540    );
541    let twiddle81 = Complex::new(
542        T::from(0.0627905195293133).unwrap(),
543        T::from(-0.9980267284282716).unwrap(),
544    );
545    let twiddle82 = Complex::new(
546        T::from(-0.6374239897486897).unwrap(),
547        T::from(-0.7705132427757893).unwrap(),
548    );
549    let twiddle83 = Complex::new(
550        T::from(-0.9921147013144779).unwrap(),
551        T::from(-0.1253332335643041).unwrap(),
552    );
553    let twiddle84 = Complex::new(
554        T::from(0.6936533058128049).unwrap(),
555        T::from(-0.7203090248879068).unwrap(),
556    );
557    let twiddle85 = Complex::new(
558        T::from(-0.037690182669934576).unwrap(),
559        T::from(-0.9992894726405892).unwrap(),
560    );
561    let twiddle86 = Complex::new(
562        T::from(-0.7459411454241821).unwrap(),
563        T::from(-0.6660118674342517).unwrap(),
564    );
565    let twiddle87 = Complex::new(
566        T::from(-0.9971589002606139).unwrap(),
567        T::from(0.07532680552793279).unwrap(),
568    );
569    let twiddle88 = Complex::new(
570        T::from(0.6565857557529564).unwrap(),
571        T::from(-0.7542513807361038).unwrap(),
572    );
573    let twiddle89 = Complex::new(
574        T::from(-0.13779029068463805).unwrap(),
575        T::from(-0.9904614256966512).unwrap(),
576    );
577    let twiddle90 = Complex::new(
578        T::from(-0.8375280400421417).unwrap(),
579        T::from(-0.5463943467342692).unwrap(),
580    );
581    let twiddle91 = Complex::new(
582        T::from(-0.9620276715860859).unwrap(),
583        T::from(0.2729519355173252).unwrap(),
584    );
585    let twiddle92 = Complex::new(
586        T::from(0.6178596130903343).unwrap(),
587        T::from(-0.7862884321366189).unwrap(),
588    );
589    let twiddle93 = Complex::new(
590        T::from(-0.23649899702372465).unwrap(),
591        T::from(-0.971631732914674).unwrap(),
592    );
593    let twiddle94 = Complex::new(
594        T::from(-0.9101059706849958).unwrap(),
595        T::from(-0.4143755809932839).unwrap(),
596    );
597    let twiddle95 = Complex::new(
598        T::from(-0.8881364488135446).unwrap(),
599        T::from(0.45957986062148776).unwrap(),
600    );
601    let twiddle96 = Complex::new(
602        T::from(0.5775727034222675).unwrap(),
603        T::from(-0.816339250717184).unwrap(),
604    );
605    let twiddle97 = Complex::new(
606        T::from(-0.3328195445229868).unwrap(),
607        T::from(-0.9429905358928644).unwrap(),
608    );
609    let twiddle98 = Complex::new(
610        T::from(-0.9620276715860859).unwrap(),
611        T::from(-0.27295193551732505).unwrap(),
612    );
613    let twiddle99 = Complex::new(
614        T::from(-0.7784623015670232).unwrap(),
615        T::from(0.6276913612907007).unwrap(),
616    );
617    let twiddle100 = Complex::new(
618        T::from(0.5358267949789965).unwrap(),
619        T::from(-0.8443279255020151).unwrap(),
620    );
621    let twiddle101 = Complex::new(
622        T::from(-0.4257792915650727).unwrap(),
623        T::from(-0.9048270524660195).unwrap(),
624    );
625    let twiddle102 = Complex::new(
626        T::from(-0.9921147013144779).unwrap(),
627        T::from(-0.1253332335643041).unwrap(),
628    );
629    let twiddle103 = Complex::new(
630        T::from(-0.6374239897486895).unwrap(),
631        T::from(0.7705132427757894).unwrap(),
632    );
633    let twiddle104 = Complex::new(
634        T::from(0.49272734154829156).unwrap(),
635        T::from(-0.8701837546695257).unwrap(),
636    );
637    let twiddle105 = Complex::new(
638        T::from(-0.5144395337815065).unwrap(),
639        T::from(-0.8575266561936522).unwrap(),
640    );
641    let twiddle106 = Complex::new(
642        T::from(-0.9996841892832999).unwrap(),
643        T::from(0.02513009544333757).unwrap(),
644    );
645    let twiddle107 = Complex::new(
646        T::from(-0.47070393216533246).unwrap(),
647        T::from(0.8822912264349533).unwrap(),
648    );
649    let twiddle108 = Complex::new(
650        T::from(0.44838321609003223).unwrap(),
651        T::from(-0.8938414241512638).unwrap(),
652    );
653    let twiddle109 = Complex::new(
654        T::from(-0.5979049830575189).unwrap(),
655        T::from(-0.8015669848708765).unwrap(),
656    );
657    let twiddle110 = Complex::new(
658        T::from(-0.9845643345292053).unwrap(),
659        T::from(0.1750230589752761).unwrap(),
660    );
661    let twiddle111 = Complex::new(
662        T::from(-0.2850192624699761).unwrap(),
663        T::from(0.958521789017376).unwrap(),
664    );
665    let twiddle112 = Complex::new(
666        T::from(0.4029064357136627).unwrap(),
667        T::from(-0.9152411726209175).unwrap(),
668    );
669    let twiddle113 = Complex::new(
670        T::from(-0.6753328081210245).unwrap(),
671        T::from(-0.7375131173581739).unwrap(),
672    );
673    let twiddle114 = Complex::new(
674        T::from(-0.9470983049947443).unwrap(),
675        T::from(0.3209436098072095).unwrap(),
676    );
677    let twiddle115 = Complex::new(
678        T::from(-0.08785119655074321).unwrap(),
679        T::from(0.9961336091431725).unwrap(),
680    );
681    let twiddle116 = Complex::new(
682        T::from(0.35641187871325075).unwrap(),
683        T::from(-0.934328942456612).unwrap(),
684    );
685    let twiddle117 = Complex::new(
686        T::from(-0.7459411454241821).unwrap(),
687        T::from(-0.6660118674342517).unwrap(),
688    );
689    let twiddle118 = Complex::new(
690        T::from(-0.8881364488135446).unwrap(),
691        T::from(0.45957986062148776).unwrap(),
692    );
693    let twiddle119 = Complex::new(
694        T::from(0.11285638487348157).unwrap(),
695        T::from(0.9936113105200084).unwrap(),
696    );
697
698    let row0 = fft5([x[0], x[25], x[50], x[75], x[100]]);
699    let row1 = fft5([x[5], x[30], x[55], x[80], x[105]]);
700    let row2 = fft5([x[10], x[35], x[60], x[85], x[110]]);
701    let row3 = fft5([x[15], x[40], x[65], x[90], x[115]]);
702    let row4 = fft5([x[20], x[45], x[70], x[95], x[120]]);
703    let row5 = fft5([x[1], x[26], x[51], x[76], x[101]]);
704    let row6 = fft5([x[6], x[31], x[56], x[81], x[106]]);
705    let row7 = fft5([x[11], x[36], x[61], x[86], x[111]]);
706    let row8 = fft5([x[16], x[41], x[66], x[91], x[116]]);
707    let row9 = fft5([x[21], x[46], x[71], x[96], x[121]]);
708
709    let row10 = fft5([x[2], x[2 + 25], x[2 + 50], x[2 + 75], x[2 + 100]]);
710    let row11 = fft5([x[2 + 5], x[2 + 30], x[2 + 55], x[2 + 80], x[2 + 105]]);
711    let row12 = fft5([x[2 + 10], x[2 + 35], x[2 + 60], x[2 + 85], x[2 + 110]]);
712    let row13 = fft5([x[2 + 15], x[2 + 40], x[2 + 65], x[2 + 90], x[2 + 115]]);
713    let row14 = fft5([x[2 + 20], x[2 + 45], x[2 + 70], x[2 + 95], x[2 + 120]]);
714    let row15 = fft5([x[2 + 1], x[2 + 26], x[2 + 51], x[2 + 76], x[2 + 101]]);
715    let row16 = fft5([x[2 + 6], x[2 + 31], x[2 + 56], x[2 + 81], x[2 + 106]]);
716    let row17 = fft5([x[2 + 11], x[2 + 36], x[2 + 61], x[2 + 86], x[2 + 111]]);
717    let row18 = fft5([x[2 + 16], x[2 + 41], x[2 + 66], x[2 + 91], x[2 + 116]]);
718    let row19 = fft5([x[2 + 21], x[2 + 46], x[2 + 71], x[2 + 96], x[2 + 121]]);
719
720    let row20 = fft5([x[4], x[4 + 25], x[4 + 50], x[4 + 75], x[4 + 100]]);
721    let row21 = fft5([x[4 + 5], x[4 + 30], x[4 + 55], x[4 + 80], x[4 + 105]]);
722    let row22 = fft5([x[4 + 10], x[4 + 35], x[4 + 60], x[4 + 85], x[4 + 110]]);
723    let row23 = fft5([x[4 + 15], x[4 + 40], x[4 + 65], x[4 + 90], x[4 + 115]]);
724    let row24 = fft5([x[4 + 20], x[4 + 45], x[4 + 70], x[4 + 95], x[4 + 120]]);
725
726    let col0 = fft5([
727        row0[0],
728        row1[0] * twiddle0,
729        row2[0] * twiddle1,
730        row3[0] * twiddle2,
731        row4[0] * twiddle3,
732    ]);
733    let col1 = fft5([
734        row0[1],
735        row1[1] * twiddle4,
736        row2[1] * twiddle5,
737        row3[1] * twiddle6,
738        row4[1] * twiddle7,
739    ]);
740    let col2 = fft5([
741        row0[2],
742        row1[2] * twiddle8,
743        row2[2] * twiddle9,
744        row3[2] * twiddle10,
745        row4[2] * twiddle11,
746    ]);
747    let col3 = fft5([
748        row0[3],
749        row1[3] * twiddle12,
750        row2[3] * twiddle13,
751        row3[3] * twiddle14,
752        row4[3] * twiddle15,
753    ]);
754    let col4 = fft5([
755        row0[4],
756        row1[4] * twiddle16,
757        row2[4] * twiddle17,
758        row3[4] * twiddle18,
759        row4[4] * twiddle19,
760    ]);
761
762    let col5 = fft5([
763        row5[0],
764        row6[0] * twiddle0,
765        row7[0] * twiddle1,
766        row8[0] * twiddle2,
767        row9[0] * twiddle3,
768    ]);
769    let col6 = fft5([
770        row5[1],
771        row6[1] * twiddle4,
772        row7[1] * twiddle5,
773        row8[1] * twiddle6,
774        row9[1] * twiddle7,
775    ]);
776    let col7 = fft5([
777        row5[2],
778        row6[2] * twiddle8,
779        row7[2] * twiddle9,
780        row8[2] * twiddle10,
781        row9[2] * twiddle11,
782    ]);
783    let col8 = fft5([
784        row5[3],
785        row6[3] * twiddle12,
786        row7[3] * twiddle13,
787        row8[3] * twiddle14,
788        row9[3] * twiddle15,
789    ]);
790    let col9 = fft5([
791        row5[4],
792        row6[4] * twiddle16,
793        row7[4] * twiddle17,
794        row8[4] * twiddle18,
795        row9[4] * twiddle19,
796    ]);
797
798    let col10 = fft5([
799        row10[0],
800        row11[0] * twiddle0,
801        row12[0] * twiddle1,
802        row13[0] * twiddle2,
803        row14[0] * twiddle3,
804    ]);
805    let col11 = fft5([
806        row10[1],
807        row11[1] * twiddle4,
808        row12[1] * twiddle5,
809        row13[1] * twiddle6,
810        row14[1] * twiddle7,
811    ]);
812    let col12 = fft5([
813        row10[2],
814        row11[2] * twiddle8,
815        row12[2] * twiddle9,
816        row13[2] * twiddle10,
817        row14[2] * twiddle11,
818    ]);
819    let col13 = fft5([
820        row10[3],
821        row11[3] * twiddle12,
822        row12[3] * twiddle13,
823        row13[3] * twiddle14,
824        row14[3] * twiddle15,
825    ]);
826    let col14 = fft5([
827        row10[4],
828        row11[4] * twiddle16,
829        row12[4] * twiddle17,
830        row13[4] * twiddle18,
831        row14[4] * twiddle19,
832    ]);
833
834    let col15 = fft5([
835        row15[0],
836        row16[0] * twiddle0,
837        row17[0] * twiddle1,
838        row18[0] * twiddle2,
839        row19[0] * twiddle3,
840    ]);
841    let col16 = fft5([
842        row15[1],
843        row16[1] * twiddle4,
844        row17[1] * twiddle5,
845        row18[1] * twiddle6,
846        row19[1] * twiddle7,
847    ]);
848    let col17 = fft5([
849        row15[2],
850        row16[2] * twiddle8,
851        row17[2] * twiddle9,
852        row18[2] * twiddle10,
853        row19[2] * twiddle11,
854    ]);
855    let col18 = fft5([
856        row15[3],
857        row16[3] * twiddle12,
858        row17[3] * twiddle13,
859        row18[3] * twiddle14,
860        row19[3] * twiddle15,
861    ]);
862    let col19 = fft5([
863        row15[4],
864        row16[4] * twiddle16,
865        row17[4] * twiddle17,
866        row18[4] * twiddle18,
867        row19[4] * twiddle19,
868    ]);
869
870    let col20 = fft5([
871        row20[0],
872        row21[0] * twiddle0,
873        row22[0] * twiddle1,
874        row23[0] * twiddle2,
875        row24[0] * twiddle3,
876    ]);
877    let col21 = fft5([
878        row20[1],
879        row21[1] * twiddle4,
880        row22[1] * twiddle5,
881        row23[1] * twiddle6,
882        row24[1] * twiddle7,
883    ]);
884    let col22 = fft5([
885        row20[2],
886        row21[2] * twiddle8,
887        row22[2] * twiddle9,
888        row23[2] * twiddle10,
889        row24[2] * twiddle11,
890    ]);
891    let col23 = fft5([
892        row20[3],
893        row21[3] * twiddle12,
894        row22[3] * twiddle13,
895        row23[3] * twiddle14,
896        row24[3] * twiddle15,
897    ]);
898    let col24 = fft5([
899        row20[4],
900        row21[4] * twiddle16,
901        row22[4] * twiddle17,
902        row23[4] * twiddle18,
903        row24[4] * twiddle19,
904    ]);
905
906    let row0 = fft5([
907        col0[0],
908        col5[0] * twiddle20,
909        col10[0] * twiddle21,
910        col15[0] * twiddle22,
911        col20[0] * twiddle23,
912    ]);
913    let row1 = fft5([
914        col1[0],
915        col6[0] * twiddle24,
916        col11[0] * twiddle25,
917        col16[0] * twiddle26,
918        col21[0] * twiddle27,
919    ]);
920    let row2 = fft5([
921        col2[0],
922        col7[0] * twiddle28,
923        col12[0] * twiddle29,
924        col17[0] * twiddle30,
925        col22[0] * twiddle31,
926    ]);
927    let row3 = fft5([
928        col3[0],
929        col8[0] * twiddle32,
930        col13[0] * twiddle33,
931        col18[0] * twiddle34,
932        col23[0] * twiddle35,
933    ]);
934    let row4 = fft5([
935        col4[0],
936        col9[0] * twiddle36,
937        col14[0] * twiddle37,
938        col19[0] * twiddle38,
939        col24[0] * twiddle39,
940    ]);
941
942    let row5 = fft5([
943        col0[1],
944        col5[1] * twiddle40,
945        col10[1] * twiddle41,
946        col15[1] * twiddle42,
947        col20[1] * twiddle43,
948    ]);
949    let row6 = fft5([
950        col1[1],
951        col6[1] * twiddle44,
952        col11[1] * twiddle45,
953        col16[1] * twiddle46,
954        col21[1] * twiddle47,
955    ]);
956    let row7 = fft5([
957        col2[1],
958        col7[1] * twiddle48,
959        col12[1] * twiddle49,
960        col17[1] * twiddle50,
961        col22[1] * twiddle51,
962    ]);
963    let row8 = fft5([
964        col3[1],
965        col8[1] * twiddle52,
966        col13[1] * twiddle53,
967        col18[1] * twiddle54,
968        col23[1] * twiddle55,
969    ]);
970    let row9 = fft5([
971        col4[1],
972        col9[1] * twiddle56,
973        col14[1] * twiddle57,
974        col19[1] * twiddle58,
975        col24[1] * twiddle59,
976    ]);
977
978    let row10 = fft5([
979        col0[2],
980        col5[2] * twiddle60,
981        col10[2] * twiddle61,
982        col15[2] * twiddle62,
983        col20[2] * twiddle63,
984    ]);
985    let row11 = fft5([
986        col1[2],
987        col6[2] * twiddle64,
988        col11[2] * twiddle65,
989        col16[2] * twiddle66,
990        col21[2] * twiddle67,
991    ]);
992    let row12 = fft5([
993        col2[2],
994        col7[2] * twiddle68,
995        col12[2] * twiddle69,
996        col17[2] * twiddle70,
997        col22[2] * twiddle71,
998    ]);
999    let row13 = fft5([
1000        col3[2],
1001        col8[2] * twiddle72,
1002        col13[2] * twiddle73,
1003        col18[2] * twiddle74,
1004        col23[2] * twiddle75,
1005    ]);
1006    let row14 = fft5([
1007        col4[2],
1008        col9[2] * twiddle76,
1009        col14[2] * twiddle77,
1010        col19[2] * twiddle78,
1011        col24[2] * twiddle79,
1012    ]);
1013
1014    let row15 = fft5([
1015        col0[3],
1016        col5[3] * twiddle80,
1017        col10[3] * twiddle81,
1018        col15[3] * twiddle82,
1019        col20[3] * twiddle83,
1020    ]);
1021    let row16 = fft5([
1022        col1[3],
1023        col6[3] * twiddle84,
1024        col11[3] * twiddle85,
1025        col16[3] * twiddle86,
1026        col21[3] * twiddle87,
1027    ]);
1028    let row17 = fft5([
1029        col2[3],
1030        col7[3] * twiddle88,
1031        col12[3] * twiddle89,
1032        col17[3] * twiddle90,
1033        col22[3] * twiddle91,
1034    ]);
1035    let row18 = fft5([
1036        col3[3],
1037        col8[3] * twiddle92,
1038        col13[3] * twiddle93,
1039        col18[3] * twiddle94,
1040        col23[3] * twiddle95,
1041    ]);
1042    let row19 = fft5([
1043        col4[3],
1044        col9[3] * twiddle96,
1045        col14[3] * twiddle97,
1046        col19[3] * twiddle98,
1047        col24[3] * twiddle99,
1048    ]);
1049
1050    let row20 = fft5([
1051        col0[4],
1052        col5[4] * twiddle100,
1053        col10[4] * twiddle101,
1054        col15[4] * twiddle102,
1055        col20[4] * twiddle103,
1056    ]);
1057    let row21 = fft5([
1058        col1[4],
1059        col6[4] * twiddle104,
1060        col11[4] * twiddle105,
1061        col16[4] * twiddle106,
1062        col21[4] * twiddle107,
1063    ]);
1064    let row22 = fft5([
1065        col2[4],
1066        col7[4] * twiddle108,
1067        col12[4] * twiddle109,
1068        col17[4] * twiddle110,
1069        col22[4] * twiddle111,
1070    ]);
1071    let row23 = fft5([
1072        col3[4],
1073        col8[4] * twiddle112,
1074        col13[4] * twiddle113,
1075        col18[4] * twiddle114,
1076        col23[4] * twiddle115,
1077    ]);
1078    let row24 = fft5([
1079        col4[4],
1080        col9[4] * twiddle116,
1081        col14[4] * twiddle117,
1082        col19[4] * twiddle118,
1083        col24[4] * twiddle119,
1084    ]);
1085
1086    [
1087        row0[0], row1[0], row2[0], row3[0], row4[0], row5[0], row6[0], row7[0], row8[0], row9[0],
1088        row10[0], row11[0], row12[0], row13[0], row14[0], row15[0], row16[0], row17[0], row18[0],
1089        row19[0], row20[0], row21[0], row22[0], row23[0], row24[0], row0[1], row1[1], row2[1],
1090        row3[1], row4[1], row5[1], row6[1], row7[1], row8[1], row9[1], row10[1], row11[1],
1091        row12[1], row13[1], row14[1], row15[1], row16[1], row17[1], row18[1], row19[1], row20[1],
1092        row21[1], row22[1], row23[1], row24[1], row0[2], row1[2], row2[2], row3[2], row4[2],
1093        row5[2], row6[2], row7[2], row8[2], row9[2], row10[2], row11[2], row12[2], row13[2],
1094        row14[2], row15[2], row16[2], row17[2], row18[2], row19[2], row20[2], row21[2], row22[2],
1095        row23[2], row24[2], row0[3], row1[3], row2[3], row3[3], row4[3], row5[3], row6[3], row7[3],
1096        row8[3], row9[3], row10[3], row11[3], row12[3], row13[3], row14[3], row15[3], row16[3],
1097        row17[3], row18[3], row19[3], row20[3], row21[3], row22[3], row23[3], row24[3], row0[4],
1098        row1[4], row2[4], row3[4], row4[4], row5[4], row6[4], row7[4], row8[4], row9[4], row10[4],
1099        row11[4], row12[4], row13[4], row14[4], row15[4], row16[4], row17[4], row18[4], row19[4],
1100        row20[4], row21[4], row22[4], row23[4], row24[4],
1101    ]
1102}
1103
1104// #[cfg(test)]
1105// mod tests {
1106//     use num_complex::Complex;
1107
1108//     use crate::fft125;
1109
1110//     #[test]
1111//     fn test_125() {
1112//         let v: Vec<Complex<f64>> = (0..125).map(|i| Complex::new(i as f64, 0.0)).collect();
1113//         let a = fft125(&v);
1114//         dbg!(&a);
1115//     }
1116// }
monarch_butterfly/lib.rs

monarch_butterfly/
lib.rs
