Function interpolate_ntt 

pub fn interpolate_ntt<B, T>(io: &mut [T])
where
    B: Elem + RootsOfUnity,
    T: Copy + Mul<B, Output = T> + Add<Output = T> + Sub<Output = T>,

Perform a reverse butterfly transform of a buffer of (1 << n) numbers. The result of this computation is a discrete Fourier transform, but with changed indices. This is described here. The output of rev_butterfly(io, n) at index i is the sum over k from 0 to 2^n-1 of io[k] ROU_REV[n]^(k i’), where i’ is i bit-reversed as an n-bit number and ROU_REV are the ‘reverse’ roots of unity.

As an example, we’ll work through a trace of the rev_butterfly algorithm with n = 3 on a list of length 8. Let w = ROU_REV[3] be the eighth root of unity. We start with

[a0, a1, a2, a3, a4, a5, a6, a7]

After the loop, before the first round of recursive calls, we have

[a0+a4, a1+a5, a2+a6, a3+a7,

a0-a4, a1w-a5w, a2w^2-a6w^2, a3w^3-a7w^3]

After first round of recursive calls, we have

[a0+a4+a2+a6, a1+a5+a3+a7,

a0+a4-a2-a6, a1w^2+a5w^2-a3w^2-a7w^2,

a0-a4+a2w^2-a6w^2, a1w-a5w+a3w^3-a7w^3,

a0-a4-a2w^2+a6w^2, a1w^3-a5w^3-a3w^5+a7w^5]

And after the second round of recursive calls, we have

[a0+a4+a2+a6+a1+a5+a3+a7,

a0+a4+a2+a6-a1-a5-a3-a7,

a0+a4-a2-a6+a1w^2+a5w^2-a3w^2-a7w^2,

a0+a4-a2-a6-a1w^2-a5w^2+a3w^2+a7w^2,

a0-a4+a2w^2-a6w^2+a1w-a5w+a3w^3-a7w^3,

a0-a4+a2w^2-a6w^2-a1w+a5w-a3w^3+a7w^3,

a0-a4-a2w^2+a6w^2+a1w^3-a5w^3+a3w^5-a7w^5,

a0-a4-a2w^2+a6w^2-a1w^3+a5w^3-a3w^5+a7w^5]

Rewriting this, we get

[sum_k ak w^0, sum_k ak w^4k, sum_k ak w^2k, sum_k ak w^6k, sum_k ak w^1k, sum_k ak w^5k, sum_k ak w^3k, sum_k ak w^7k]

The exponent multiplicands in the sum arise from reversing the indices as three-bit numbers. For example, 3 is 011 in binary, which reversed is 110, which is 6. So i’ in the exponent of the index-3 value is 6.