falcon-rust 0.2.0

use std::ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign};

use falcon_profiler::profiling;
use itertools::Itertools;
use lazy_static::lazy_static;
use num::{One, Zero};
use num_complex::{Complex, Complex64};

use crate::{
    cyclotomic_fourier::CyclotomicFourier,
    falcon_field::Felt,
    fixed_point::{FixedPoint64, FixedPoint128},
    fp_field::FpField,
    polynomial::Polynomial,
    U32Field,
};

/// Implements Cyclotomic FFT without bitreversing the outputs, and using
/// precomputed powers of the 2nth primitive root of unity.
pub trait FastFft: Sized + Clone {
    type Field: Add + Mul + AddAssign + MulAssign + Neg + Sub + SubAssign + One + Zero;

    fn fft_inplace(&mut self);

    fn fft(&self) -> Self {
        let mut a = self.clone();
        a.fft_inplace();
        a
    }

    fn merge_fft(a: &Self, b: &Self) -> Self;

    fn split_fft(&self) -> (Self, Self);

    fn ifft_inplace(&mut self);

    fn ifft(&self) -> Self {
        let mut a = self.clone();
        a.ifft_inplace();
        a
    }
}

#[allow(clippy::approx_constant)]
const COMPLEX_BITREVERSED_POWERS_1024: [Complex64; 1024] = [
    Complex64::new(1.0, 0.0),
    Complex64::new(0.00000000000000006123233995736766, 1.0),
    Complex64::new(0.7071067811865476, 0.7071067811865475),
    Complex64::new(-0.7071067811865475, 0.7071067811865476),
    Complex64::new(0.9238795325112867, 0.3826834323650898),
    Complex64::new(-0.3826834323650897, 0.9238795325112867),
    Complex64::new(0.38268343236508984, 0.9238795325112867),
    Complex64::new(-0.9238795325112867, 0.3826834323650899),
    Complex64::new(0.9807852804032304, 0.19509032201612825),
    Complex64::new(-0.1950903220161282, 0.9807852804032304),
    Complex64::new(0.5555702330196023, 0.8314696123025452),
    Complex64::new(-0.8314696123025453, 0.5555702330196022),
    Complex64::new(0.8314696123025452, 0.5555702330196022),
    Complex64::new(-0.555570233019602, 0.8314696123025455),
    Complex64::new(0.19509032201612833, 0.9807852804032304),
    Complex64::new(-0.9807852804032304, 0.1950903220161286),
    Complex64::new(0.9951847266721969, 0.0980171403295606),
    Complex64::new(-0.09801714032956065, 0.9951847266721969),
    Complex64::new(0.6343932841636455, 0.773010453362737),
    Complex64::new(-0.773010453362737, 0.6343932841636455),
    Complex64::new(0.881921264348355, 0.47139673682599764),
    Complex64::new(-0.4713967368259977, 0.881921264348355),
    Complex64::new(0.29028467725446233, 0.9569403357322089),
    Complex64::new(-0.9569403357322088, 0.2902846772544624),
    Complex64::new(0.9569403357322088, 0.29028467725446233),
    Complex64::new(-0.29028467725446216, 0.9569403357322089),
    Complex64::new(0.4713967368259978, 0.8819212643483549),
    Complex64::new(-0.8819212643483549, 0.47139673682599786),
    Complex64::new(0.773010453362737, 0.6343932841636455),
    Complex64::new(-0.6343932841636454, 0.7730104533627371),
    Complex64::new(0.09801714032956077, 0.9951847266721968),
    Complex64::new(-0.9951847266721968, 0.09801714032956083),
    Complex64::new(0.9987954562051724, 0.049067674327418015),
    Complex64::new(-0.04906767432741801, 0.9987954562051724),
    Complex64::new(0.6715589548470183, 0.7409511253549591),
    Complex64::new(-0.7409511253549589, 0.6715589548470186),
    Complex64::new(0.9039892931234433, 0.4275550934302821),
    Complex64::new(-0.42755509343028186, 0.9039892931234434),
    Complex64::new(0.33688985339222005, 0.9415440651830208),
    Complex64::new(-0.9415440651830207, 0.33688985339222033),
    Complex64::new(0.970031253194544, 0.24298017990326387),
    Complex64::new(-0.24298017990326387, 0.970031253194544),
    Complex64::new(0.5141027441932217, 0.8577286100002721),
    Complex64::new(-0.857728610000272, 0.5141027441932218),
    Complex64::new(0.8032075314806449, 0.5956993044924334),
    Complex64::new(-0.5956993044924334, 0.8032075314806449),
    Complex64::new(0.14673047445536175, 0.989176509964781),
    Complex64::new(-0.989176509964781, 0.1467304744553618),
    Complex64::new(0.989176509964781, 0.14673047445536175),
    Complex64::new(-0.14673047445536164, 0.989176509964781),
    Complex64::new(0.5956993044924335, 0.8032075314806448),
    Complex64::new(-0.8032075314806448, 0.5956993044924335),
    Complex64::new(0.8577286100002721, 0.5141027441932217),
    Complex64::new(-0.5141027441932217, 0.8577286100002721),
    Complex64::new(0.24298017990326398, 0.970031253194544),
    Complex64::new(-0.970031253194544, 0.24298017990326407),
    Complex64::new(0.9415440651830208, 0.33688985339222005),
    Complex64::new(-0.33688985339221994, 0.9415440651830208),
    Complex64::new(0.4275550934302822, 0.9039892931234433),
    Complex64::new(-0.9039892931234433, 0.42755509343028203),
    Complex64::new(0.7409511253549591, 0.6715589548470183),
    Complex64::new(-0.6715589548470184, 0.740951125354959),
    Complex64::new(0.049067674327418126, 0.9987954562051724),
    Complex64::new(-0.9987954562051724, 0.049067674327417966),
    Complex64::new(0.9996988186962042, 0.024541228522912288),
    Complex64::new(-0.024541228522912142, 0.9996988186962042),
    Complex64::new(0.6895405447370669, 0.7242470829514669),
    Complex64::new(-0.7242470829514668, 0.689540544737067),
    Complex64::new(0.9142097557035307, 0.40524131400498986),
    Complex64::new(-0.40524131400498975, 0.9142097557035307),
    Complex64::new(0.3598950365349883, 0.9329927988347388),
    Complex64::new(-0.9329927988347388, 0.35989503653498833),
    Complex64::new(0.9757021300385286, 0.2191012401568698),
    Complex64::new(-0.21910124015686966, 0.9757021300385286),
    Complex64::new(0.5349976198870973, 0.844853565249707),
    Complex64::new(-0.8448535652497071, 0.5349976198870972),
    Complex64::new(0.8175848131515837, 0.5758081914178453),
    Complex64::new(-0.5758081914178453, 0.8175848131515837),
    Complex64::new(0.17096188876030136, 0.9852776423889412),
    Complex64::new(-0.9852776423889412, 0.17096188876030122),
    Complex64::new(0.99247953459871, 0.1224106751992162),
    Complex64::new(-0.12241067519921615, 0.99247953459871),
    Complex64::new(0.6152315905806268, 0.7883464276266062),
    Complex64::new(-0.7883464276266062, 0.6152315905806269),
    Complex64::new(0.8700869911087115, 0.49289819222978404),
    Complex64::new(-0.492898192229784, 0.8700869911087115),
    Complex64::new(0.2667127574748984, 0.9637760657954398),
    Complex64::new(-0.9637760657954398, 0.2667127574748985),
    Complex64::new(0.9495281805930367, 0.3136817403988915),
    Complex64::new(-0.3136817403988914, 0.9495281805930367),
    Complex64::new(0.4496113296546066, 0.8932243011955153),
    Complex64::new(-0.8932243011955152, 0.4496113296546069),
    Complex64::new(0.7572088465064846, 0.6531728429537768),
    Complex64::new(-0.6531728429537765, 0.7572088465064847),
    Complex64::new(0.07356456359966745, 0.9972904566786902),
    Complex64::new(-0.9972904566786902, 0.07356456359966773),
    Complex64::new(0.9972904566786902, 0.07356456359966743),
    Complex64::new(-0.07356456359966733, 0.9972904566786902),
    Complex64::new(0.6531728429537768, 0.7572088465064845),
    Complex64::new(-0.7572088465064846, 0.6531728429537766),
    Complex64::new(0.8932243011955153, 0.44961132965460654),
    Complex64::new(-0.4496113296546067, 0.8932243011955152),
    Complex64::new(0.3136817403988916, 0.9495281805930367),
    Complex64::new(-0.9495281805930367, 0.3136817403988914),
    Complex64::new(0.9637760657954398, 0.26671275747489837),
    Complex64::new(-0.2667127574748983, 0.9637760657954398),
    Complex64::new(0.4928981922297841, 0.8700869911087113),
    Complex64::new(-0.8700869911087113, 0.49289819222978415),
    Complex64::new(0.7883464276266063, 0.6152315905806268),
    Complex64::new(-0.6152315905806267, 0.7883464276266063),
    Complex64::new(0.12241067519921628, 0.99247953459871),
    Complex64::new(-0.99247953459871, 0.12241067519921635),
    Complex64::new(0.9852776423889412, 0.17096188876030122),
    Complex64::new(-0.17096188876030124, 0.9852776423889412),
    Complex64::new(0.5758081914178453, 0.8175848131515837),
    Complex64::new(-0.8175848131515836, 0.5758081914178454),
    Complex64::new(0.8448535652497071, 0.5349976198870972),
    Complex64::new(-0.534997619887097, 0.8448535652497072),
    Complex64::new(0.21910124015686977, 0.9757021300385286),
    Complex64::new(-0.9757021300385285, 0.21910124015687005),
    Complex64::new(0.932992798834739, 0.3598950365349881),
    Complex64::new(-0.35989503653498817, 0.9329927988347388),
    Complex64::new(0.40524131400498986, 0.9142097557035307),
    Complex64::new(-0.9142097557035307, 0.4052413140049899),
    Complex64::new(0.724247082951467, 0.6895405447370668),
    Complex64::new(-0.6895405447370669, 0.7242470829514669),
    Complex64::new(0.024541228522912264, 0.9996988186962042),
    Complex64::new(-0.9996988186962042, 0.024541228522912326),
    Complex64::new(0.9999247018391445, 0.012271538285719925),
    Complex64::new(-0.012271538285719823, 0.9999247018391445),
    Complex64::new(0.6983762494089729, 0.7157308252838186),
    Complex64::new(-0.7157308252838186, 0.6983762494089729),
    Complex64::new(0.9191138516900578, 0.3939920400610481),
    Complex64::new(-0.393992040061048, 0.9191138516900578),
    Complex64::new(0.3713171939518376, 0.9285060804732155),
    Complex64::new(-0.9285060804732155, 0.3713171939518377),
    Complex64::new(0.9783173707196277, 0.20711137619221856),
    Complex64::new(-0.20711137619221845, 0.9783173707196277),
    Complex64::new(0.5453249884220465, 0.838224705554838),
    Complex64::new(-0.8382247055548381, 0.5453249884220464),
    Complex64::new(0.8245893027850253, 0.5657318107836131),
    Complex64::new(-0.5657318107836132, 0.8245893027850252),
    Complex64::new(0.18303988795514106, 0.9831054874312163),
    Complex64::new(-0.9831054874312163, 0.1830398879551409),
    Complex64::new(0.9939069700023561, 0.11022220729388306),
    Complex64::new(-0.11022220729388306, 0.9939069700023561),
    Complex64::new(0.6248594881423865, 0.7807372285720944),
    Complex64::new(-0.7807372285720945, 0.6248594881423863),
    Complex64::new(0.8760700941954066, 0.4821837720791227),
    Complex64::new(-0.4821837720791227, 0.8760700941954066),
    Complex64::new(0.27851968938505306, 0.9604305194155658),
    Complex64::new(-0.9604305194155658, 0.27851968938505317),
    Complex64::new(0.9533060403541939, 0.3020059493192281),
    Complex64::new(-0.3020059493192281, 0.9533060403541939),
    Complex64::new(0.46053871095824, 0.8876396204028539),
    Complex64::new(-0.8876396204028538, 0.4605387109582402),
    Complex64::new(0.765167265622459, 0.6438315428897914),
    Complex64::new(-0.6438315428897913, 0.7651672656224591),
    Complex64::new(0.08579731234443988, 0.996312612182778),
    Complex64::new(-0.996312612182778, 0.08579731234444016),
    Complex64::new(0.9981181129001492, 0.06132073630220858),
    Complex64::new(-0.06132073630220853, 0.9981181129001492),
    Complex64::new(0.6624157775901718, 0.7491363945234593),
    Complex64::new(-0.7491363945234591, 0.662415777590172),
    Complex64::new(0.8986744656939538, 0.43861623853852766),
    Complex64::new(-0.4386162385385274, 0.8986744656939539),
    Complex64::new(0.325310292162263, 0.9456073253805213),
    Complex64::new(-0.9456073253805212, 0.32531029216226326),
    Complex64::new(0.9669764710448521, 0.25486565960451457),
    Complex64::new(-0.2548656596045145, 0.9669764710448521),
    Complex64::new(0.5035383837257176, 0.8639728561215867),
    Complex64::new(-0.8639728561215867, 0.5035383837257177),
    Complex64::new(0.7958369046088836, 0.6055110414043255),
    Complex64::new(-0.6055110414043254, 0.7958369046088836),
    Complex64::new(0.13458070850712622, 0.99090263542778),
    Complex64::new(-0.99090263542778, 0.13458070850712628),
    Complex64::new(0.9873014181578584, 0.15885814333386145),
    Complex64::new(-0.15885814333386128, 0.9873014181578584),
    Complex64::new(0.5857978574564389, 0.8104571982525948),
    Complex64::new(-0.8104571982525947, 0.585797857456439),
    Complex64::new(0.8513551931052652, 0.524589682678469),
    Complex64::new(-0.5245896826784687, 0.8513551931052652),
    Complex64::new(0.23105810828067128, 0.9729399522055601),
    Complex64::new(-0.9729399522055601, 0.23105810828067133),
    Complex64::new(0.937339011912575, 0.34841868024943456),
    Complex64::new(-0.3484186802494344, 0.937339011912575),
    Complex64::new(0.4164295600976373, 0.9091679830905223),
    Complex64::new(-0.9091679830905224, 0.41642956009763715),
    Complex64::new(0.7326542716724128, 0.680600997795453),
    Complex64::new(-0.680600997795453, 0.7326542716724128),
    Complex64::new(0.03680722294135899, 0.9993223845883495),
    Complex64::new(-0.9993223845883495, 0.03680722294135883),
    Complex64::new(0.9993223845883495, 0.03680722294135883),
    Complex64::new(-0.036807222941358866, 0.9993223845883495),
    Complex64::new(0.6806009977954531, 0.7326542716724128),
    Complex64::new(-0.7326542716724127, 0.6806009977954532),
    Complex64::new(0.9091679830905224, 0.41642956009763715),
    Complex64::new(-0.416429560097637, 0.9091679830905225),
    Complex64::new(0.3484186802494345, 0.937339011912575),
    Complex64::new(-0.9373390119125748, 0.3484186802494348),
    Complex64::new(0.9729399522055602, 0.2310581082806711),
    Complex64::new(-0.23105810828067114, 0.9729399522055602),
    Complex64::new(0.5245896826784688, 0.8513551931052652),
    Complex64::new(-0.8513551931052652, 0.524589682678469),
    Complex64::new(0.8104571982525948, 0.5857978574564389),
    Complex64::new(-0.5857978574564389, 0.8104571982525948),
    Complex64::new(0.1588581433338614, 0.9873014181578584),
    Complex64::new(-0.9873014181578584, 0.15885814333386147),
    Complex64::new(0.99090263542778, 0.13458070850712617),
    Complex64::new(-0.1345807085071261, 0.99090263542778),
    Complex64::new(0.6055110414043255, 0.7958369046088835),
    Complex64::new(-0.7958369046088835, 0.6055110414043257),
    Complex64::new(0.8639728561215868, 0.5035383837257176),
    Complex64::new(-0.5035383837257175, 0.8639728561215868),
    Complex64::new(0.2548656596045146, 0.9669764710448521),
    Complex64::new(-0.9669764710448521, 0.2548656596045147),
    Complex64::new(0.9456073253805213, 0.3253102921622629),
    Complex64::new(-0.32531029216226287, 0.9456073253805214),
    Complex64::new(0.4386162385385277, 0.8986744656939538),
    Complex64::new(-0.8986744656939539, 0.43861623853852755),
    Complex64::new(0.7491363945234594, 0.6624157775901718),
    Complex64::new(-0.6624157775901719, 0.7491363945234593),
    Complex64::new(0.06132073630220865, 0.9981181129001492),
    Complex64::new(-0.9981181129001492, 0.06132073630220849),
    Complex64::new(0.996312612182778, 0.0857973123444399),
    Complex64::new(-0.08579731234443976, 0.996312612182778),
    Complex64::new(0.6438315428897915, 0.765167265622459),
    Complex64::new(-0.765167265622459, 0.6438315428897914),
    Complex64::new(0.8876396204028539, 0.46053871095824),
    Complex64::new(-0.46053871095824006, 0.8876396204028539),
    Complex64::new(0.3020059493192282, 0.9533060403541938),
    Complex64::new(-0.9533060403541939, 0.30200594931922803),
    Complex64::new(0.9604305194155658, 0.27851968938505306),
    Complex64::new(-0.27851968938505295, 0.9604305194155659),
    Complex64::new(0.48218377207912283, 0.8760700941954066),
    Complex64::new(-0.8760700941954065, 0.4821837720791229),
    Complex64::new(0.7807372285720945, 0.6248594881423863),
    Complex64::new(-0.6248594881423862, 0.7807372285720946),
    Complex64::new(0.11022220729388318, 0.9939069700023561),
    Complex64::new(-0.9939069700023561, 0.11022220729388324),
    Complex64::new(0.9831054874312163, 0.18303988795514095),
    Complex64::new(-0.18303988795514092, 0.9831054874312163),
    Complex64::new(0.5657318107836132, 0.8245893027850253),
    Complex64::new(-0.8245893027850251, 0.5657318107836135),
    Complex64::new(0.8382247055548381, 0.5453249884220465),
    Complex64::new(-0.5453249884220462, 0.8382247055548382),
    Complex64::new(0.20711137619221856, 0.9783173707196277),
    Complex64::new(-0.9783173707196275, 0.20711137619221884),
    Complex64::new(0.9285060804732156, 0.37131719395183754),
    Complex64::new(-0.3713171939518375, 0.9285060804732156),
    Complex64::new(0.3939920400610481, 0.9191138516900578),
    Complex64::new(-0.9191138516900578, 0.39399204006104815),
    Complex64::new(0.7157308252838186, 0.6983762494089729),
    Complex64::new(-0.6983762494089728, 0.7157308252838187),
    Complex64::new(0.012271538285719944, 0.9999247018391445),
    Complex64::new(-0.9999247018391445, 0.012271538285720007),
    Complex64::new(0.9999811752826011, 0.006135884649154475),
    Complex64::new(-0.006135884649154393, 0.9999811752826011),
    Complex64::new(0.7027547444572253, 0.7114321957452164),
    Complex64::new(-0.7114321957452165, 0.7027547444572252),
    Complex64::new(0.921514039342042, 0.38834504669882625),
    Complex64::new(-0.3883450466988262, 0.921514039342042),
    Complex64::new(0.3770074102164183, 0.9262102421383113),
    Complex64::new(-0.9262102421383114, 0.37700741021641815),
    Complex64::new(0.9795697656854405, 0.2011046348420919),
    Complex64::new(-0.20110463484209182, 0.9795697656854405),
    Complex64::new(0.5504579729366048, 0.83486287498638),
    Complex64::new(-0.83486287498638, 0.5504579729366049),
    Complex64::new(0.8280450452577558, 0.560661576197336),
    Complex64::new(-0.5606615761973359, 0.8280450452577558),
    Complex64::new(0.18906866414980628, 0.9819638691095552),
    Complex64::new(-0.9819638691095552, 0.18906866414980636),
    Complex64::new(0.9945645707342554, 0.10412163387205459),
    Complex64::new(-0.1041216338720546, 0.9945645707342554),
    Complex64::new(0.6296382389149271, 0.7768884656732324),
    Complex64::new(-0.7768884656732323, 0.6296382389149272),
    Complex64::new(0.8790122264286335, 0.4767992300633221),
    Complex64::new(-0.4767992300633219, 0.8790122264286335),
    Complex64::new(0.2844075372112718, 0.9587034748958716),
    Complex64::new(-0.9587034748958715, 0.2844075372112721),
    Complex64::new(0.9551411683057708, 0.2961508882436238),
    Complex64::new(-0.29615088824362384, 0.9551411683057707),
    Complex64::new(0.4659764957679661, 0.8847970984309378),
    Complex64::new(-0.8847970984309378, 0.4659764957679662),
    Complex64::new(0.7691033376455797, 0.6391244448637757),
    Complex64::new(-0.6391244448637757, 0.7691033376455796),
    Complex64::new(0.0919089564971327, 0.9957674144676598),
    Complex64::new(-0.9957674144676598, 0.09190895649713275),
    Complex64::new(0.9984755805732948, 0.055195244349689934),
    Complex64::new(-0.05519524434968991, 0.9984755805732948),
    Complex64::new(0.6669999223036375, 0.745057785441466),
    Complex64::new(-0.745057785441466, 0.6669999223036376),
    Complex64::new(0.901348847046022, 0.43309381885315196),
    Complex64::new(-0.4330938188531519, 0.901348847046022),
    Complex64::new(0.33110630575987643, 0.9435934581619604),
    Complex64::new(-0.9435934581619604, 0.3311063057598765),
    Complex64::new(0.9685220942744174, 0.24892760574572015),
    Complex64::new(-0.24892760574572012, 0.9685220942744174),
    Complex64::new(0.508830142543107, 0.8608669386377673),
    Complex64::new(-0.8608669386377671, 0.5088301425431073),
    Complex64::new(0.799537269107905, 0.600616479383869),
    Complex64::new(-0.6006164793838688, 0.7995372691079052),
    Complex64::new(0.14065823933284924, 0.9900582102622971),
    Complex64::new(-0.990058210262297, 0.14065823933284954),
    Complex64::new(0.9882575677307495, 0.15279718525844344),
    Complex64::new(-0.1527971852584433, 0.9882575677307495),
    Complex64::new(0.5907597018588743, 0.8068475535437992),
    Complex64::new(-0.8068475535437993, 0.5907597018588742),
    Complex64::new(0.8545579883654005, 0.5193559901655896),
    Complex64::new(-0.5193559901655896, 0.8545579883654005),
    Complex64::new(0.23702360599436734, 0.9715038909862518),
    Complex64::new(-0.9715038909862518, 0.23702360599436717),
    Complex64::new(0.9394592236021899, 0.3426607173119944),
    Complex64::new(-0.34266071731199427, 0.9394592236021899),
    Complex64::new(0.4220002707997998, 0.9065957045149153),
    Complex64::new(-0.9065957045149153, 0.42200027079979985),
    Complex64::new(0.7368165688773699, 0.6760927035753159),
    Complex64::new(-0.6760927035753158, 0.73681656887737),
    Complex64::new(0.04293825693494096, 0.9990777277526454),
    Complex64::new(-0.9990777277526454, 0.04293825693494102),
    Complex64::new(0.9995294175010931, 0.030674803176636626),
    Complex64::new(-0.03067480317663646, 0.9995294175010931),
    Complex64::new(0.6850836677727004, 0.7284643904482252),
    Complex64::new(-0.7284643904482252, 0.6850836677727004),
    Complex64::new(0.9117060320054299, 0.4108431710579039),
    Complex64::new(-0.4108431710579038, 0.9117060320054299),
    Complex64::new(0.3541635254204905, 0.9351835099389475),
    Complex64::new(-0.9351835099389476, 0.3541635254204904),
    Complex64::new(0.9743393827855759, 0.22508391135979283),
    Complex64::new(-0.22508391135979267, 0.9743393827855759),
    Complex64::new(0.5298036246862948, 0.8481203448032971),
    Complex64::new(-0.8481203448032971, 0.5298036246862948),
    Complex64::new(0.8140363297059484, 0.5808139580957645),
    Complex64::new(-0.5808139580957644, 0.8140363297059485),
    Complex64::new(0.1649131204899701, 0.9863080972445987),
    Complex64::new(-0.9863080972445986, 0.16491312048997014),
    Complex64::new(0.9917097536690995, 0.12849811079379317),
    Complex64::new(-0.1284981107937931, 0.9917097536690995),
    Complex64::new(0.6103828062763095, 0.7921065773002124),
    Complex64::new(-0.7921065773002122, 0.6103828062763097),
    Complex64::new(0.8670462455156926, 0.49822766697278187),
    Complex64::new(-0.4982276669727816, 0.8670462455156928),
    Complex64::new(0.26079411791527557, 0.9653944416976894),
    Complex64::new(-0.9653944416976893, 0.26079411791527585),
    Complex64::new(0.9475855910177411, 0.3195020308160157),
    Complex64::new(-0.31950203081601564, 0.9475855910177412),
    Complex64::new(0.44412214457042926, 0.8959662497561851),
    Complex64::new(-0.8959662497561851, 0.4441221445704293),
    Complex64::new(0.7531867990436125, 0.6578066932970786),
    Complex64::new(-0.6578066932970786, 0.7531867990436125),
    Complex64::new(0.0674439195636641, 0.9977230666441916),
    Complex64::new(-0.9977230666441916, 0.06744391956366418),
    Complex64::new(0.9968202992911657, 0.07968243797143013),
    Complex64::new(-0.07968243797143001, 0.9968202992911658),
    Complex64::new(0.6485144010221126, 0.7612023854842618),
    Complex64::new(-0.7612023854842617, 0.6485144010221126),
    Complex64::new(0.8904487232447579, 0.45508358712634384),
    Complex64::new(-0.4550835871263437, 0.890448723244758),
    Complex64::new(0.307849640041535, 0.9514350209690083),
    Complex64::new(-0.9514350209690083, 0.30784964004153503),
    Complex64::new(0.9621214042690416, 0.272621355449949),
    Complex64::new(-0.27262135544994887, 0.9621214042690416),
    Complex64::new(0.48755016014843605, 0.8730949784182901),
    Complex64::new(-0.8730949784182901, 0.4875501601484359),
    Complex64::new(0.7845565971555752, 0.6200572117632891),
    Complex64::new(-0.6200572117632892, 0.7845565971555751),
    Complex64::new(0.11631863091190488, 0.9932119492347945),
    Complex64::new(-0.9932119492347945, 0.11631863091190471),
    Complex64::new(0.984210092386929, 0.17700422041214875),
    Complex64::new(-0.17700422041214875, 0.984210092386929),
    Complex64::new(0.5707807458869674, 0.8211025149911046),
    Complex64::new(-0.8211025149911046, 0.5707807458869673),
    Complex64::new(0.8415549774368984, 0.5401714727298929),
    Complex64::new(-0.5401714727298929, 0.8415549774368984),
    Complex64::new(0.21311031991609136, 0.9770281426577544),
    Complex64::new(-0.9770281426577544, 0.21311031991609142),
    Complex64::new(0.9307669610789837, 0.36561299780477385),
    Complex64::new(-0.36561299780477385, 0.9307669610789837),
    Complex64::new(0.3996241998456468, 0.9166790599210427),
    Complex64::new(-0.9166790599210426, 0.39962419984564707),
    Complex64::new(0.7200025079613817, 0.693971460889654),
    Complex64::new(-0.6939714608896538, 0.7200025079613818),
    Complex64::new(0.01840672990580482, 0.9998305817958234),
    Complex64::new(-0.9998305817958234, 0.0184067299058051),
    Complex64::new(0.9998305817958234, 0.01840672990580482),
    Complex64::new(-0.018406729905804695, 0.9998305817958234),
    Complex64::new(0.693971460889654, 0.7200025079613817),
    Complex64::new(-0.7200025079613817, 0.693971460889654),
    Complex64::new(0.9166790599210427, 0.3996241998456468),
    Complex64::new(-0.3996241998456467, 0.9166790599210427),
    Complex64::new(0.36561299780477396, 0.9307669610789837),
    Complex64::new(-0.9307669610789837, 0.3656129978047738),
    Complex64::new(0.9770281426577544, 0.21311031991609136),
    Complex64::new(-0.21311031991609125, 0.9770281426577544),
    Complex64::new(0.540171472729893, 0.8415549774368983),
    Complex64::new(-0.8415549774368983, 0.540171472729893),
    Complex64::new(0.8211025149911046, 0.5707807458869673),
    Complex64::new(-0.5707807458869671, 0.8211025149911048),
    Complex64::new(0.17700422041214886, 0.984210092386929),
    Complex64::new(-0.984210092386929, 0.17700422041214894),
    Complex64::new(0.9932119492347945, 0.11631863091190475),
    Complex64::new(-0.11631863091190475, 0.9932119492347945),
    Complex64::new(0.6200572117632892, 0.7845565971555752),
    Complex64::new(-0.784556597155575, 0.6200572117632894),
    Complex64::new(0.8730949784182901, 0.487550160148436),
    Complex64::new(-0.4875501601484357, 0.8730949784182902),
    Complex64::new(0.272621355449949, 0.9621214042690416),
    Complex64::new(-0.9621214042690415, 0.27262135544994925),
    Complex64::new(0.9514350209690083, 0.30784964004153487),
    Complex64::new(-0.30784964004153487, 0.9514350209690083),
    Complex64::new(0.45508358712634384, 0.8904487232447579),
    Complex64::new(-0.8904487232447579, 0.4550835871263439),
    Complex64::new(0.7612023854842618, 0.6485144010221124),
    Complex64::new(-0.6485144010221124, 0.7612023854842619),
    Complex64::new(0.07968243797143013, 0.9968202992911657),
    Complex64::new(-0.9968202992911657, 0.0796824379714302),
    Complex64::new(0.9977230666441916, 0.06744391956366405),
    Complex64::new(-0.06744391956366398, 0.9977230666441916),
    Complex64::new(0.6578066932970786, 0.7531867990436124),
    Complex64::new(-0.7531867990436124, 0.6578066932970787),
    Complex64::new(0.8959662497561852, 0.4441221445704292),
    Complex64::new(-0.44412214457042914, 0.8959662497561852),
    Complex64::new(0.31950203081601575, 0.9475855910177411),
    Complex64::new(-0.9475855910177411, 0.3195020308160158),
    Complex64::new(0.9653944416976894, 0.2607941179152755),
    Complex64::new(-0.26079411791527546, 0.9653944416976894),
    Complex64::new(0.49822766697278187, 0.8670462455156926),
    Complex64::new(-0.8670462455156928, 0.49822766697278176),
    Complex64::new(0.7921065773002124, 0.6103828062763095),
    Complex64::new(-0.6103828062763096, 0.7921065773002123),
    Complex64::new(0.12849811079379322, 0.9917097536690995),
    Complex64::new(-0.9917097536690995, 0.12849811079379309),
    Complex64::new(0.9863080972445987, 0.16491312048996992),
    Complex64::new(-0.16491312048996995, 0.9863080972445987),
    Complex64::new(0.5808139580957645, 0.8140363297059483),
    Complex64::new(-0.8140363297059484, 0.5808139580957645),
    Complex64::new(0.8481203448032972, 0.5298036246862946),
    Complex64::new(-0.5298036246862947, 0.8481203448032972),
    Complex64::new(0.22508391135979278, 0.9743393827855759),
    Complex64::new(-0.9743393827855759, 0.22508391135979283),
    Complex64::new(0.9351835099389476, 0.35416352542049034),
    Complex64::new(-0.3541635254204904, 0.9351835099389476),
    Complex64::new(0.4108431710579039, 0.9117060320054299),
    Complex64::new(-0.9117060320054298, 0.41084317105790413),
    Complex64::new(0.7284643904482252, 0.6850836677727004),
    Complex64::new(-0.6850836677727002, 0.7284643904482253),
    Complex64::new(0.03067480317663658, 0.9995294175010931),
    Complex64::new(-0.9995294175010931, 0.030674803176636865),
    Complex64::new(0.9990777277526454, 0.04293825693494082),
    Complex64::new(-0.042938256934940834, 0.9990777277526454),
    Complex64::new(0.676092703575316, 0.7368165688773698),
    Complex64::new(-0.7368165688773699, 0.6760927035753159),
    Complex64::new(0.9065957045149153, 0.4220002707997997),
    Complex64::new(-0.4220002707997997, 0.9065957045149153),
    Complex64::new(0.3426607173119944, 0.9394592236021899),
    Complex64::new(-0.9394592236021899, 0.34266071731199443),
    Complex64::new(0.9715038909862518, 0.2370236059943672),
    Complex64::new(-0.23702360599436723, 0.9715038909862518),
    Complex64::new(0.5193559901655895, 0.8545579883654005),
    Complex64::new(-0.8545579883654004, 0.5193559901655898),
    Complex64::new(0.8068475535437993, 0.5907597018588742),
    Complex64::new(-0.590759701858874, 0.8068475535437994),
    Complex64::new(0.1527971852584434, 0.9882575677307495),
    Complex64::new(-0.9882575677307495, 0.15279718525844369),
    Complex64::new(0.9900582102622971, 0.1406582393328492),
    Complex64::new(-0.14065823933284913, 0.9900582102622971),
    Complex64::new(0.600616479383869, 0.799537269107905),
    Complex64::new(-0.7995372691079051, 0.6006164793838689),
    Complex64::new(0.8608669386377673, 0.508830142543107),
    Complex64::new(-0.5088301425431071, 0.8608669386377672),
    Complex64::new(0.24892760574572026, 0.9685220942744173),
    Complex64::new(-0.9685220942744174, 0.2489276057457201),
    Complex64::new(0.9435934581619604, 0.33110630575987643),
    Complex64::new(-0.3311063057598763, 0.9435934581619604),
    Complex64::new(0.433093818853152, 0.901348847046022),
    Complex64::new(-0.9013488470460219, 0.43309381885315207),
    Complex64::new(0.7450577854414661, 0.6669999223036375),
    Complex64::new(-0.6669999223036374, 0.7450577854414661),
    Complex64::new(0.05519524434969003, 0.9984755805732948),
    Complex64::new(-0.9984755805732948, 0.055195244349690094),
    Complex64::new(0.9957674144676598, 0.09190895649713272),
    Complex64::new(-0.09190895649713257, 0.9957674144676598),
    Complex64::new(0.6391244448637757, 0.7691033376455796),
    Complex64::new(-0.7691033376455795, 0.6391244448637758),
    Complex64::new(0.8847970984309378, 0.4659764957679662),
    Complex64::new(-0.465976495767966, 0.8847970984309379),
    Complex64::new(0.29615088824362396, 0.9551411683057707),
    Complex64::new(-0.9551411683057707, 0.296150888243624),
    Complex64::new(0.9587034748958716, 0.2844075372112719),
    Complex64::new(-0.2844075372112717, 0.9587034748958716),
    Complex64::new(0.47679923006332225, 0.8790122264286334),
    Complex64::new(-0.8790122264286335, 0.4767992300633221),
    Complex64::new(0.7768884656732324, 0.629638238914927),
    Complex64::new(-0.6296382389149271, 0.7768884656732324),
    Complex64::new(0.10412163387205473, 0.9945645707342554),
    Complex64::new(-0.9945645707342554, 0.10412163387205457),
    Complex64::new(0.9819638691095552, 0.1890686641498062),
    Complex64::new(-0.18906866414980616, 0.9819638691095552),
    Complex64::new(0.560661576197336, 0.8280450452577558),
    Complex64::new(-0.8280450452577557, 0.5606615761973361),
    Complex64::new(0.83486287498638, 0.5504579729366048),
    Complex64::new(-0.5504579729366047, 0.8348628749863801),
    Complex64::new(0.20110463484209196, 0.9795697656854405),
    Complex64::new(-0.9795697656854405, 0.201104634842092),
    Complex64::new(0.9262102421383114, 0.37700741021641826),
    Complex64::new(-0.3770074102164182, 0.9262102421383114),
    Complex64::new(0.3883450466988263, 0.9215140393420419),
    Complex64::new(-0.9215140393420418, 0.3883450466988266),
    Complex64::new(0.7114321957452164, 0.7027547444572253),
    Complex64::new(-0.7027547444572251, 0.7114321957452167),
    Complex64::new(0.006135884649154515, 0.9999811752826011),
    Complex64::new(-0.9999811752826011, 0.006135884649154799),
    Complex64::new(0.9999952938095762, 0.003067956762965976),
    Complex64::new(-0.0030679567629660156, 0.9999952938095762),
    Complex64::new(0.704934080375905, 0.7092728264388656),
    Complex64::new(-0.7092728264388655, 0.7049340803759051),
    Complex64::new(0.9227011283338786, 0.38551605384391885),
    Complex64::new(-0.3855160538439189, 0.9227011283338785),
    Complex64::new(0.3798472089240511, 0.9250492407826776),
    Complex64::new(-0.9250492407826775, 0.3798472089240514),
    Complex64::new(0.9801821359681174, 0.19809841071795356),
    Complex64::new(-0.19809841071795362, 0.9801821359681174),
    Complex64::new(0.5530167055800276, 0.8331701647019132),
    Complex64::new(-0.8331701647019132, 0.5530167055800276),
    Complex64::new(0.829761233794523, 0.5581185312205561),
    Complex64::new(-0.5581185312205561, 0.829761233794523),
    Complex64::new(0.19208039704989238, 0.9813791933137546),
    Complex64::new(-0.9813791933137546, 0.19208039704989247),
    Complex64::new(0.9948793307948056, 0.10106986275482782),
    Complex64::new(-0.10106986275482775, 0.9948793307948056),
    Complex64::new(0.6320187359398091, 0.7749531065948738),
    Complex64::new(-0.7749531065948738, 0.6320187359398091),
    Complex64::new(0.8804708890521608, 0.47410021465054997),
    Complex64::new(-0.4741002146505499, 0.8804708890521609),
    Complex64::new(0.28734745954472957, 0.9578264130275329),
    Complex64::new(-0.9578264130275329, 0.2873474595447296),
    Complex64::new(0.9560452513499964, 0.29321916269425863),
    Complex64::new(-0.2932191626942586, 0.9560452513499965),
    Complex64::new(0.46868882203582796, 0.8833633386657316),
    Complex64::new(-0.8833633386657317, 0.46868882203582785),
    Complex64::new(0.7710605242618138, 0.6367618612362842),
    Complex64::new(-0.6367618612362843, 0.7710605242618137),
    Complex64::new(0.09496349532963906, 0.9954807554919269),
    Complex64::new(-0.9954807554919269, 0.09496349532963891),
    Complex64::new(0.9986402181802653, 0.052131704680283324),
    Complex64::new(-0.05213170468028319, 0.9986402181802653),
    Complex64::new(0.669282588346636, 0.7430079521351217),
    Complex64::new(-0.7430079521351217, 0.669282588346636),
    Complex64::new(0.9026733182372588, 0.4303264813400826),
    Complex64::new(-0.4303264813400827, 0.9026733182372588),
    Complex64::new(0.3339996514420095, 0.9425731976014469),
    Complex64::new(-0.9425731976014469, 0.3339996514420094),
    Complex64::new(0.9692812353565485, 0.2459550503357946),
    Complex64::new(-0.24595505033579448, 0.9692812353565485),
    Complex64::new(0.5114688504379705, 0.8593018183570084),
    Complex64::new(-0.8593018183570084, 0.5114688504379705),
    Complex64::new(0.8013761717231402, 0.5981607069963423),
    Complex64::new(-0.5981607069963422, 0.8013761717231404),
    Complex64::new(0.14369503315029458, 0.9896220174632008),
    Complex64::new(-0.9896220174632008, 0.14369503315029464),
    Complex64::new(0.9887216919603238, 0.1497645346773215),
    Complex64::new(-0.1497645346773215, 0.9887216919603238),
    Complex64::new(0.5932322950397998, 0.8050313311429637),
    Complex64::new(-0.8050313311429634, 0.5932322950398),
    Complex64::new(0.8561473283751945, 0.5167317990176499),
    Complex64::new(-0.5167317990176497, 0.8561473283751946),
    Complex64::new(0.2400030224487415, 0.9707721407289504),
    Complex64::new(-0.9707721407289502, 0.24000302244874178),
    Complex64::new(0.9405060705932683, 0.33977688440682685),
    Complex64::new(-0.33977688440682685, 0.9405060705932683),
    Complex64::new(0.4247796812091088, 0.9052967593181188),
    Complex64::new(-0.9052967593181187, 0.42477968120910886),
    Complex64::new(0.7388873244606151, 0.673829000378756),
    Complex64::new(-0.673829000378756, 0.7388873244606152),
    Complex64::new(0.046003182130914644, 0.9989412931868569),
    Complex64::new(-0.9989412931868569, 0.046003182130914706),
    Complex64::new(0.9996188224951786, 0.02760814577896574),
    Complex64::new(-0.027608145778965698, 0.9996188224951786),
    Complex64::new(0.6873153408917592, 0.726359155084346),
    Complex64::new(-0.7263591550843458, 0.6873153408917593),
    Complex64::new(0.9129621904283982, 0.4080441628649787),
    Complex64::new(-0.40804416286497863, 0.9129621904283982),
    Complex64::new(0.35703096123343003, 0.9340925504042589),
    Complex64::new(-0.9340925504042588, 0.3570309612334303),
    Complex64::new(0.9750253450669941, 0.2220936209732035),
    Complex64::new(-0.22209362097320348, 0.9750253450669941),
    Complex64::new(0.532403127877198, 0.846490938774052),
    Complex64::new(-0.846490938774052, 0.532403127877198),
    Complex64::new(0.8158144108067338, 0.5783137964116556),
    Complex64::new(-0.5783137964116555, 0.8158144108067338),
    Complex64::new(0.16793829497473123, 0.9857975091675674),
    Complex64::new(-0.9857975091675674, 0.16793829497473128),
    Complex64::new(0.9920993131421918, 0.12545498341154623),
    Complex64::new(-0.12545498341154607, 0.9920993131421918),
    Complex64::new(0.6128100824294097, 0.79023022143731),
    Complex64::new(-0.7902302214373099, 0.6128100824294098),
    Complex64::new(0.8685707059713409, 0.49556526182577254),
    Complex64::new(-0.4955652618257724, 0.868570705971341),
    Complex64::new(0.2637546789748315, 0.9645897932898126),
    Complex64::new(-0.9645897932898126, 0.26375467897483157),
    Complex64::new(0.9485613499157303, 0.31659337555616585),
    Complex64::new(-0.31659337555616573, 0.9485613499157304),
    Complex64::new(0.4468688401623743, 0.8945994856313826),
    Complex64::new(-0.8945994856313827, 0.44686884016237416),
    Complex64::new(0.7552013768965365, 0.6554928529996153),
    Complex64::new(-0.6554928529996155, 0.7552013768965365),
    Complex64::new(0.07050457338961401, 0.9975114561403035),
    Complex64::new(-0.9975114561403035, 0.07050457338961386),
    Complex64::new(0.997060070339483, 0.07662386139203149),
    Complex64::new(-0.0766238613920315, 0.997060070339483),
    Complex64::new(0.650846684996381, 0.759209188978388),
    Complex64::new(-0.7592091889783881, 0.650846684996381),
    Complex64::new(0.8918407093923427, 0.4523495872337709),
    Complex64::new(-0.4523495872337709, 0.8918407093923427),
    Complex64::new(0.3107671527496115, 0.9504860739494817),
    Complex64::new(-0.9504860739494817, 0.31076715274961153),
    Complex64::new(0.9629532668736839, 0.2696683255729151),
    Complex64::new(-0.2696683255729151, 0.9629532668736839),
    Complex64::new(0.4902264832882911, 0.8715950866559511),
    Complex64::new(-0.8715950866559509, 0.4902264832882914),
    Complex64::new(0.7864552135990858, 0.6176473079378039),
    Complex64::new(-0.6176473079378038, 0.7864552135990859),
    Complex64::new(0.11936521481099135, 0.9928504144598651),
    Complex64::new(-0.9928504144598651, 0.11936521481099163),
    Complex64::new(0.9847485018019042, 0.17398387338746382),
    Complex64::new(-0.1739838733874637, 0.9847485018019042),
    Complex64::new(0.5732971666980423, 0.8193475200767969),
    Complex64::new(-0.819347520076797, 0.5732971666980421),
    Complex64::new(0.8432082396418454, 0.5375870762956454),
    Complex64::new(-0.5375870762956456, 0.8432082396418454),
    Complex64::new(0.2161067970762196, 0.9763697313300211),
    Complex64::new(-0.9763697313300211, 0.21610679707621944),
    Complex64::new(0.9318842655816681, 0.3627557243673972),
    Complex64::new(-0.3627557243673971, 0.9318842655816681),
    Complex64::new(0.40243465085941854, 0.9154487160882678),
    Complex64::new(-0.9154487160882677, 0.4024346508594186),
    Complex64::new(0.7221281939292153, 0.6917592583641577),
    Complex64::new(-0.6917592583641576, 0.7221281939292155),
    Complex64::new(0.021474080275469605, 0.9997694053512153),
    Complex64::new(-0.9997694053512153, 0.021474080275469667),
    Complex64::new(0.9998823474542126, 0.0153392062849881),
    Complex64::new(-0.015339206284988098, 0.9998823474542126),
    Complex64::new(0.696177131491463, 0.7178700450557317),
    Complex64::new(-0.7178700450557316, 0.6961771314914631),
    Complex64::new(0.9179007756213905, 0.3968099874167103),
    Complex64::new(-0.3968099874167103, 0.9179007756213905),
    Complex64::new(0.3684668299533723, 0.9296408958431813),
    Complex64::new(-0.9296408958431812, 0.3684668299533726),
    Complex64::new(0.9776773578245099, 0.2101118368804696),
    Complex64::new(-0.2101118368804696, 0.9776773578245099),
    Complex64::new(0.542750784864516, 0.8398937941959994),
    Complex64::new(-0.8398937941959995, 0.5427507848645159),
    Complex64::new(0.8228497813758264, 0.5682589526701315),
    Complex64::new(-0.5682589526701315, 0.8228497813758263),
    Complex64::new(0.18002290140569951, 0.9836624192117303),
    Complex64::new(-0.9836624192117303, 0.18002290140569957),
    Complex64::new(0.9935641355205953, 0.11327095217756435),
    Complex64::new(-0.11327095217756424, 0.9935641355205953),
    Complex64::new(0.6224612793741501, 0.7826505961665757),
    Complex64::new(-0.7826505961665756, 0.6224612793741501),
    Complex64::new(0.8745866522781761, 0.48486924800079106),
    Complex64::new(-0.484869248000791, 0.8745866522781762),
    Complex64::new(0.27557181931095825, 0.9612804858113206),
    Complex64::new(-0.9612804858113206, 0.2755718193109583),
    Complex64::new(0.9523750127197659, 0.3049292297354024),
    Complex64::new(-0.30492922973540226, 0.9523750127197659),
    Complex64::new(0.4578133035988773, 0.8890483558546646),
    Complex64::new(-0.8890483558546646, 0.4578133035988772),
    Complex64::new(0.7631884172633813, 0.6461760129833163),
    Complex64::new(-0.6461760129833164, 0.7631884172633813),
    Complex64::new(0.0827402645493758, 0.9965711457905548),
    Complex64::new(-0.9965711457905548, 0.08274026454937564),
    Complex64::new(0.997925286198596, 0.06438263092985747),
    Complex64::new(-0.06438263092985728, 0.997925286198596),
    Complex64::new(0.6601143420674205, 0.7511651319096864),
    Complex64::new(-0.7511651319096865, 0.6601143420674205),
    Complex64::new(0.8973245807054183, 0.44137126873171667),
    Complex64::new(-0.4413712687317167, 0.8973245807054183),
    Complex64::new(0.32240767880107, 0.9466009130832835),
    Complex64::new(-0.9466009130832835, 0.32240767880106985),
    Complex64::new(0.9661900034454125, 0.257831102162159),
    Complex64::new(-0.2578311021621588, 0.9661900034454126),
    Complex64::new(0.5008853826112409, 0.865513624090569),
    Complex64::new(-0.865513624090569, 0.5008853826112409),
    Complex64::new(0.7939754775543372, 0.6079497849677736),
    Complex64::new(-0.6079497849677735, 0.7939754775543373),
    Complex64::new(0.13154002870288328, 0.9913108598461154),
    Complex64::new(-0.9913108598461154, 0.13154002870288334),
    Complex64::new(0.9868094018141855, 0.16188639378011183),
    Complex64::new(-0.16188639378011177, 0.9868094018141855),
    Complex64::new(0.5833086529376983, 0.8122505865852039),
    Complex64::new(-0.8122505865852038, 0.5833086529376985),
    Complex64::new(0.8497417680008525, 0.5271991347819013),
    Complex64::new(-0.5271991347819011, 0.8497417680008527),
    Complex64::new(0.2280720831708858, 0.9736442496508119),
    Complex64::new(-0.9736442496508119, 0.22807208317088606),
    Complex64::new(0.9362656671702783, 0.3512927560855671),
    Complex64::new(-0.35129275608556704, 0.9362656671702783),
    Complex64::new(0.41363831223843456, 0.9104412922580671),
    Complex64::new(-0.9104412922580671, 0.4136383122384346),
    Complex64::new(0.7305627692278276, 0.6828455463852481),
    Complex64::new(-0.682845546385248, 0.7305627692278276),
    Complex64::new(0.03374117185137764, 0.9994306045554617),
    Complex64::new(-0.9994306045554617, 0.033741171851377705),
    Complex64::new(0.9992047586183639, 0.03987292758773981),
    Complex64::new(-0.03987292758773973, 0.9992047586183639),
    Complex64::new(0.6783500431298616, 0.7347388780959634),
    Complex64::new(-0.7347388780959635, 0.6783500431298614),
    Complex64::new(0.9078861164876663, 0.4192168883632239),
    Complex64::new(-0.41921688836322407, 0.9078861164876662),
    Complex64::new(0.34554132496398915, 0.9384035340631081),
    Complex64::new(-0.9384035340631082, 0.345541324963989),
    Complex64::new(0.9722264970789363, 0.23404195858354343),
    Complex64::new(-0.23404195858354332, 0.9722264970789364),
    Complex64::new(0.5219752929371544, 0.8529606049303636),
    Complex64::new(-0.8529606049303636, 0.5219752929371545),
    Complex64::new(0.808656181588175, 0.5882815482226452),
    Complex64::new(-0.5882815482226452, 0.8086561815881751),
    Complex64::new(0.15582839765426532, 0.9877841416445722),
    Complex64::new(-0.9877841416445722, 0.15582839765426537),
    Complex64::new(0.9904850842564571, 0.13762012158648604),
    Complex64::new(-0.13762012158648607, 0.990485084256457),
    Complex64::new(0.6030665985403483, 0.797690840943391),
    Complex64::new(-0.7976908409433909, 0.6030665985403484),
    Complex64::new(0.8624239561110406, 0.5061866453451552),
    Complex64::new(-0.5061866453451551, 0.8624239561110406),
    Complex64::new(0.2518978181542169, 0.9677538370934755),
    Complex64::new(-0.9677538370934754, 0.2518978181542172),
    Complex64::new(0.9446048372614803, 0.3282098435790925),
    Complex64::new(-0.32820984357909255, 0.9446048372614803),
    Complex64::new(0.4358570799222555, 0.9000158920161603),
    Complex64::new(-0.9000158920161602, 0.43585707992225553),
    Complex64::new(0.7471006059801801, 0.6647109782033448),
    Complex64::new(-0.6647109782033449, 0.7471006059801801),
    Complex64::new(0.05825826450043573, 0.9983015449338929),
    Complex64::new(-0.9983015449338929, 0.058258264500435794),
    Complex64::new(0.996044700901252, 0.0888535525825246),
    Complex64::new(-0.08885355258252456, 0.996044700901252),
    Complex64::new(0.6414810128085832, 0.7671389119358204),
    Complex64::new(-0.7671389119358203, 0.6414810128085832),
    Complex64::new(0.8862225301488806, 0.46325978355186015),
    Complex64::new(-0.46325978355186015, 0.8862225301488806),
    Complex64::new(0.2990798263080405, 0.9542280951091057),
    Complex64::new(-0.9542280951091056, 0.29907982630804053),
    Complex64::new(0.9595715130819845, 0.28146493792575794),
    Complex64::new(-0.28146493792575794, 0.9595715130819845),
    Complex64::new(0.479493757660153, 0.8775452902072612),
    Complex64::new(-0.8775452902072611, 0.4794937576601533),
    Complex64::new(0.778816512381476, 0.6272518154951441),
    Complex64::new(-0.6272518154951439, 0.7788165123814761),
    Complex64::new(0.10717242495680887, 0.9942404494531879),
    Complex64::new(-0.9942404494531879, 0.10717242495680916),
    Complex64::new(0.9825393022874412, 0.18605515166344663),
    Complex64::new(-0.1860551516634465, 0.9825393022874412),
    Complex64::new(0.5631993440138341, 0.8263210628456634),
    Complex64::new(-0.8263210628456635, 0.5631993440138341),
    Complex64::new(0.836547727223512, 0.5478940591731002),
    Complex64::new(-0.5478940591731002, 0.836547727223512),
    Complex64::new(0.204108966092817, 0.9789481753190622),
    Complex64::new(-0.9789481753190622, 0.20410896609281684),
    Complex64::new(0.9273625256504011, 0.37416406297145793),
    Complex64::new(-0.3741640629714579, 0.9273625256504011),
    Complex64::new(0.391170384302254, 0.9203182767091105),
    Complex64::new(-0.9203182767091105, 0.39117038430225404),
    Complex64::new(0.7135848687807936, 0.7005687939432483),
    Complex64::new(-0.7005687939432482, 0.7135848687807937),
    Complex64::new(0.00920375478205996, 0.9999576445519639),
    Complex64::new(-0.9999576445519639, 0.00920375478206002),
    Complex64::new(0.9999576445519639, 0.00920375478205982),
    Complex64::new(-0.009203754782059837, 0.9999576445519639),
    Complex64::new(0.7005687939432484, 0.7135848687807935),
    Complex64::new(-0.7135848687807936, 0.7005687939432483),
    Complex64::new(0.9203182767091106, 0.39117038430225387),
    Complex64::new(-0.39117038430225387, 0.9203182767091106),
    Complex64::new(0.374164062971458, 0.9273625256504011),
    Complex64::new(-0.9273625256504011, 0.37416406297145804),
    Complex64::new(0.9789481753190622, 0.20410896609281687),
    Complex64::new(-0.2041089660928169, 0.9789481753190622),
    Complex64::new(0.5478940591731002, 0.8365477272235119),
    Complex64::new(-0.8365477272235119, 0.5478940591731004),
    Complex64::new(0.8263210628456635, 0.5631993440138341),
    Complex64::new(-0.563199344013834, 0.8263210628456636),
    Complex64::new(0.18605515166344663, 0.9825393022874412),
    Complex64::new(-0.9825393022874412, 0.1860551516634469),
    Complex64::new(0.9942404494531879, 0.10717242495680884),
    Complex64::new(-0.10717242495680876, 0.9942404494531879),
    Complex64::new(0.6272518154951442, 0.7788165123814759),
    Complex64::new(-0.778816512381476, 0.6272518154951441),
    Complex64::new(0.8775452902072614, 0.479493757660153),
    Complex64::new(-0.4794937576601531, 0.8775452902072612),
    Complex64::new(0.28146493792575805, 0.9595715130819845),
    Complex64::new(-0.9595715130819845, 0.2814649379257579),
    Complex64::new(0.9542280951091057, 0.2990798263080405),
    Complex64::new(-0.29907982630804036, 0.9542280951091057),
    Complex64::new(0.46325978355186026, 0.8862225301488806),
    Complex64::new(-0.8862225301488805, 0.4632597835518603),
    Complex64::new(0.7671389119358204, 0.6414810128085832),
    Complex64::new(-0.641481012808583, 0.7671389119358205),
    Complex64::new(0.08885355258252468, 0.996044700901252),
    Complex64::new(-0.996044700901252, 0.08885355258252475),
    Complex64::new(0.9983015449338929, 0.05825826450043575),
    Complex64::new(-0.05825826450043561, 0.9983015449338929),
    Complex64::new(0.6647109782033449, 0.7471006059801801),
    Complex64::new(-0.74710060598018, 0.664710978203345),
    Complex64::new(0.9000158920161603, 0.4358570799222555),
    Complex64::new(-0.43585707992225536, 0.9000158920161603),
    Complex64::new(0.32820984357909266, 0.9446048372614803),
    Complex64::new(-0.9446048372614801, 0.3282098435790927),
    Complex64::new(0.9677538370934755, 0.25189781815421697),
    Complex64::new(-0.2518978181542168, 0.9677538370934755),
    Complex64::new(0.5061866453451555, 0.8624239561110405),
    Complex64::new(-0.8624239561110405, 0.5061866453451552),
    Complex64::new(0.7976908409433912, 0.6030665985403482),
    Complex64::new(-0.6030665985403483, 0.797690840943391),
    Complex64::new(0.13762012158648618, 0.990485084256457),
    Complex64::new(-0.9904850842564571, 0.13762012158648604),
    Complex64::new(0.9877841416445722, 0.15582839765426523),
    Complex64::new(-0.1558283976542652, 0.9877841416445722),
    Complex64::new(0.5882815482226453, 0.808656181588175),
    Complex64::new(-0.808656181588175, 0.5882815482226453),
    Complex64::new(0.8529606049303636, 0.5219752929371544),
    Complex64::new(-0.5219752929371543, 0.8529606049303637),
    Complex64::new(0.23404195858354346, 0.9722264970789363),
    Complex64::new(-0.9722264970789363, 0.2340419585835435),
    Complex64::new(0.9384035340631081, 0.3455413249639891),
    Complex64::new(-0.34554132496398904, 0.9384035340631082),
    Complex64::new(0.41921688836322396, 0.9078861164876662),
    Complex64::new(-0.907886116487666, 0.41921688836322424),
    Complex64::new(0.7347388780959635, 0.6783500431298615),
    Complex64::new(-0.6783500431298612, 0.7347388780959636),
    Complex64::new(0.039872927587739845, 0.9992047586183639),
    Complex64::new(-0.9992047586183639, 0.03987292758774013),
    Complex64::new(0.9994306045554617, 0.03374117185137758),
    Complex64::new(-0.03374117185137752, 0.9994306045554617),
    Complex64::new(0.6828455463852481, 0.7305627692278276),
    Complex64::new(-0.7305627692278275, 0.6828455463852482),
    Complex64::new(0.9104412922580672, 0.4136383122384345),
    Complex64::new(-0.41363831223843445, 0.9104412922580672),
    Complex64::new(0.35129275608556715, 0.9362656671702783),
    Complex64::new(-0.9362656671702783, 0.3512927560855672),
    Complex64::new(0.973644249650812, 0.22807208317088573),
    Complex64::new(-0.22807208317088568, 0.973644249650812),
    Complex64::new(0.5271991347819014, 0.8497417680008524),
    Complex64::new(-0.8497417680008525, 0.5271991347819013),
    Complex64::new(0.8122505865852039, 0.5833086529376983),
    Complex64::new(-0.5833086529376984, 0.8122505865852039),
    Complex64::new(0.16188639378011188, 0.9868094018141854),
    Complex64::new(-0.9868094018141855, 0.16188639378011174),
    Complex64::new(0.9913108598461154, 0.13154002870288312),
    Complex64::new(-0.13154002870288314, 0.9913108598461154),
    Complex64::new(0.6079497849677737, 0.7939754775543372),
    Complex64::new(-0.7939754775543372, 0.6079497849677736),
    Complex64::new(0.8655136240905691, 0.5008853826112407),
    Complex64::new(-0.5008853826112408, 0.8655136240905691),
    Complex64::new(0.25783110216215893, 0.9661900034454126),
    Complex64::new(-0.9661900034454125, 0.257831102162159),
    Complex64::new(0.9466009130832835, 0.32240767880106985),
    Complex64::new(-0.32240767880106985, 0.9466009130832835),
    Complex64::new(0.4413712687317166, 0.8973245807054183),
    Complex64::new(-0.8973245807054182, 0.4413712687317169),
    Complex64::new(0.7511651319096865, 0.6601143420674205),
    Complex64::new(-0.6601143420674204, 0.7511651319096866),
    Complex64::new(0.06438263092985741, 0.997925286198596),
    Complex64::new(-0.997925286198596, 0.0643826309298577),
    Complex64::new(0.9965711457905548, 0.08274026454937569),
    Complex64::new(-0.08274026454937568, 0.9965711457905548),
    Complex64::new(0.6461760129833164, 0.7631884172633813),
    Complex64::new(-0.763188417263381, 0.6461760129833166),
    Complex64::new(0.8890483558546646, 0.4578133035988772),
    Complex64::new(-0.457813303598877, 0.8890483558546647),
    Complex64::new(0.30492922973540243, 0.9523750127197659),
    Complex64::new(-0.9523750127197658, 0.30492922973540265),
    Complex64::new(0.9612804858113206, 0.27557181931095814),
    Complex64::new(-0.27557181931095814, 0.9612804858113206),
    Complex64::new(0.4848692480007911, 0.8745866522781761),
    Complex64::new(-0.8745866522781761, 0.4848692480007911),
    Complex64::new(0.7826505961665757, 0.62246127937415),
    Complex64::new(-0.62246127937415, 0.7826505961665757),
    Complex64::new(0.11327095217756436, 0.9935641355205953),
    Complex64::new(-0.9935641355205953, 0.11327095217756442),
    Complex64::new(0.9836624192117303, 0.18002290140569951),
    Complex64::new(-0.1800229014056994, 0.9836624192117303),
    Complex64::new(0.5682589526701315, 0.8228497813758263),
    Complex64::new(-0.8228497813758262, 0.5682589526701317),
    Complex64::new(0.8398937941959995, 0.5427507848645159),
    Complex64::new(-0.5427507848645158, 0.8398937941959996),
    Complex64::new(0.21011183688046972, 0.9776773578245099),
    Complex64::new(-0.9776773578245099, 0.2101118368804698),
    Complex64::new(0.9296408958431813, 0.3684668299533723),
    Complex64::new(-0.3684668299533722, 0.9296408958431813),
    Complex64::new(0.3968099874167104, 0.9179007756213904),
    Complex64::new(-0.9179007756213905, 0.39680998741671025),
    Complex64::new(0.7178700450557317, 0.696177131491463),
    Complex64::new(-0.696177131491463, 0.7178700450557317),
    Complex64::new(0.01533920628498822, 0.9998823474542126),
    Complex64::new(-0.9998823474542126, 0.01533920628498806),
    Complex64::new(0.9997694053512153, 0.021474080275469508),
    Complex64::new(-0.021474080275469484, 0.9997694053512153),
    Complex64::new(0.6917592583641577, 0.7221281939292153),
    Complex64::new(-0.7221281939292152, 0.6917592583641579),
    Complex64::new(0.9154487160882678, 0.40243465085941843),
    Complex64::new(-0.40243465085941843, 0.9154487160882678),
    Complex64::new(0.3627557243673972, 0.9318842655816681),
    Complex64::new(-0.931884265581668, 0.3627557243673973),
    Complex64::new(0.9763697313300211, 0.21610679707621952),
    Complex64::new(-0.2161067970762195, 0.9763697313300211),
    Complex64::new(0.5375870762956455, 0.8432082396418454),
    Complex64::new(-0.8432082396418453, 0.5375870762956457),
    Complex64::new(0.8193475200767969, 0.5732971666980422),
    Complex64::new(-0.573297166698042, 0.8193475200767971),
    Complex64::new(0.17398387338746385, 0.9847485018019042),
    Complex64::new(-0.9847485018019042, 0.17398387338746413),
    Complex64::new(0.9928504144598651, 0.11936521481099135),
    Complex64::new(-0.11936521481099123, 0.9928504144598651),
    Complex64::new(0.617647307937804, 0.7864552135990858),
    Complex64::new(-0.7864552135990858, 0.6176473079378039),
    Complex64::new(0.871595086655951, 0.49022648328829116),
    Complex64::new(-0.4902264832882912, 0.871595086655951),
    Complex64::new(0.2696683255729152, 0.9629532668736839),
    Complex64::new(-0.9629532668736839, 0.2696683255729151),
    Complex64::new(0.9504860739494817, 0.3107671527496115),
    Complex64::new(-0.31076715274961136, 0.9504860739494818),
    Complex64::new(0.452349587233771, 0.8918407093923427),
    Complex64::new(-0.8918407093923426, 0.45234958723377106),
    Complex64::new(0.7592091889783881, 0.6508466849963809),
    Complex64::new(-0.6508466849963808, 0.7592091889783882),
    Complex64::new(0.07662386139203162, 0.997060070339483),
    Complex64::new(-0.997060070339483, 0.07662386139203169),
    Complex64::new(0.9975114561403035, 0.07050457338961386),
    Complex64::new(-0.0705045733896139, 0.9975114561403035),
    Complex64::new(0.6554928529996155, 0.7552013768965365),
    Complex64::new(-0.7552013768965364, 0.6554928529996156),
    Complex64::new(0.8945994856313827, 0.44686884016237416),
    Complex64::new(-0.446868840162374, 0.8945994856313828),
    Complex64::new(0.31659337555616585, 0.9485613499157303),
    Complex64::new(-0.9485613499157303, 0.31659337555616607),
    Complex64::new(0.9645897932898128, 0.26375467897483135),
    Complex64::new(-0.2637546789748314, 0.9645897932898128),
    Complex64::new(0.4955652618257725, 0.8685707059713409),
    Complex64::new(-0.8685707059713409, 0.49556526182577254),
    Complex64::new(0.79023022143731, 0.6128100824294097),
    Complex64::new(-0.6128100824294097, 0.79023022143731),
    Complex64::new(0.1254549834115462, 0.9920993131421918),
    Complex64::new(-0.9920993131421918, 0.12545498341154626),
    Complex64::new(0.9857975091675675, 0.16793829497473117),
    Complex64::new(-0.1679382949747311, 0.9857975091675675),
    Complex64::new(0.5783137964116556, 0.8158144108067338),
    Complex64::new(-0.8158144108067337, 0.5783137964116557),
    Complex64::new(0.8464909387740521, 0.5324031278771979),
    Complex64::new(-0.5324031278771979, 0.8464909387740521),
    Complex64::new(0.2220936209732036, 0.9750253450669941),
    Complex64::new(-0.9750253450669941, 0.22209362097320365),
    Complex64::new(0.934092550404259, 0.35703096123343),
    Complex64::new(-0.3570309612334299, 0.934092550404259),
    Complex64::new(0.40804416286497874, 0.9129621904283981),
    Complex64::new(-0.9129621904283982, 0.4080441628649786),
    Complex64::new(0.726359155084346, 0.687315340891759),
    Complex64::new(-0.6873153408917592, 0.7263591550843459),
    Complex64::new(0.02760814577896582, 0.9996188224951786),
    Complex64::new(-0.9996188224951786, 0.02760814577896566),
    Complex64::new(0.9989412931868569, 0.04600318213091462),
    Complex64::new(-0.04600318213091452, 0.9989412931868569),
    Complex64::new(0.6738290003787561, 0.7388873244606151),
    Complex64::new(-0.738887324460615, 0.6738290003787561),
    Complex64::new(0.9052967593181188, 0.4247796812091088),
    Complex64::new(-0.4247796812091087, 0.9052967593181188),
    Complex64::new(0.33977688440682696, 0.9405060705932683),
    Complex64::new(-0.9405060705932683, 0.339776884406827),
    Complex64::new(0.9707721407289504, 0.2400030224487415),
    Complex64::new(-0.2400030224487414, 0.9707721407289504),
    Complex64::new(0.51673179901765, 0.8561473283751945),
    Complex64::new(-0.8561473283751945, 0.5167317990176498),
    Complex64::new(0.8050313311429637, 0.5932322950397998),
    Complex64::new(-0.5932322950397999, 0.8050313311429635),
    Complex64::new(0.14976453467732162, 0.9887216919603238),
    Complex64::new(-0.9887216919603238, 0.14976453467732145),
    Complex64::new(0.9896220174632009, 0.14369503315029447),
    Complex64::new(-0.14369503315029444, 0.9896220174632009),
    Complex64::new(0.5981607069963424, 0.8013761717231401),
    Complex64::new(-0.8013761717231402, 0.5981607069963424),
    Complex64::new(0.8593018183570085, 0.5114688504379703),
    Complex64::new(-0.5114688504379704, 0.8593018183570084),
    Complex64::new(0.2459550503357946, 0.9692812353565485),
    Complex64::new(-0.9692812353565484, 0.24595505033579465),
    Complex64::new(0.9425731976014469, 0.3339996514420094),
    Complex64::new(-0.3339996514420094, 0.9425731976014469),
    Complex64::new(0.4303264813400826, 0.9026733182372588),
    Complex64::new(-0.9026733182372587, 0.4303264813400829),
    Complex64::new(0.7430079521351217, 0.669282588346636),
    Complex64::new(-0.6692825883466359, 0.7430079521351218),
    Complex64::new(0.05213170468028332, 0.9986402181802653),
    Complex64::new(-0.9986402181802652, 0.052131704680283594),
    Complex64::new(0.9954807554919269, 0.09496349532963899),
    Complex64::new(-0.09496349532963895, 0.9954807554919269),
    Complex64::new(0.6367618612362842, 0.7710605242618137),
    Complex64::new(-0.7710605242618136, 0.6367618612362844),
    Complex64::new(0.8833633386657316, 0.4686888220358279),
    Complex64::new(-0.4686888220358277, 0.8833633386657317),
    Complex64::new(0.2932191626942587, 0.9560452513499964),
    Complex64::new(-0.9560452513499963, 0.29321916269425896),
    Complex64::new(0.9578264130275329, 0.2873474595447295),
    Complex64::new(-0.28734745954472946, 0.9578264130275329),
    Complex64::new(0.47410021465055, 0.8804708890521608),
    Complex64::new(-0.8804708890521608, 0.4741002146505501),
    Complex64::new(0.7749531065948739, 0.6320187359398091),
    Complex64::new(-0.632018735939809, 0.7749531065948739),
    Complex64::new(0.10106986275482788, 0.9948793307948056),
    Complex64::new(-0.9948793307948056, 0.10106986275482793),
    Complex64::new(0.9813791933137546, 0.19208039704989244),
    Complex64::new(-0.19208039704989227, 0.9813791933137546),
    Complex64::new(0.5581185312205561, 0.829761233794523),
    Complex64::new(-0.8297612337945229, 0.5581185312205563),
    Complex64::new(0.8331701647019132, 0.5530167055800275),
    Complex64::new(-0.5530167055800274, 0.8331701647019133),
    Complex64::new(0.19809841071795373, 0.9801821359681173),
    Complex64::new(-0.9801821359681173, 0.1980984107179538),
    Complex64::new(0.9250492407826776, 0.37984720892405116),
    Complex64::new(-0.379847208924051, 0.9250492407826777),
    Complex64::new(0.385516053843919, 0.9227011283338785),
    Complex64::new(-0.9227011283338786, 0.38551605384391885),
    Complex64::new(0.7092728264388657, 0.7049340803759049),
    Complex64::new(-0.7049340803759049, 0.7092728264388656),
    Complex64::new(0.003067956762966138, 0.9999952938095762),
    Complex64::new(-0.9999952938095762, 0.003067956762965977),
];

