smartvectors

package
v0.0.0-...-869bcdc Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 24, 2025 License: Apache-2.0 Imports: 15 Imported by: 0

Documentation

Index

Constants

View Source 
const FuzzIteration int = 20000

Variables

This section is empty.

Functions

func BatchInterpolate 

func BatchInterpolate(vs []SmartVector, x field.Element, oncoset ...bool) []field.Element

Batch-evaluate polynomials in Lagrange basis

func Copy 

func Copy(into *SmartVector, x SmartVector)

Copy into a smart-vector, will panic if into is not a regular Mainly used as a sugar for refactoring

func Density 

func Density(v SmartVector) int

Density returns the density of a smart-vector. By density we mean the size of the concrete underlying vectors. This can be used as a proxi for the memory required to store the smart-vector.

func EvalCoeff 

func EvalCoeff(v SmartVector, x field.Element) field.Element

Evaluate a polynomial in coefficient basis

func EvalCoeffBivariate 

func EvalCoeffBivariate(v SmartVector, x field.Element, numCoeffX int, y field.Element) field.Element

func InnerProduct 

func InnerProduct(a, b SmartVector) field.Element

InnerProduct returns a scalar obtained as the inner-product of `a` and `b`.

  • a and b must have the same length, otherwise the function panics

func Interpolate 

func Interpolate(v SmartVector, x field.Element, oncoset ...bool) field.Element

Evaluate a polynomial in Lagrange basis

func IntoGnarkAssignment 

func IntoGnarkAssignment(sv SmartVector) []frontend.Variable

IntoGnarkAssignment converts a smart-vector into a gnark assignment

func IntoRegVec 

func IntoRegVec(s SmartVector) []field.Element

IntoRegVec converts a smart-vector into a normal vec. The resulting vector is always reallocated and can be safely mutated without side-effects on s.

func IntoRegVecExt 

func IntoRegVecExt(s SmartVector) []fext.Element

func Sum 

func Sum(a SmartVector) (res field.Element)

Sum returns the field summation of all the elements contained in the vector

func Window 

func Window(v SmartVector) []field.Element

Window returns the effective window of the vector, if the vector is Padded with zeroes it return the window. Namely, the part without zero pads.

func WindowBase 

func WindowBase(v SmartVector) ([]field.Element, error)

func WindowExt 

func WindowExt(v SmartVector) []fext.Element

Types

type CircularInterval 

type CircularInterval struct {

	// IntervalLen is length of the interval. Meaning the number of points in
	// the interval
	IntervalLen int
	// contains filtered or unexported fields
}

CircularInterval represents an interval over a discretized circle. The discretized circle is assumed to be equipped with an origin point; thus allowing to set a unique coordinate for each point.

  • The intervals are "cardinal": meaning that the largest possible interval is the full-circuit
  • The empty interval is considered as invalid and should never be constructed

func IvalWithFullLen 

func IvalWithFullLen(n int) CircularInterval

IvalWithFullLen returns an interval representing the full-circle.

func IvalWithStartLen 

func IvalWithStartLen(start, len, n int) CircularInterval

IvalWithStartLen constructs an interval by passing the Start, the len and n being the size of the circle.

func IvalWithStartStop 

func IvalWithStartStop(start, stop, n int) CircularInterval

IvalWithStartStop constructs a CircularInterval by using its starting and stopping points.

func SmallestCoverInterval 

func SmallestCoverInterval(intervals []CircularInterval) CircularInterval

Returns the smallest windows that covers the entire set

func (CircularInterval) DoesFullyContain 

func (c CircularInterval) DoesFullyContain(other CircularInterval) bool

DoesFullyContain returns true if `c` fully contains `other`

func (CircularInterval) DoesInclude 

func (c CircularInterval) DoesInclude(p int) bool

Returns true iff `p` is included in the receiver interval

func (CircularInterval) DoesWrapAround 

func (c CircularInterval) DoesWrapAround() bool

DoesWrapAround returns true iff the interval rolls over

func (CircularInterval) IsFullCircle 

func (c CircularInterval) IsFullCircle() bool

IsFullCircle returns true of the interval is the full circle

func (CircularInterval) Start 

