FLINT3.7.0-dev
/

_gr_dft_mul_root, _gr_dft_mul_const

Synopsis#include <flint/gr_dft.h>
int _gr_dft_mul_root(gr_ptr res, gr_srcptr x, ulong e, int inverse, gr_ptr rtmp, const gr_dft_pre_t P)source
int _gr_dft_mul_const(gr_ptr res, gr_srcptr x, gr_srcptr w, gr_srcptr wtab3, gr_ptr rtmp, const gr_dft_pre_t P)source

The first sets res to wexw^e x (or w−exw^{-e} x if inverse is set), for 0≤e<n0 \le e < n and a plan that stores the full root table. Radix-2 plans, and split-radix plans in complex mode, of length at least 4 and without Karatsuba tables store per-stage tables instead. The second sets res to wxw x for a plan constant ww, using the complex Karatsuba entry wtab3 (three real elements cc, d−cd - c, d+cd + c for w=c+diw = c + di) if it is not NULL. res must not alias x. In complex mode, rtmp is an initialised element of the real ring used as scratch space.

In complex mode, _gr_dft_mul_root multiplies by the powers ±1\pm 1, ±i\pm i at no cost and by the odd multiples of wn/8w^{n/8}, which have the form c(1±i)c(1 \pm i), with two real multiplications. Other roots take three real multiplications with the Karatsuba tables or one complex multiplication without them.

Cite this page

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