impl FastFft for Polynomial<Complex64> {
    type Field = Complex64;
    fn fft_inplace(&mut self) {
        Complex64::fft(&mut self.coefficients, &COMPLEX_BITREVERSED_POWERS_1024);
    }

    fn ifft_inplace(&mut self) {
        let n = self.coefficients.len();
        let psi_inv_rev = &COMPLEX_BITREVERSED_POWERS_1024
            .iter()
            .take(n)
            .map(|c| Complex64::new(c.re, -c.im))
            .collect_vec();
        let ninv = Complex64::new(1.0 / (n as f64), 0.0);
        Complex64::ifft(&mut self.coefficients, psi_inv_rev, ninv);
    }

    fn merge_fft(a: &Self, b: &Self) -> Self {
        Self {
            coefficients: Self::Field::merge_fft(
                &a.coefficients,
                &b.coefficients,
                &COMPLEX_BITREVERSED_POWERS_1024,
            ),
        }
    }

    fn split_fft(&self) -> (Self, Self) {
        let n = self.coefficients.len();
        let psi_inv_rev = &COMPLEX_BITREVERSED_POWERS_1024
            .iter()
            .take(n)
            .map(|c| Complex64::new(c.re, -c.im))
            .collect_vec();
        let (a, b) = Self::Field::split_fft(&self.coefficients, psi_inv_rev);
        (Self { coefficients: a }, Self { coefficients: b })
    }
}