func (c CircularInterval) Start() int

Start returns the starting point (included) of the interval

func (CircularInterval) Stop 

func (c CircularInterval) Stop() int

Stop returns the stopping point (excluded) of the interval of the interval

func (CircularInterval) TryOverlapWith 

func (c CircularInterval) TryOverlapWith(other CircularInterval) (ok bool, connected CircularInterval)

TryOverlapWith returns true if the left of `c` touches the right of `other` 

		        c.Start-------------c.Stop
						other.Start---------other.Stop

									OR

	|c.Start|-------------|c.Stop|

    							 |other.Start|---------|other.Stop|

This also include the edge cases where `other.Stop`. Also returns the resulting circular interval obtained by connecting the two.

type Constant 

type Constant struct {
	// contains filtered or unexported fields
}

A constant vector is a vector obtained by repeated "length" time the same value

func NewConstant 

func NewConstant(val field.Element, length int) *Constant

Construct a new "Constant" smart-vector

func (*Constant) DeepCopy 

func (c *Constant) DeepCopy() SmartVector

func (*Constant) Get 

func (r *Constant) Get(n int) field.Element

func (*Constant) GetBase 

func (c *Constant) GetBase(int) (field.Element, error)

Returns an entry of the constant

func (*Constant) GetExt 

func (c *Constant) GetExt(int) fext.Element

func (*Constant) IntoRegVecSaveAlloc 

func (c *Constant) IntoRegVecSaveAlloc() []field.Element

func (*Constant) IntoRegVecSaveAllocBase 

func (c *Constant) IntoRegVecSaveAllocBase() ([]field.Element, error)

Temporary function for code transition

func (*Constant) IntoRegVecSaveAllocExt 

func (c *Constant) IntoRegVecSaveAllocExt() []fext.Element

func (*Constant) Len 

func (c *Constant) Len() int

Return the length of the smart-vector

func (*Constant) Pretty 

func (c *Constant) Pretty() string

func (*Constant) RotateRight 

func (c *Constant) RotateRight(int) SmartVector

Returns a rotated version of the slice

func (*Constant) SubVector 

func (c *Constant) SubVector(start, stop int) SmartVector

Returns a subvector

func (*Constant) Val 

func (c *Constant) Val() field.Element

func (*Constant) WriteInSlice 

func (c *Constant) WriteInSlice(s []field.Element)

Write the constant vector in a slice

func (*Constant) WriteInSliceExt 

func (c *Constant) WriteInSliceExt(s []fext.Element)

type PaddedCircularWindow 

type PaddedCircularWindow struct {
	// contains filtered or unexported fields
}

It's a slice - zero padded up to a certain length - and rotated

func NewPaddedCircularWindow 

func NewPaddedCircularWindow(window []field.Element, paddingVal field.Element, offset, totLen int) *PaddedCircularWindow

Create a new padded circular window vector

func (*PaddedCircularWindow) DeepCopy 

func (w *PaddedCircularWindow) DeepCopy() SmartVector

func (*PaddedCircularWindow) Get 

func (r *PaddedCircularWindow) Get(n int) field.Element

func (*PaddedCircularWindow) GetBase 

func (p *PaddedCircularWindow) GetBase(n int) (field.Element, error)

Returns a queries position

func (*PaddedCircularWindow) GetExt 

func (p *PaddedCircularWindow) GetExt(n int) fext.Element

func (*PaddedCircularWindow) IntoRegVecSaveAlloc 

func (w *PaddedCircularWindow) IntoRegVecSaveAlloc() []field.Element

Converts a smart-vector into a normal vec. The implementation minimizes then number of copies.

func (*PaddedCircularWindow) IntoRegVecSaveAllocBase 

func (w *PaddedCircularWindow) IntoRegVecSaveAllocBase() ([]field.Element, error)

func (*PaddedCircularWindow) IntoRegVecSaveAllocExt 

func (w *PaddedCircularWindow) IntoRegVecSaveAllocExt() []fext.Element

func (*PaddedCircularWindow) Len 

func (p *PaddedCircularWindow) Len() int

Returns the length of the vector

func (*PaddedCircularWindow) Pretty 

