fft

Documentation

Overview

Package fft provides in-place discrete Fourier transform.

Index

• func BitReverse(a []fr.Element)
• type Decimation
• type Domain
  • func NewDomain(m uint64) *Domain
  • func (domain *Domain) FFT(a []fr.Element, decimation Decimation, coset ...bool)
  • func (domain *Domain) FFTInverse(a []fr.Element, decimation Decimation, coset ...bool)
  • 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
	CardinalityInv         fr.Element
	Generator              fr.Element
	GeneratorInv           fr.Element
	FrMultiplicativeGen    fr.Element // generator of Fr*
	FrMultiplicativeGenInv 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 u*<1,g,..,g^(n-1)>
	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         []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 uint64) *Domain

NewDomain returns a subgroup with a power of 2 cardinality cardinality >= m

func (*Domain) FFT

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

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 if coset if set, the FFT(a) returns the evaluation of a on a coset.

func (*Domain) FFTInverse

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

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