type ComplexFP = Complex<FixedPoint64>;

lazy_static! {
    static ref FP_BITREVERSED_POWERS_1024: Vec<ComplexFP> =
        ComplexFP::bitreversed_powers(1024);
}

impl FastFft for Polynomial<ComplexFP> {
    type Field = ComplexFP;

    fn fft_inplace(&mut self) {
        ComplexFP::fft(&mut self.coefficients, &FP_BITREVERSED_POWERS_1024);
    }

    fn ifft_inplace(&mut self) {
        let n = self.coefficients.len();
        let psi_inv_rev = FP_BITREVERSED_POWERS_1024
            .iter()
            .take(n)
            .map(|c| Complex::new(c.re, -c.im))
            .collect_vec();
        let ninv = Complex::new(
            FixedPoint64::ONE / FixedPoint64::from(n as i32),
            FixedPoint64::ZERO,
        );
        ComplexFP::ifft(&mut self.coefficients, &psi_inv_rev, ninv);
    }

    fn merge_fft(a: &Self, b: &Self) -> Self {
        Self {
            coefficients: ComplexFP::merge_fft(
                &a.coefficients,
                &b.coefficients,
                &FP_BITREVERSED_POWERS_1024,
            ),
        }
    }

    fn split_fft(&self) -> (Self, Self) {
        let n = self.coefficients.len();
        let psi_inv_rev = FP_BITREVERSED_POWERS_1024
            .iter()
            .take(n)
            .map(|c| Complex::new(c.re, -c.im))
            .collect_vec();
        let (a, b) = ComplexFP::split_fft(&self.coefficients, &psi_inv_rev);
        (Self { coefficients: a }, Self { coefficients: b })
    }
}