func (p *PaddedCircularWindow) Pretty() string

func (*PaddedCircularWindow) RotateRight 

func (p *PaddedCircularWindow) RotateRight(offset int) SmartVector

Rotate the vector

func (*PaddedCircularWindow) SubVector 

func (p *PaddedCircularWindow) SubVector(start, stop int) SmartVector

Extract a subvector from p[Start:Stop), the subvector cannot "roll-over". i.e, we enforce that Start < Stop

func (*PaddedCircularWindow) WriteInSlice 

func (p *PaddedCircularWindow) WriteInSlice(buff []field.Element)

func (*PaddedCircularWindow) WriteInSliceExt 

func (p *PaddedCircularWindow) WriteInSliceExt(buff []fext.Element)

type Pooled 

type Pooled struct {
	Regular
	// contains filtered or unexported fields
}

func AllocFromPool 

func AllocFromPool(pool mempool.MemPool) *Pooled

func (*Pooled) Free 

func (p *Pooled) Free(pool mempool.MemPool)

type Regular 

type Regular []field.Element

It's normal vector in a nutshell

func NewRegular 

func NewRegular(v []field.Element) *Regular

Instanstiate a new regular from a slice. Returns a pointer so that the result can be reused without referencing as a SmartVector.

func (*Regular) DeepCopy 

func (r *Regular) DeepCopy() SmartVector

func (*Regular) Get 

func (r *Regular) Get(n int) field.Element

func (*Regular) GetBase 

func (r *Regular) GetBase(n int) (field.Element, error)

Returns a particular element of the vector

func (*Regular) GetExt 

func (r *Regular) GetExt(n int) fext.Element

func (*Regular) IntoRegVecSaveAlloc 

func (r *Regular) IntoRegVecSaveAlloc() []field.Element

Converts a smart-vector into a normal vec. The implementation minimizes then number of copies.

func (*Regular) IntoRegVecSaveAllocBase 

func (r *Regular) IntoRegVecSaveAllocBase() ([]field.Element, error)

func (*Regular) IntoRegVecSaveAllocExt 

func (r *Regular) IntoRegVecSaveAllocExt() []fext.Element

func (*Regular) Len 

func (r *Regular) Len() int

Returns the length of the regular vector

func (*Regular) Pretty 

func (r *Regular) Pretty() string

func (*Regular) RotateRight 

func (r *Regular) RotateRight(offset int) SmartVector

Rotates the vector into a new one

func (*Regular) SubVector 

func (r *Regular) SubVector(start, stop int) SmartVector

Returns a subvector of the regular

func (*Regular) WriteInSlice 

func (r *Regular) WriteInSlice(s []field.Element)

func (*Regular) WriteInSliceExt 

func (r *Regular) WriteInSliceExt(s []fext.Element)

type Rotated 

type Rotated struct {
	// contains filtered or unexported fields
}

Rotated represents a rotated version of a regular smartvector and also implements the SmartVector interface. Rotated have a very niche use-case in the repository as they are used to help saving FFT operations in the github.com/consensys/linea-monorepo/prover/protocol/compiler/arithmetic.CompileGlobal compiler when the coset evaluation is done over a cyclic rotation of a smart-vector.

Rotated works by abstractly storing the offset and only applying the rotation when the vector is written or sub-vectored. This makes rotations essentially free.

func NewRotated 

func NewRotated(reg Regular, offset int) *Rotated

NewRotated constructs a new Rotated, positive offset means a cyclic left shift.

func (*Rotated) DeepCopy 

func (r *Rotated) DeepCopy() SmartVector

func (*Rotated) Get 

func (r *Rotated) Get(n int) field.Element

func (*Rotated) GetBase 

func (r *Rotated) GetBase(n int) (field.Element, error)

Returns a particular element of the vector

func (*Rotated) GetExt 

func (r *Rotated) GetExt(n int) fext.Element

Returns a particular element of the vector

func (*Rotated) IntoRegVecSaveAlloc 

func (r *Rotated) IntoRegVecSaveAlloc() []field.Element

func (*Rotated) IntoRegVecSaveAllocBase 

func (r *Rotated) IntoRegVecSaveAllocBase() ([]field.Element, error)

