cplib::radix2_fft_root< MMInt64< 4512606826625236993 > > Struct Reference

Specialization of radix2_fft_root for a large FFT-friendly finite prime field. More...

#include <fft.hpp>

Public Types
using	mint = MMInt64< 4512606826625236993 >

Static Public Member Functions
static mint	get (int n)

Detailed Description

Specialization of radix2_fft_root for a large FFT-friendly finite prime field.

Since \(p=4512606826625236993=501\cdot 2^{53}+1\), \(2^n\)-th root of unity exists for \(0\leq n \leq 53\).

This is useful for convolution over \(\mathbb{Z}\) where all terms in the result are bounded by a range smaller than \(p\approx 4.5\times 10^{18}\), so the value modulo \(p\) uniquely determines the value in \(\mathbb{Z}\).

---

The documentation for this struct was generated from the following file:

• src/cplib/conv/fft.hpp