lambdaworks_math/fft/cpu/
ops.rs

1use crate::{
2    fft::errors::FFTError,
3    field::{
4        element::FieldElement,
5        traits::{IsFFTField, IsField, IsSubFieldOf},
6    },
7};
8
9use super::{bit_reversing::in_place_bit_reverse_permute, fft::in_place_nr_2radix_fft};
10
11/// Executes Fast Fourier Transform over elements of a two-adic finite field `E` and domain in a
12/// subfield `F`. Usually used for fast polynomial evaluation.
13pub fn fft<F: IsFFTField + IsSubFieldOf<E>, E: IsField>(
14    input: &[FieldElement<E>],
15    twiddles: &[FieldElement<F>],
16) -> Result<alloc::vec::Vec<FieldElement<E>>, FFTError> {
17    if !input.len().is_power_of_two() {
18        return Err(FFTError::InputError(input.len()));
19    }
20
21    let mut results = input.to_vec();
22    in_place_nr_2radix_fft(&mut results, twiddles);
23    in_place_bit_reverse_permute(&mut results);
24
25    Ok(results)
26}
lambdaworks_math/fft/cpu/ops.rs

lambdaworks_math/fft/cpu/
ops.rs
