Module cfft

Functions

cfft

fft in place algorithm used to evaluate a polynomial of degree 2^n - 1 in 2^n points. Input must be of size 2^n for some n.

icfft

The inverse fft algorithm used to interpolate 2^n points. Input must be of size 2^n for some n.

order_cfft_result_naive

This function permutes a slice of field elements to order the result of the cfft in the natural way. We call the natural order to [P(x0, y0), P(x1, y1), P(x2, y2), …], where (x0, y0) is the first point of the corresponding coset. The cfft doesn’t return the evaluations in the natural order. For example, if we apply the cfft to 8 coefficients of a polynomial of degree 7 we’ll get the evaluations in this order: [P(x0, y0), P(x2, y2), P(x4, y4), P(x6, y6), P(x7, y7), P(x5, y5), P(x3, y3), P(x1, y1)], where the even indices are found first in ascending order and then the odd indices in descending order. This function permutes the slice [0, 2, 4, 6, 7, 5, 3, 1] into [0, 1, 2, 3, 4, 5, 6, 7]. TODO: This can be optimized by performing in-place value swapping (WIP).

order_icfft_input_naive

This function permutes a slice of field elements to order the input of the icfft in a specific way. For example, if we want to interpolate 8 points we should input them in the icfft in this order: [(x0, y0), (x2, y2), (x4, y4), (x6, y6), (x7, y7), (x5, y5), (x3, y3), (x1, y1)], where the even indices are found first in ascending order and then the odd indices in descending order. This function permutes the slice [0, 1, 2, 3, 4, 5, 6, 7] into [0, 2, 4, 6, 7, 5, 3, 1]. TODO: This can be optimized by performing in-place value swapping (WIP).