type ComplexFixed128 = Complex<FixedPoint128>;

lazy_static! {
    static ref FIXED128_BITREVERSED_POWERS_1024: Vec<ComplexFixed128> =
        ComplexFixed128::bitreversed_powers(1024);
}

impl FastFft for Polynomial<ComplexFixed128> {
    type Field = ComplexFixed128;

    fn fft_inplace(&mut self) {
        ComplexFixed128::fft(&mut self.coefficients, &FIXED128_BITREVERSED_POWERS_1024);
    }

    fn ifft_inplace(&mut self) {
        let n = self.coefficients.len();
        let psi_inv_rev = FIXED128_BITREVERSED_POWERS_1024
            .iter()
            .take(n)
            .map(|c| Complex::new(c.re, -c.im))
            .collect_vec();
        let ninv = Complex::new(
            FixedPoint128::ONE / FixedPoint128::from(n as i64),
            FixedPoint128::ZERO,
        );
        ComplexFixed128::ifft(&mut self.coefficients, &psi_inv_rev, ninv);
    }

    fn merge_fft(a: &Self, b: &Self) -> Self {
        Self {
            coefficients: ComplexFixed128::merge_fft(
                &a.coefficients,
                &b.coefficients,
                &FIXED128_BITREVERSED_POWERS_1024,
            ),
        }
    }

