fft

Documentation

Overview

Package fft provides in-place discrete Fourier transform.

Index

• func BitReverse(a []fr.Element)
• func Generator(m uint64) (fr.Element, error)
• type Decimation
• type Domain
  • func NewDomain(m uint64, shift ...fr.Element) *Domain
  • func (domain *Domain) FFT(a []fr.Element, decimation Decimation, opts ...Option)
  • func (domain *Domain) FFTInverse(a []fr.Element, decimation Decimation, opts ...Option)
  • func (d *Domain) ReadFrom(r io.Reader) (int64, error)
  • func (d *Domain) WriteTo(w io.Writer) (int64, error)
• type Option
  • func OnCoset() Option
  • func WithNbTasks(nbTasks int) Option

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)

func Generator

func Generator(m uint64) (fr.Element, error)

Generator returns a generator for Z/2^(log(m))Z or an error if m is too big (required root of unity doesn't exist)

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, shift ...fr.Element) *Domain

NewDomain returns a subgroup with a power of 2 cardinality cardinality >= m shift: when specified, it's the element by which the set of root of unity is shifted.

func (*Domain) FFT

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

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

func (*Domain) FFTInverse

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

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

type Option

type Option func(*fftConfig)

Option defines option for altering the behavior of FFT methods. See the descriptions of functions returning instances of this type for particular options.

func OnCoset

func OnCoset() Option

OnCoset if provided, FFT(a) returns the evaluation of a on a coset.

func WithNbTasks

func WithNbTasks(nbTasks int) Option

WithNbTasks sets the max number of task (go routine) to spawn. Must be between 1 and 512.