Function rug_fft::cooley_tukey_radix_2_intt

pub fn cooley_tukey_radix_2_intt(ys: &mut [Integer], p: &Integer, w: &Integer)

Computes, for i in 0..n, x_i such that y_i = sum_{j=0}^{n-1} w^{ij}*x_j, modulo p.

Requires n to be a power of two, and w to be an nth root of unity.

Example

use rug::Integer;
use rug_fft::cooley_tukey_radix_2_intt;

let mut xs = vec![5, 4]
    .into_iter()
    .map(Integer::from)
    .collect::<Vec<_>>();
let p = Integer::from(7);
let w = Integer::from(6);
cooley_tukey_radix_2_intt(&mut xs, &p, &w);
let ys_ex = vec![1, 4]
    .into_iter()
    .map(Integer::from)
    .collect::<Vec<_>>();
assert_eq!(xs, ys_ex);