    fn split_fft(&self) -> (Self, Self) {
        let n = self.coefficients.len();
        let psi_inv_rev = FIXED128_BITREVERSED_POWERS_1024
            .iter()
            .take(n)
            .map(|c| Complex::new(c.re, -c.im))
            .collect_vec();
        let (a, b) = ComplexFixed128::split_fft(&self.coefficients, &psi_inv_rev);
        (Self { coefficients: a }, Self { coefficients: b })
    }
}

/// Build the bit-reversed powers `[base^0, base^1, …, base^{N-1}]` of `base` at
/// compile time, in bit-reversed index order — the `const` analogue of
/// [`CyclotomicFourier::bitreversed_powers`].  Used to fold the `Felt` NTT
/// twiddle tables into the binary instead of carrying ~1000 literals each.
const fn felt_bitreversed_powers<const N: usize>(base: Felt) -> [Felt; N] {
    let mut array = [Felt::new(0); N];
    let mut alpha = Felt::new(1);
    let mut i = 0;
    while i < N {
        array[i] = alpha;
        alpha = alpha.multiply(base);
        i += 1;
    }
    // In-place bit reversal (const fn cannot use `[T]::swap`).
    let mut i = 0;
    while i < N {
        let j = crate::cyclotomic_fourier::bitreverse_index(i, N);
        if i < j {
            let tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }
        i += 1;
    }
    array
}