func (*Rotated) IntoRegVecSaveAllocExt 

func (r *Rotated) IntoRegVecSaveAllocExt() []fext.Element

func (*Rotated) Len 

func (r *Rotated) Len() int

Returns the lenght of the vector

func (*Rotated) Pretty 

func (r *Rotated) Pretty() string

func (*Rotated) RotateRight 

func (r *Rotated) RotateRight(offset int) SmartVector

Rotates the vector into a new one, a positive offset means a left cyclic shift

func (*Rotated) SubVector 

func (r *Rotated) SubVector(start, stop int) SmartVector

Returns a particular element. The subvector is taken at indices [Start, Stop). (Stop being excluded from the span)

func (*Rotated) WriteInSlice 

func (r *Rotated) WriteInSlice(s []field.Element)

func (*Rotated) WriteInSliceExt 

func (r *Rotated) WriteInSliceExt(s []fext.Element)

type SmartVector 

type SmartVector interface {
	// Len returns the length of the SmartVector
	Len() int
	// Get returns an entry of the SmartVector at particular position
	GetBase(int) (field.Element, error)
	Get(int) field.Element
	GetExt(int) fext.Element
	// SubVector returns a subvector of the [SmartVector]. It mirrors slice[Start:Stop]
	SubVector(int, int) SmartVector
	// RotateRight cyclically rotates the SmartVector
	RotateRight(int) SmartVector
	// WriteInSlice writes the SmartVector into a slice. The slice must be just
	// as large as [Len] otherwise the function will panic
	WriteInSlice([]field.Element)
	WriteInSliceExt([]fext.Element)
	// Pretty returns a prettified version of the vector, useful for debugging.
	Pretty() string
	// DeepCopy returns a deep-copy of the SmartVector which can be freely
	// mutated without affecting the
	DeepCopy() SmartVector
	// IntoRegVecSaveAlloc converts a smart-vector into a normal vec. The
	// implementation minimizes then number of copies
	IntoRegVecSaveAlloc() []field.Element
	IntoRegVecSaveAllocBase() ([]field.Element, error)
	IntoRegVecSaveAllocExt() []fext.Element
}

SmartVector is an abstraction over vectors of field elements that can be optimized for structured vectors. For instance, if we have a vector of repeated elements we can use smartvectors.NewConstant(x, n) to represent it. This way instead of using n * sizeof(field.Element) memory it will only store the element once. Additionally, every operation performed on it will be sped up with dedicated algorithms.

There are a few precautions to take when implementing or using smart-vectors

  • constructing a zero-length smart-vector should be considered illegal. The reason for such a restriction is tha t
  • although the smart-vectors are not immutable, the user should refrain mutating them after they are created as this may have unintended side effects that are hard to track.

func Add 

func Add(vecs ...SmartVector) SmartVector

Add returns a smart-vector obtained by position-wise adding SmartVector.

  • all inputs `vecs` must have the same size, or the function panics
  • the output smart-vector has the same size as the input vectors
  • if no input vectors are provided, the function panics

func AllocateRegular 

func AllocateRegular(n int) SmartVector

AllocateRegular returns a newly allocated smart-vector

func BatchInvert 

func BatchInvert(x SmartVector) SmartVector

BatchInvert performs the batch inverse operation over a SmartVector and returns a SmartVector of the same type. When an input element is zero, the function returns 0 at the corresponding position.

func FFT 

func FFT(v SmartVector, decimation fft.Decimation, bitReverse bool, cosetRatio int, cosetID int, pool mempool.MemPool) SmartVector

Compute the FFT of a vector Decimation:

  • Either DIT : input in bit-reverse order - output in normal order
  • Or DIF : input in normal order - output in bit reversed order

BitReverse:

  • If set to true, this cancels the decimation and forces : input normal order - output normal order

CosetRatio > CosetID:

  • Specifies on which coset to perform the operation
  • 0, 0 to assert that the transformation should not be done over a coset

func FFTInverse 

func FFTInverse(v SmartVector, decimation fft.Decimation, bitReverse bool, cosetRatio int, cosetID int, pool mempool.MemPool) SmartVector

