monarch_butterfly/
lib.rs

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

monarch_butterfly/
lib.rs