const FELT_BITREVERSED_POWERS_1024: [Felt; 1024] = {
    // Bit-reversed powers of psi, a primitive 2048th root of unity, folded into
    // the binary at compile time.  Verified byte-for-byte against the runtime
    // `CyclotomicFourier` oracle by `felt_const_tables_match_runtime`.
    let psi = Felt::const_primitive_root_of_unity(2048);
    felt_bitreversed_powers::<1024>(psi)
};

const FELT_BITREVERSED_POWERS_INVERSE_1024: [Felt; 1024] = {
    // Bit-reversed powers of psi^{-1}.  psi is a 2048th root of unity, so its
    // inverse is psi^2047.
    let psi = Felt::const_primitive_root_of_unity(2048);
    felt_bitreversed_powers::<1024>(psi.const_pow(2047))
};

/// Inverse twiddle factors for the IFFT of length ≤ 1024, each pre-multiplied
/// by 2⁻¹ mod Q.  Used by the self-normalizing ifft_inplace below.
const FELT_BITREVERSED_POWERS_INVERSE_HALVED_1024: [Felt; 1024] = {
    let src = FELT_BITREVERSED_POWERS_INVERSE_1024;
    let mut result = [Felt::new(0); 1024];
    let mut i = 0;
    while i < 1024 {
        result[i] = src[i].half();
        i += 1;
    }
    result
};

