fft

Documentation

Index

• func BitReverse(a []fr.Element)
• type Decimation
• type Domain
  • func NewDomain(m int) *Domain
  • func (domain *Domain) FFT(a []fr.Element, decimation Decimation)
  • func (domain *Domain) FFTInverse(a []fr.Element, decimation Decimation)

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 {
	Generator        fr.Element
	GeneratorInv     fr.Element
	GeneratorSqRt    fr.Element // generator of 2 adic subgroup of order 2*nb_constraints
	GeneratorSqRtInv fr.Element
	Cardinality      int
	CardinalityInv   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[0] = 1
	// CosetTable[0] = domain.GeneratorSqrt ^ 1
	// CosetTable[1] = domain.GeneratorSqrt ^ 2
	// ...
	// CosetTable = fft.BitReverse(CosetTable)
	CosetTable []fr.Element

	// CosetTableInv[0] = 1
	// CosetTableInv[0] = domain.GeneratorSqrtInv ^ 1
	// CosetTableInv[1] = domain.GeneratorSqrtInv ^ 2
	// ...
	// CosetTableInv = fft.BitReverse(CosetTableInv)
	CosetTableInv []fr.Element
}

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

func NewDomain

func NewDomain(m int) *Domain

NewDomain returns a subgroup with a power of 2 cardinality cardinality >= m compute a field element of order 2x and store it in GeneratorSqRt all other values can be derived from x, GeneratorSqrt

func (*Domain) FFT

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

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 len(a) must be a power of 2, and w must be a len(a)th root of unity in field F.

func (*Domain) FFTInverse

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

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 len(a) must be a power of 2, and w must be a len(a)th root of unity in field F.