sd_fft_ctx_w, sd_fft_ctx_w2, sd_fft_ctx_w2inv
#include <flint/fft_small.h>double sd_fft_ctx_w(const sd_fft_ctx_t Q, ulong j)sourcedouble sd_fft_ctx_w2(const sd_fft_ctx_t Q, ulong j)sourcedouble sd_fft_ctx_w2inv(const sd_fft_ctx_t Q, ulong j)sourceReturn the root of unity w_j, w_{2j}, and -w_{2j}^{-1} modulo p, as integers in [-p/2, p/2]. Here w_0 = 1 and, for 2^{k-1} \le j < 2^k, w_j = \omega^{r} where \omega is a primitive 2^k-th root of unity and r is j with its k bits reversed; the roots for different k are chosen compatibly, \omega_{2^k} = \omega_{2^{k+1}}^2. The tables must cover the index.
So 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 2^L of them are the 2^L-th roots of unity in bit-reversed order. Since w_{2j+1} = -w_{2j}, only even indices are stored.
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-10-20).
@misc{flint-doc-fft-small-sd-fft-ctx-w,
author = {{The FLINT team}},
title = {{sd\_fft\_ctx\_w, sd\_fft\_ctx\_w2, sd\_fft\_ctx\_w2inv (fft\_small.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/fft_small/sd_fft_ctx_w.html},
note = {Generated 2026-10-20}
}