Struct AdditiveFft 

pub struct AdditiveFft<F> { /* private fields */ }

In-place additive FFT over a 2^log_n subspace of a binary tower field.

Examples

use hekate_math::{AdditiveFft, Block16, Flat, HardwareField};

let log_n = 10;
let fft = AdditiveFft::<Block16>::new(log_n)?;

let coeffs: Vec<Flat<Block16>> = (0..1u32 << log_n)
    .map(|i| Block16::from(i).to_hardware())
    .collect();

let mut data = coeffs.clone();
fft.forward_scalar(&mut data)?;
fft.inverse_scalar(&mut data)?;

assert_eq!(data, coeffs);

Implementations

impl<F: BinaryFieldExtras + HardwareField> AdditiveFft<F>

pub fn new(log_n: u32) -> Result<Self, FftError>

Derives the Cantor basis (via solve_quadratic) and the twiddle schedule for transform size 2^log_n.

Errors

BadLogN unless log_n is in 1..=min(F::BITS, usize::BITS - 1) and F admits a Cantor basis of that size; TwiddleAlloc if the 2^(log_n-1)-entry twiddle table cannot be allocated.

pub fn forward_scalar(&self, data: &mut [Flat<F>]) -> Result<(), FftError>

Evaluates in place: novel-basis coefficients of f become data[j] = f(point(j)), point as in CantorBasis::point.

Errors

BadLength unless data.len() == 2^log_n.

pub fn inverse_scalar(&self, data: &mut [Flat<F>]) -> Result<(), FftError>

Interpolates in place: the inverse of Self::forward_scalar.

Errors

BadLength unless data.len() == 2^log_n.

pub fn forward_coset_scalar( &self, data: &mut [Flat<F>], offset: Flat<F>, ) -> Result<(), FftError>

Evaluates in place on the coset offset + W_log_n: data[j] = f(offset + point(j)).

Errors

BadLength unless data.len() == 2^log_n.

pub fn inverse_coset_scalar( &self, data: &mut [Flat<F>], offset: Flat<F>, ) -> Result<(), FftError>

Interpolates in place: the inverse of Self::forward_coset_scalar at the same offset.

Errors

BadLength unless data.len() == 2^log_n.

pub fn forward(&self, data: &mut [PackedFlat<F>]) -> Result<(), FftError>

Runs Self::forward_scalar on each of the F::WIDTH lanes: lane l of data[j] is element j of input l.

Errors

BadLength unless data.len() == 2^log_n.

pub fn inverse(&self, data: &mut [PackedFlat<F>]) -> Result<(), FftError>

Runs Self::inverse_scalar on each of the F::WIDTH lanes.

Errors

BadLength unless data.len() == 2^log_n.

pub fn forward_coset( &self, data: &mut [PackedFlat<F>], offset: Flat<F>, ) -> Result<(), FftError>

Runs Self::forward_coset_scalar on each of the F::WIDTH lanes.

Errors

BadLength unless data.len() == 2^log_n.

pub fn inverse_coset( &self, data: &mut [PackedFlat<F>], offset: Flat<F>, ) -> Result<(), FftError>

Runs Self::inverse_coset_scalar on each of the F::WIDTH lanes.

Errors

BadLength unless data.len() == 2^log_n.