impl FastFft for Polynomial<Felt> {
    type Field = Felt;

    #[profiling]
    fn fft_inplace(&mut self) {
        Felt::fft(&mut self.coefficients, &FELT_BITREVERSED_POWERS_1024);
    }

    #[profiling]
    fn ifft_inplace(&mut self) {
        // Standard inverse-NTT butterfly, but with the n⁻¹ normalization
        // folded in: both butterfly outputs are halved at every stage.
        //
        //   sum  output: a[j]   = (u + v).half()   — Felt::half() uses a
        //                                             cheap shift, not a full
        //                                             Montgomery multiply
        //   diff output: a[j+t] = (u − v) * s      — s is drawn from
        //                                             FELT_BITREVERSED_POWERS_INVERSE_HALVED_1024,
        //                                             which already incorporates
        //                                             the ×2⁻¹ factor
        //
        // Every coefficient passes through exactly one butterfly per stage.
        // After log₂(n) stages each coefficient has been halved log₂(n) times,
        // accumulating a factor of (½)^{log₂n} = n⁻¹.  No separate
        // normalization pass is needed.
        let n = self.coefficients.len();
        let a = &mut self.coefficients;
        let mut t = 1;
        let mut m = n;
        while m > 1 {
            let h = m / 2;
            let mut j1 = 0;
            for i in 0..h {
                let s = FELT_BITREVERSED_POWERS_INVERSE_HALVED_1024[h + i];
                for j in j1..j1 + t {
                    let u = a[j];
                    let v = a[j + t];
                    a[j] = (u + v).half();
                    a[j + t] = (u - v) * s;
                }
                j1 += 2 * t;
            }
            t <<= 1;
            m >>= 1;
        }
    }

