fft

Documentation

Index

• func BitReverse(v []field.Element)
• func BitReverseExt(v []fext.Element)
• func GetCoset(N, r, numCoset int) (cos, cosInv, cosBR, cosInvBR []field.Element)
• func GetOmega(domainSize int) field.Element
• func GetTwiddleForDomainOfSize(domainSize int) (twid, twidInvs [][]field.Element)
• type Decimation
• type Domain
  • func NewDomain(m int) *Domain
  • func (domain *Domain) FFT(a []field.Element, decimation Decimation, opts ...Option)
  • func (domain *Domain) FFTExt(a []fext.Element, decimation Decimation, opts ...Option)
  • func (domain *Domain) FFTInverse(a []field.Element, decimation Decimation, opts ...Option)
  • func (domain *Domain) FFTInverseExt(a []fext.Element, decimation Decimation, opts ...Option)
  • func (dom *Domain) WithCoset() *Domain
  • func (dom *Domain) WithCustomCoset(r, numcoset int) *Domain
• type Option
  • func EmptyOption() Option
  • func OnCoset() Option
  • func WithNbTasks(nbTasks int) Option

Functions

func BitReverse

func BitReverse(v []field.Element)

BitReverse applies the bit-reversal permutation to v. len(v) must be a power of 2

func BitReverseExt

func BitReverseExt(v []fext.Element)

BitReverseExt applies the bit-reversal permutation to v. len(v) must be a power of 2

func GetCoset

func GetCoset(N, r, numCoset int) (cos, cosInv, cosBR, cosInvBR []field.Element)

Find the position of the coset table

Let H be the domain of "N" root of unity
Let Hr be the supergroup of "Nr" roots of unity.
Let gr be a generator of Hr, and g = g^r the generator for H
Let a be the multiplicative generator of F^*

`CosetID` returns a coset table for the coset a*gr^{numCoset}*H

* N the size of the cosets
* r the ratio
* numCoset, the ID of the coset in the given ratio

func GetOmega

func GetOmega(domainSize int) field.Element

Returns a generator for a domain of application with the requested size. Omega is a root of unity which generates the domain of evaluation of the constraint.

func GetTwiddleForDomainOfSize

func GetTwiddleForDomainOfSize(domainSize int) (twid, twidInvs [][]field.Element)

Returns the twiddles for a domain of size `n`

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         field.Element
	Generator              field.Element
	GeneratorInv           field.Element
	FrMultiplicativeGen    field.Element // generator of Fr*
	FrMultiplicativeGenInv field.Element

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

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

	// CosetTable u*<1,g,..,g^(n-1)>
	CosetTable         []field.Element
	CosetTableReversed []field.Element // optional, this is computed on demand at the creation of the domain

	// CosetTable[i][j] = domain.Generator(i-th)SqrtInv ^ j
	CosetTableInv         []field.Element
	CosetTableInvReversed []field.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 int) *Domain

Creates a domain without a coset

func (*Domain) FFT

func (domain *Domain) FFT(a []field.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 if coset if set, the FFT(a) returns the evaluation of a on a coset.

func (*Domain) FFTExt

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

func (*Domain) FFTInverse

func (domain *Domain) FFTInverse(a []field.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) FFTInverseExt

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

FFTInverseExt 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) WithCoset

func (dom *Domain) WithCoset() *Domain

Equip the current domain with a coset shifted by the multiplicative generator

func (*Domain) WithCustomCoset

func (dom *Domain) WithCustomCoset(r, numcoset int) *Domain

Equipe the current domain with a custom coset obtained as explained in the doc of `GetCoset`

type Option

type Option func(fftConfig) 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 EmptyOption

func EmptyOption() Option

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.