fft

Documentation

Overview

Package fft provides in-place discrete Fourier transform.

Index

• func BitReverse(a []fr.Element)
• type Decimation
• type Domain
  • func NewDomain(m, depth uint64, precomputeReversedTable bool) *Domain
  • func (domain *Domain) FFT(a []fr.Element, decimation Decimation, coset uint64)
  • func (domain *Domain) FFTInverse(a []fr.Element, decimation Decimation, coset uint64)
  • func (d *Domain) ReadFrom(r io.Reader) (int64, error)
  • func (d *Domain) WriteTo(w io.Writer) (int64, error)

Functions

func BitReverse

func BitReverse(a []fr.Element)

BitReverse applies the bit-reversal permutation to a. len(a) must be a power of 2 (as in every single function in this file)

Types

type Decimation

type Decimation uint8

Decimation is used in the FFT call to select decimation in time or in frequency

const (
	DIT Decimation = iota
	DIF
)

type Domain

type Domain struct {
	Cardinality             uint64
	Depth                   uint64
	PrecomputeReversedTable uint64 // uint64 so it is recognized by the decoder from gnark-crypto
	CardinalityInv          fr.Element
	Generator               fr.Element
	GeneratorInv            fr.Element
	FinerGenerator          fr.Element
	FinerGeneratorInv       fr.Element

	// Twiddles factor for the FFT using Generator for each stage of the recursive FFT
	Twiddles [][]fr.Element

	// Twiddles factor for the FFT using GeneratorInv for each stage of the recursive FFT
	TwiddlesInv [][]fr.Element

	// CosetTable[i][j] = domain.Generator(i-th)Sqrt ^ j
	// CosetTable = fft.BitReverse(CosetTable)
	CosetTable         [][]fr.Element
	CosetTableReversed [][]fr.Element // optional, this is computed on demand at the creation of the domain

	// CosetTable[i][j] = domain.Generator(i-th)SqrtInv ^ j
	// CosetTableInv = fft.BitReverse(CosetTableInv)
	CosetTableInv         [][]fr.Element
	CosetTableInvReversed [][]fr.Element // optional, this is computed on demand at the creation of the domain
}

Domain with a power of 2 cardinality compute a field element of order 2x and store it in FinerGenerator all other values can be derived from x, GeneratorSqrt

func NewDomain

func NewDomain(m, depth uint64, precomputeReversedTable bool) *Domain

NewDomain returns a subgroup with a power of 2 cardinality cardinality >= m If depth>0, the Domain will also store a primitive (2**depth)*m root of 1, with associated precomputed data. This allows to perform shifted FFT/FFTInv. If precomputeReversedCosetTable is set, the bit reversed cosetTable/cosetTableInv are precomputed.

example: --------

* NewDomain(m, 0, false) outputs a new domain to perform the fft on Z/mZ. * NewDomain(m, 2, false) outputs a new domain to perform fft on Z/mZ, plus a primitive 2**2*m=4m-th root of 1 and associated data to compute fft/fftinv on the cosets of (Z/4mZ)/(Z/mZ).

func (*Domain) FFT

func (domain *Domain) FFT(a []fr.Element, decimation Decimation, coset uint64)

FFT computes (recursively) the discrete Fourier transform of a and stores the result in a if decimation == DIT (decimation in time), the input must be in bit-reversed order if decimation == DIF (decimation in frequency), the output will be in bit-reversed order coset sets the shift of the fft (0 = no shift, standard fft) len(a) must be a power of 2, and w must be a len(a)th root of unity in field F.

example: ------- domain := NewDomain(m, 2) --> contains precomputed data for Z/mZ, and Z/4mZ FFT(pol, DIT, 1) --> evaluates pol on the coset 1 in (Z/4mZ)/(Z/mZ)

func (*Domain) FFTInverse

func (domain *Domain) FFTInverse(a []fr.Element, decimation Decimation, coset uint64)

FFTInverse computes (recursively) the inverse discrete Fourier transform of a and stores the result in a if decimation == DIT (decimation in time), the input must be in bit-reversed order if decimation == DIF (decimation in frequency), the output will be in bit-reversed order coset sets the shift of the fft (0 = no shift, standard fft) len(a) must be a power of 2, and w must be a len(a)th root of unity in field F.

func (*Domain) ReadFrom

func (d *Domain) ReadFrom(r io.Reader) (int64, error)

ReadFrom attempts to decode a domain from Reader

func (*Domain) WriteTo

func (d *Domain) WriteTo(w io.Writer) (int64, error)

WriteTo writes a binary representation of the domain (without the precomputed twiddle factors) to the provided writer