Compute the FFT inverse of a vector Decimation:

  • Either DIT : input in bit-reverse order - output in normal order
  • Or DIF : input in normal order - output in bit reversed order

BitReverse:

  • If set to true, this cancels the decimation and forces : input normal order - output normal order

CosetRatio > CosetID:

  • Specifies on which coset to perform the operation
  • 0, 0 to assert that the transformation should not be done over a coset

func ForTest 

func ForTest(xs ...int) SmartVector

ForTest returns a witness from a explicit litteral assignement

func IsZero 

func IsZero(x SmartVector) SmartVector

IsZero returns a SmartVector z with the same type of structure than x such that x[i] = 0 => z[i] = 1 AND x[i] != 0 => z[i] = 0.

func LeftPadded 

func LeftPadded(v []field.Element, padding field.Element, targetLen int) SmartVector

LeftPadded creates a new padded vector (padded on the left)

func LeftZeroPadded 

func LeftZeroPadded(v []field.Element, targetLen int) SmartVector

LeftZeroPadded creates a new vector (padded on the left)

func LinComb 

func LinComb(coeffs []int, svecs []SmartVector, p ...mempool.MemPool) SmartVector

LinComb computes a linear combination of the given vectors with integer coefficients.

  • The function panics if provided SmartVector of different lengths
  • The function panics if svecs is empty
  • The function panics if the length of coeffs does not match the length of svecs

func Mul 

func Mul(vecs ...SmartVector) SmartVector

Mul returns a smart-vector obtained by position-wise multiplying SmartVector.

  • all inputs `vecs` must have the same size, or the function panics
  • the output smart-vector has the same size as the input vectors
  • if no input vectors are provided, the function panics

func PolyAdd 

func PolyAdd(a, b SmartVector) SmartVector

Add two vectors representing polynomials in coefficient form. a and b may have different sizes

func PolyEval 

func PolyEval(vecs []SmartVector, x field.Element, p ...mempool.MemPool) (result SmartVector)

PolyEval returns a SmartVector computed as: 

result = vecs[0] + vecs[1] * x + vecs[2] * x^2 + vecs[3] * x^3 + ...

where `x` is a scalar and `vecs[i]` are SmartVector

func PolySub 

func PolySub(a, b SmartVector) SmartVector

func Product 

func Product(exponents []int, svecs []SmartVector, p ...mempool.MemPool) SmartVector

Product computes a product of smart-vectors with integer exponents

  • The function panics if provided SmartVector of different lengths
  • The function panics if svecs is empty
  • The function panics if the length of exponents does not match the length of svecs

func PseudoRand 

func PseudoRand(rng *rand.Rand, n int) SmartVector

Rand creates a vector with random entries. Used for testing. Should not be used to generate secrets. Takes a math.Rand as input for reproducibility math

func Rand 

func Rand(n int) SmartVector

Rand creates a vector with random entries. Used for testing. Should not be used to generate secrets. Not reproducible.

func RightPadded 

func RightPadded(v []field.Element, padding field.Element, targetLen int) SmartVector

RightPadded creates a new vector (padded on the right)

func RightZeroPadded 

func RightZeroPadded(v []field.Element, targetLen int) SmartVector

RightZeroPadded creates a new vector (padded on the right)

func RuffiniQuoRem 

func RuffiniQuoRem(p SmartVector, q field.Element) (quo SmartVector, rem field.Element)

Ruffini division

  • p polynomial in coefficient form
  • q field.Element, caracterizing the divisor X - q
  • quo quotient polynomial in coefficient form, result will be passed here. quo is truncated of its first entry in the process
  • expected to be at least as large as `p`

- rem, remainder also equals to P(r)

Supports &p == quo

func ScalarMul 

func ScalarMul(vec SmartVector, x field.Element) SmartVector

ScalarMul returns a smart-vector obtained by multiplying a scalar with a SmartVector.

  • the output smart-vector has the same size as the input vector

func SoftRotate 

func SoftRotate(v SmartVector, offset int) SmartVector

SoftRotate converts v into a SmartVector representing the same SmartVector. The function tries to not reallocate the result. This means that changing the v can subsequently affects the result of this function.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.