fft_butterfly_twiddle, ifft_butterfly_twiddle
Synopsis
#include <flint/fft.h>void fft_butterfly_twiddle(mp_limb_t * u, mp_limb_t * v, mp_limb_t * s, mp_limb_t * t, mp_size_t limbs, flint_bitcnt_t b1, flint_bitcnt_t b2)sourcevoid ifft_butterfly_twiddle(mp_limb_t * u, mp_limb_t * v, mp_limb_t * s, mp_limb_t * t, mp_size_t limbs, flint_bitcnt_t b1, flint_bitcnt_t b2)sourcefft_butterfly_twiddle sets u = 2^{b_1}(s + t) and v = 2^{b_2}(s - t). ifft_butterfly_twiddle sets u = 2^{-b_1} s + 2^{-b_2} t and v = 2^{-b_1} s - 2^{-b_2} t, overwriting s and t. Both work modulo 2^N + 1, N = \mathit{limbs} \cdot \mathtt{FLINT\_BITS}, for 0 \le b_1, b_2 < 2N. They form the last layer of the forward and the first layer of the inverse column transforms, with the twiddle factors of the matrix Fourier algorithm merged into the shifts.
Cite this page
The FLINT team, “fft_butterfly_twiddle, ifft_butterfly_twiddle (fft.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/fft/fft_butterfly_twiddle.html (generated 2026-10-20).
@misc{flint-doc-fft-fft-butterfly-twiddle,
author = {{The FLINT team}},
title = {{fft\_butterfly\_twiddle, ifft\_butterfly\_twiddle (fft.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/fft/fft_butterfly_twiddle.html},
note = {Generated 2026-10-20}
}