FLINT3.7.0-dev
/

sd_fft_ctx_w, sd_fft_ctx_w2, sd_fft_ctx_w2inv

Synopsis#include <flint/fft_small.h>
double sd_fft_ctx_w(const sd_fft_ctx_t Q, ulong j)source
double sd_fft_ctx_w2(const sd_fft_ctx_t Q, ulong j)source
double sd_fft_ctx_w2inv(const sd_fft_ctx_t Q, ulong j)source

Return the root of unity wjw_j, w2jw_{2j}, and −w2j−1-w_{2j}^{-1} modulo pp, as integers in [−p/2,p/2][-p/2, p/2]. Here w0=1w_0 = 1 and, for 2k−1≤j<2k2^{k-1} \le j < 2^k, wj=ωrw_j = \omega^{r} where ω\omega is a primitive 2k2^k-th root of unity and rr is jj with its kk bits reversed; the roots for different kk are chosen compatibly, ω2k=ω2k+12\omega_{2^k} = \omega_{2^{k+1}}^2. The tables must cover the index.

So w0,w1,w2,w3,…=1,−1,ω4,−ω4,ω8,ω85,ω83,ω87,…w_0, w_1, w_2, w_3, \ldots = 1, -1, \omega_4, -\omega_4, \omega_8, \omega_8^5, \omega_8^3, \omega_8^7, \ldots, and the first 2L2^L of them are the 2L2^L-th roots of unity in bit-reversed order. Since w2j+1=−w2jw_{2j+1} = -w_{2j}, only even indices are stored.

Cite this page

The FLINT team, “sd_fft_ctx_w, sd_fft_ctx_w2, sd_fft_ctx_w2inv (fft_small.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/fft_small/sd_fft_ctx_w.html (generated 2026-11-02).