    fn merge_fft(a: &Self, b: &Self) -> Self {
        Self {
            coefficients: Self::Field::merge_fft(
                &a.coefficients,
                &b.coefficients,
                &FELT_BITREVERSED_POWERS_1024,
            ),
        }
    }

    fn split_fft(&self) -> (Self, Self) {
        let (a, b) =
            Self::Field::split_fft(&self.coefficients, &FELT_BITREVERSED_POWERS_INVERSE_1024);
        (Self { coefficients: a }, Self { coefficients: b })
    }
}

/// Const bit-reversed powers of `base` for an `FpField` NTT of length `N` — the
/// `const` analogue of [`CyclotomicFourier::bitreversed_powers`], used to fold
/// the `U32Field` twiddle tables into the binary instead of carrying ~1000
/// literals each.  Verified against the runtime oracle by
/// `u32_field_bitreversed_powers_is_correct` and `u32_field_ninv_is_correct`.
const fn fpfield_bitreversed_powers<const Q: u32, const N: usize>(
    base: FpField<Q>,
) -> [FpField<Q>; N] {
    let mut array = [FpField::<Q>::new(0); N];
    let mut alpha = FpField::<Q>::new(1);
    let mut i = 0;
    while i < N {
        array[i] = alpha;
        alpha = alpha.multiply(base);
        i += 1;
    }
    // In-place bit reversal (const fn cannot use `[T]::swap`).
    let mut i = 0;
    while i < N {
        let j = crate::cyclotomic_fourier::bitreverse_index(i, N);
        if i < j {
            let tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }
        i += 1;
    }
    array
}

/// Const `n^{-1}` in Montgomery form, the final scaling for the `FpField` iNTT.
const fn fpfield_ninv<const Q: u32>(n: u32) -> FpField<Q> {
    FpField::<Q>::new(n).pow((Q - 2) as u64)
}

const U32_FIELD_PSI_REV_1024: [U32Field; 1024] = {
    let psi = U32Field::primitive_nth_root_of_unity(2048);
    fpfield_bitreversed_powers(psi)
};

const U32_FIELD_PSI_REV_INV_1024: [U32Field; 1024] = {
    // psi is a 2048th root of unity, so its inverse is psi^2047.
    let psi = U32Field::primitive_nth_root_of_unity(2048);
    fpfield_bitreversed_powers(psi.pow(2047))
};

const U32_FIELD_NINV_2: U32Field = fpfield_ninv(2);
const U32_FIELD_NINV_4: U32Field = fpfield_ninv(4);
const U32_FIELD_NINV_8: U32Field = fpfield_ninv(8);
const U32_FIELD_NINV_16: U32Field = fpfield_ninv(16);
const U32_FIELD_NINV_32: U32Field = fpfield_ninv(32);
const U32_FIELD_NINV_64: U32Field = fpfield_ninv(64);
const U32_FIELD_NINV_128: U32Field = fpfield_ninv(128);
const U32_FIELD_NINV_256: U32Field = fpfield_ninv(256);
const U32_FIELD_NINV_512: U32Field = fpfield_ninv(512);
const U32_FIELD_NINV_1024: U32Field = fpfield_ninv(1024);

impl FastFft for Polynomial<U32Field> {
    type Field = U32Field;

    fn fft_inplace(&mut self) {
        U32Field::fft(&mut self.coefficients, &U32_FIELD_PSI_REV_1024);
    }

    fn merge_fft(a: &Self, b: &Self) -> Self {
        Self {
            coefficients: U32Field::merge_fft(
                &a.coefficients,
                &b.coefficients,
                &U32_FIELD_PSI_REV_1024,
            ),
        }
    }

    fn split_fft(&self) -> (Self, Self) {
        let (a, b) = U32Field::split_fft(&self.coefficients, &U32_FIELD_PSI_REV_INV_1024);
        (Self { coefficients: a }, Self { coefficients: b })
    }

    fn ifft_inplace(&mut self) {
        let n = self.coefficients.len();
        let ninv = match n {
            2 => U32_FIELD_NINV_2,
            4 => U32_FIELD_NINV_4,
            8 => U32_FIELD_NINV_8,
            16 => U32_FIELD_NINV_16,
            32 => U32_FIELD_NINV_32,
            64 => U32_FIELD_NINV_64,
            128 => U32_FIELD_NINV_128,
            256 => U32_FIELD_NINV_256,
            512 => U32_FIELD_NINV_512,
            1024 => U32_FIELD_NINV_1024,
            _ => unreachable!(),
        };
        U32Field::ifft(&mut self.coefficients, &U32_FIELD_PSI_REV_INV_1024, ninv);
    }
}

#[cfg(test)]
mod test {
    use itertools::Itertools;
    use num::One;

    use crate::{
        cyclotomic_fourier::CyclotomicFourier,
        fast_fft::{
            U32_FIELD_NINV_1024, U32_FIELD_NINV_128, U32_FIELD_NINV_16, U32_FIELD_NINV_2,
            U32_FIELD_NINV_256, U32_FIELD_NINV_32, U32_FIELD_NINV_4, U32_FIELD_NINV_512,
            U32_FIELD_NINV_64, U32_FIELD_NINV_8,
        },
        inverse::Inverse,
        U32Field,
    };

    use super::{U32_FIELD_PSI_REV_1024, U32_FIELD_PSI_REV_INV_1024};

    /// Pin the compile-time `Felt` NTT twiddle tables to the independent runtime
    /// `CyclotomicFourier` oracle, so the `const fn` regeneration can never drift
    /// from the reference implementation.
    #[test]
    fn felt_const_tables_match_runtime() {
        use super::{FELT_BITREVERSED_POWERS_1024, FELT_BITREVERSED_POWERS_INVERSE_1024};
        use crate::falcon_field::Felt;

        assert_eq!(
            FELT_BITREVERSED_POWERS_1024.to_vec(),
            Felt::bitreversed_powers(1024)
        );
        assert_eq!(
            FELT_BITREVERSED_POWERS_INVERSE_1024.to_vec(),
            Felt::bitreversed_powers_inverse(1024)
        );
    }

    #[test]
    fn u32_field_bitreversed_powers_is_correct() {
        let print_nicely = |v: &[U32Field]| {
            format!(
                "[{}]",
                v.iter()
                    .map(|e| format!("U32Field({})", e.value()))
                    .join(", ")
            )
        };
        let assert_or_print_nicely = |lhs: &[U32Field], rhs: Vec<U32Field>| {
            assert_eq!(lhs.to_vec(), rhs, "Should be: {}", print_nicely(&rhs));
        };
        for logn in 1..=10 {
            assert_or_print_nicely(
                &U32_FIELD_PSI_REV_1024[0..(1 << logn)],
                U32Field::bitreversed_powers(1 << logn),
            );
            assert_or_print_nicely(
                &U32_FIELD_PSI_REV_INV_1024[0..(1 << logn)],
                U32Field::bitreversed_powers_inverse(1 << logn),
            );
        }
    }

    #[test]
    fn u32_field_ninv_is_correct() {
        let mut powers_of_two_inverse = vec![];
        let two_inverse = U32Field::new(2).inverse_or_zero();
        let mut acc = two_inverse;
        for _ in 0..10 {
            powers_of_two_inverse.push(acc);
            acc *= two_inverse;
        }
        assert_eq!(
            powers_of_two_inverse,
            vec![
                U32_FIELD_NINV_2,
                U32_FIELD_NINV_4,
                U32_FIELD_NINV_8,
                U32_FIELD_NINV_16,
                U32_FIELD_NINV_32,
                U32_FIELD_NINV_64,
                U32_FIELD_NINV_128,
                U32_FIELD_NINV_256,
                U32_FIELD_NINV_512,
                U32_FIELD_NINV_1024,
            ]
        );
        assert_eq!(
            U32Field::new(2) * U32_FIELD_NINV_2,
            U32Field::one(),
            "2 inv is wrong"
        );
        assert_eq!(
            U32Field::new(4) * U32_FIELD_NINV_4,
            U32Field::one(),
            "4 inv is wrong"
        );
        assert_eq!(
            U32Field::new(8) * U32_FIELD_NINV_8,
            U32Field::one(),
            "8 inv is wrong; should be: {}",
            U32Field::new(8).inverse_or_zero()
        );
        assert_eq!(
            U32Field::new(16) * U32_FIELD_NINV_16,
            U32Field::one(),
            "16 inv is wrong; should be: {}",
            U32Field::new(16).inverse_or_zero()
        );
        assert_eq!(
            U32Field::new(32) * U32_FIELD_NINV_32,
            U32Field::one(),
            "32 inv is wrong; should be: {}",
            U32Field::new(32).inverse_or_zero()
        );
        assert_eq!(
            U32Field::new(64) * U32_FIELD_NINV_64,
            U32Field::one(),
            "64 inv is wrong; should be: {}",
            U32Field::new(64).inverse_or_zero()
        );
        assert_eq!(
            U32Field::new(128) * U32_FIELD_NINV_128,
            U32Field::one(),
            "128 inv is wrong; should be: {}",
            U32Field::new(128).inverse_or_zero()
        );
        assert_eq!(
            U32Field::new(256) * U32_FIELD_NINV_256,
            U32Field::one(),
            "256 inv is wrong; should be: {}",
            U32Field::new(256).inverse_or_zero()
        );
        assert_eq!(
            U32Field::new(512) * U32_FIELD_NINV_512,
            U32Field::one(),
            "512 inv is wrong; should be: {}",
            U32Field::new(512).inverse_or_zero()
        );
        assert_eq!(
            U32Field::new(1024) * U32_FIELD_NINV_1024,
            U32Field::one(),
            "1024 inv is wrong; should be: {}",
            U32Field::new(1024).inverse_or_zero()
        );
    }
}