poly

package
v0.3.0 Latest Latest
Warning

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

 Go to latest Published: Apr 1, 2024 License: Apache-2.0 Imports: 6 Imported by: 0

Documentation

Overview

Package poly implements polynomial and its operations.

Index

Constants

View Source 
const (
	// MinDegree is the minimum degree of polynomial that Evaluator can handle.
	// Currently, this is set to 16, because AVX2 implementation of FFT and inverse FFT
	// handles first/last two loops separately.
	MinDegree = 1 << 4

	// MaxDegree is the maximum degree of polynomial that Evaluator can handle.
	// Currently, this is set to 2^30, because [*FourierEvaluator.PolyMulBinary] trick
	// supports up to 2^30 degree.
	MaxDegree = 1 << 30
)

Variables

This section is empty.

Functions

This section is empty.

Types

type Evaluator 

type Evaluator[T num.Integer] struct {
	// contains filtered or unexported fields
}

Evaluator calculates polynomial algorithms.

Operations usually take two forms: for example,

  • Add(p0, p1) adds p0, p1, allocates a new polynomial to store the result and returns it.
  • AddAssign(p0, p1, pOut) adds p0, p1 and writes the result to pre-allocated pOut without returning.

Note that in most cases, p0, p1, and pOut can overlap. However, for operations that cannot, InPlace methods are implemented separately.

For performance reasons, most methods in this package don't implement bound checks. If length mismatch happens, it may panic or produce wrong results.

func NewEvaluator 

func NewEvaluator[T num.Integer](N int) *Evaluator[T]

NewEvaluator allocates an empty Evaluator with degree N.

Panics when N is not a power of two, or when N is smaller than MinDegree or larger than MaxDegree.

func (*Evaluator[T]) Add 

func (e *Evaluator[T]) Add(p0, p1 Poly[T]) Poly[T]

Add returns p0 + p1.

func (*Evaluator[T]) AddAssign 

func (e *Evaluator[T]) AddAssign(p0, p1, pOut Poly[T])

AddAssign computes pOut = p0 + p1.

func (*Evaluator[T]) Degree 

func (e *Evaluator[T]) Degree() int

Degree returns the degree of polynomial that the evaluator can handle.

func (*Evaluator[T]) MonomialMul 

func (e *Evaluator[T]) MonomialMul(p0 Poly[T], d int) Poly[T]

MonomialMul returns X^d * p0.

func (*Evaluator[T]) MonomialMulAddAssign added in v0.2.5 

func (e *Evaluator[T]) MonomialMulAddAssign(p0 Poly[T], d int, pOut Poly[T])

MonomialMulAddAssign computes pOut += X^d * p0.

p0 and pOut should not overlap.

func (*Evaluator[T]) MonomialMulAssign 

func (e *Evaluator[T]) MonomialMulAssign(p0 Poly[T], d int, pOut Poly[T])

MonomialMulAssign computes pOut = X^d * p0.

p0 and pOut should not overlap. For inplace multiplication, use *Evaluator.MonomialMulInPlace.

func (*Evaluator[T]) MonomialMulInPlace 

func (e *Evaluator[T]) MonomialMulInPlace(p0 Poly[T], d int)

MonomialMulInPlace computes p0 = X^d * p0.

func (*Evaluator[T]) MonomialMulSubAssign added in v0.2.5 

func (e *Evaluator[T]) MonomialMulSubAssign(p0 Poly[T], d int, pOut Poly[T])

MonomialMulSubAssign computes pOut -= X^d * p0.

p0 and pOut should not overlap.

func (*Evaluator[T]) Mul 

func (e *Evaluator[T]) Mul(p0, p1 Poly[T]) Poly[T]

Mul returns p0 * p1.

func (*Evaluator[T]) MulAddAssign 

func (e *Evaluator[T]) MulAddAssign(p0, p1, pOut Poly[T])

MulAddAssign computes pOut += p0 * p1.

func (*Evaluator[T]) MulAssign 

func (e *Evaluator[T]) MulAssign(p0, p1, pOut Poly[T])

MulAssign computes pOut = p0 * p1.

func (*Evaluator[T]) MulSubAssign 

func (e *Evaluator[T]) MulSubAssign(p0, p1, pOut Poly[T])

MulSubAssign computes pOut -= p0 * p1.

func (*Evaluator[T]) Neg 

func (e *Evaluator[T]) Neg(p0 Poly[T]) Poly[T]

Neg returns pOut = -p0.

func (*Evaluator[T]) NegAssign 

func (e *Evaluator[T]) NegAssign(p0, pOut Poly[T])

NegAssign computes pOut = -p0.

func (*Evaluator[T]) NewFourierPoly added in v0.3.0 

func (e *Evaluator[T]) NewFourierPoly() FourierPoly

NewFourierPoly allocates an empty fourier polynomial with the same degree as the evaluator.

func (*Evaluator[T]) NewPoly added in v0.1.3 

func (e *Evaluator[T]) NewPoly() Poly[T]

NewPoly allocates an empty polynomial with the same degree as the evaluator.

func (*Evaluator[T]) ScalarMul 

func (e *Evaluator[T]) ScalarMul(p0 Poly[T], c T) Poly[T]

ScalarMul returns c * p0.

func (*Evaluator[T]) ScalarMulAddAssign 

func (e *Evaluator[T]) ScalarMulAddAssign(p0 Poly[T], c T, pOut Poly[T])

ScalarMulAddAssign computes pOut += c * p0.

func (*Evaluator[T]) ScalarMulAssign 

func (e *Evaluator[T]) ScalarMulAssign(p0 Poly[T], c T, pOut Poly[T])

ScalarMulAssign computes pOut = c * p0.

func (*Evaluator[T]) ScalarMulSubAssign 

func (e *Evaluator[T]) ScalarMulSubAssign(p0 Poly[T], c T, pOut Poly[T])

ScalarMulSubAssign computes pOut -= c * p0.

func (*Evaluator[T]) ShallowCopy 

func (e *Evaluator[T]) ShallowCopy() *Evaluator[T]

ShallowCopy returns a shallow copy of this Evaluator. Returned Evaluator is safe for concurrent use.

func (*Evaluator[T]) Sub 

func (e *Evaluator[T]) Sub(p0, p1 Poly[T]) Poly[T]

Sub returns p0 - p1.

func (*Evaluator[T]) SubAssign 

func (e *Evaluator[T]) SubAssign(p0, p1, pOut Poly[T])

SubAssign computes pOut = p0 - p1.

type FourierEvaluator added in v0.1.3 

type FourierEvaluator[T num.Integer] struct {
	// contains filtered or unexported fields
}

FourierEvaluator calculates algorithms related to FFT, most notably the polynomial multiplication.

Operations usually take two forms: for example,

  • Add(fp0, fp1) adds fp0, fp1, allocates a new polynomial to store the result and returns it.
  • AddAssign(fp0, fp1, fpOut) adds fp0, fp1 and writes the result to pre-allocated pOut without returning.

Note that in most cases, fp0, fp1, and fpOut can overlap. However, for operations that cannot, InPlace methods are implemented separately.

For performance reasons, most methods in this package don't implement bound checks. If length mismatch happens, it may panic or produce wrong results.

func NewFourierEvaluator added in v0.1.3 

func NewFourierEvaluator[T num.Integer](N int) *FourierEvaluator[T]

NewFourierEvaluator allocates an empty FourierEvaluator with degree N.

Panics when N is not a power of two, or when N is smaller than MinDegree or larger than MaxDegree.

func (*FourierEvaluator[T]) Add added in v0.1.3 

func (f *FourierEvaluator[T]) Add(fp0, fp1 FourierPoly) FourierPoly

Add returns fp0 + fp1.

func (*FourierEvaluator[T]) AddAssign added in v0.1.3 

func (f *FourierEvaluator[T]) AddAssign(fp0, fp1, fpOut FourierPoly)

AddAssign computes fpOut = fp0 + fp1.

func (*FourierEvaluator[T]) CmplxMul added in v0.3.0 

func (f *FourierEvaluator[T]) CmplxMul(fp0 FourierPoly, c complex128) FourierPoly

CmplxMul returns c * fp0.

func (*FourierEvaluator[T]) CmplxMulAddAssign added in v0.3.0 

func (f *FourierEvaluator[T]) CmplxMulAddAssign(fp0 FourierPoly, c complex128, fpOut FourierPoly)

CmplxMulAddAssign computes fpOut += c * fp0.

func (*FourierEvaluator[T]) CmplxMulAssign added in v0.3.0 

func (f *FourierEvaluator[T]) CmplxMulAssign(fp0 FourierPoly, c complex128, fpOut FourierPoly)

CmplxMulAssign computes fpOut = c * fp0.

func (*FourierEvaluator[T]) CmplxMulSubAssign added in v0.3.0 

func (f *FourierEvaluator[T]) CmplxMulSubAssign(fp0 FourierPoly, c complex128, fpOut FourierPoly)

CmplxMulSubAssign computes fpOut -= c * fp0.

func (*FourierEvaluator[T]) Degree added in v0.1.3 

func (f *FourierEvaluator[T]) Degree() int

Degree returns the degree of polynomial that the evaluator can handle.

func (*FourierEvaluator[T]) FloatMul added in v0.3.0 

func (f *FourierEvaluator[T]) FloatMul(fp0 FourierPoly, c float64) FourierPoly

FloatMul returns c * fp0.

func (*FourierEvaluator[T]) FloatMulAddAssign added in v0.3.0 

func (f *FourierEvaluator[T]) FloatMulAddAssign(fp0 FourierPoly, c float64, fpOut FourierPoly)

FloatMulAddAssign computes fpOut += c * fp0.

func (*FourierEvaluator[T]) FloatMulAssign added in v0.3.0 

func (f *FourierEvaluator[T]) FloatMulAssign(fp0 FourierPoly, c float64, fpOut FourierPoly)

FloatMulAssign computes fpOut = c * fp0.

func (*FourierEvaluator[T]) FloatMulSubAssign added in v0.3.0 

func (f *FourierEvaluator[T]) FloatMulSubAssign(fp0 FourierPoly, c float64, fpOut FourierPoly)

FloatMulSubAssign computes fpOut -= c * fp0.

func (*FourierEvaluator[T]) MonomialSubOneToFourierPoly added in v0.3.0 

func (f *FourierEvaluator[T]) MonomialSubOneToFourierPoly(d int) FourierPoly

MonomialSubOneToFourierPoly transforms X^d-1 to FourierPoly.

d should be positive.

func (*FourierEvaluator[T]) MonomialSubOneToFourierPolyAssign added in v0.3.0 

func (f *FourierEvaluator[T]) MonomialSubOneToFourierPolyAssign(d int, fpOut FourierPoly)

MonomialSubOneToFourierPolyAssign transforms X^d-1 to FourierPoly and writes it to fpOut.

d should be positive.

func (*FourierEvaluator[T]) MonomialToFourierPoly added in v0.2.7 

func (f *FourierEvaluator[T]) MonomialToFourierPoly(d int) FourierPoly

MonomialToFourierPoly transforms X^d to FourierPoly.

d should be positive.

func (*FourierEvaluator[T]) MonomialToFourierPolyAssign added in v0.2.7 

func (f *FourierEvaluator[T]) MonomialToFourierPolyAssign(d int, fpOut FourierPoly)

MonomialToFourierPolyAssign transforms X^d to FourierPoly and writes it to fpOut.

d should be positive.

func (*FourierEvaluator[T]) Mul added in v0.1.3 

func (f *FourierEvaluator[T]) Mul(fp0, fp1 FourierPoly) FourierPoly

Mul returns fp0 * fp1.

func (*FourierEvaluator[T]) MulAddAssign added in v0.1.3 

func (f *FourierEvaluator[T]) MulAddAssign(fp0, fp1, fpOut FourierPoly)

MulAddAssign computes fpOut += fp0 * fp1.

func (*FourierEvaluator[T]) MulAssign added in v0.1.3 

func (f *FourierEvaluator[T]) MulAssign(fp0, fp1, fpOut FourierPoly)

MulAssign computes fpOut = fp0 * fp1.

func (*FourierEvaluator[T]) MulSubAssign added in v0.1.3 

func (f *FourierEvaluator[T]) MulSubAssign(fp0, fp1, fpOut FourierPoly)

MulSubAssign computes fpOut -= fp0 * fp1.

func (*FourierEvaluator[T]) Neg added in v0.1.3 

func (f *FourierEvaluator[T]) Neg(fp0 FourierPoly) FourierPoly

Neg returns -fp0.

func (*FourierEvaluator[T]) NegAssign added in v0.1.3 

func (f *FourierEvaluator[T]) NegAssign(fp0, fpOut FourierPoly)

NegAssign computes fpOut = -fp0.

func (*FourierEvaluator[T]) NewFourierPoly added in v0.1.3 

func (f *FourierEvaluator[T]) NewFourierPoly() FourierPoly

NewFourierPoly allocates an empty fourier polynomial with the same degree as the evaluator.

func (*FourierEvaluator[T]) NewPoly added in v0.3.0 

func (f *FourierEvaluator[T]) NewPoly() Poly[T]

NewPoly allocates an empty polynomial with the same degree as the evaluator.

func (*FourierEvaluator[T]) PolyMul added in v0.1.3 

func (f *FourierEvaluator[T]) PolyMul(fp0 FourierPoly, p Poly[T]) FourierPoly

PolyMul returns p * fp0 as FourierPoly.

func (*FourierEvaluator[T]) PolyMulAddAssign added in v0.1.3 

func (f *FourierEvaluator[T]) PolyMulAddAssign(fp0 FourierPoly, p Poly[T], fpOut FourierPoly)

PolyMulAddAssign computes fpOut += p * fp0.

func (*FourierEvaluator[T]) PolyMulAssign added in v0.1.3 

func (f *FourierEvaluator[T]) PolyMulAssign(fp0 FourierPoly, p Poly[T], fpOut FourierPoly)

PolyMulAssign computes fpOut = p * fp0.

func (*FourierEvaluator[T]) PolyMulBinary added in v0.3.0 

func (f *FourierEvaluator[T]) PolyMulBinary(fp0 FourierPoly, p Poly[T]) Poly[T]

PolyMulBinary returns p * fp0 as Poly, assuming fp0 is a binary polynomial.

func (*FourierEvaluator[T]) PolyMulBinaryAddAssign added in v0.3.0 

func (f *FourierEvaluator[T]) PolyMulBinaryAddAssign(fp0 FourierPoly, p Poly[T], pOut Poly[T])

PolyMulBinaryAddAssign computes pOut += p * fp0, assuming fp0 is a binary polynomial.

p and pOut should not overlap.

func (*FourierEvaluator[T]) PolyMulBinaryAssign added in v0.3.0 

func (f *FourierEvaluator[T]) PolyMulBinaryAssign(fp0 FourierPoly, p Poly[T], pOut Poly[T])

PolyMulBinaryAssign computes pOut = p * fp0, assuming fp0 is a binary polynomial.

p and pOut should not overlap.

func (*FourierEvaluator[T]) PolyMulBinarySubAssign added in v0.3.0 

func (f *FourierEvaluator[T]) PolyMulBinarySubAssign(fp0 FourierPoly, p Poly[T], pOut Poly[T])

PolyMulBinarySubAssign computes pOut -= p * fp0, assuming fp0 is a binary polynomial.

p and pOut should not overlap.

func (*FourierEvaluator[T]) PolyMulSubAssign added in v0.1.3 

func (f *FourierEvaluator[T]) PolyMulSubAssign(fp0 FourierPoly, p Poly[T], fpOut FourierPoly)

PolyMulSubAssign computes fpOut -= p * fp0.

func (*FourierEvaluator[T]) ShallowCopy added in v0.1.3 

func (f *FourierEvaluator[T]) ShallowCopy() *FourierEvaluator[T]

ShallowCopy returns a shallow copy of this FourierEvaluator. Returned FourierEvaluator is safe for concurrent use.

func (*FourierEvaluator[T]) Sub added in v0.1.3 

func (f *FourierEvaluator[T]) Sub(fp0, fp1 FourierPoly) FourierPoly

Sub returns fp0 - fp1.

func (*FourierEvaluator[T]) SubAssign added in v0.1.3 

func (f *FourierEvaluator[T]) SubAssign(fp0, fp1, fpOut FourierPoly)

SubAssign computes fpOut = fp0 - fp1.

func (*FourierEvaluator[T]) ToFourierPoly added in v0.1.3 

func (f *FourierEvaluator[T]) ToFourierPoly(p Poly[T]) FourierPoly

ToFourierPoly transforms Poly to FourierPoly.

func (*FourierEvaluator[T]) ToFourierPolyAddAssign added in v0.3.0 

func (f *FourierEvaluator[T]) ToFourierPolyAddAssign(p Poly[T], fpOut FourierPoly)

ToFourierPolyAddAssign transforms Poly to FourierPoly and adds it to fpOut.

func (*FourierEvaluator[T]) ToFourierPolyAssign added in v0.1.3 

func (f *FourierEvaluator[T]) ToFourierPolyAssign(p Poly[T], fpOut FourierPoly)

ToFourierPolyAssign transforms Poly to FourierPoly and writes it to fpOut.

func (*FourierEvaluator[T]) ToFourierPolySubAssign added in v0.3.0 

func (f *FourierEvaluator[T]) ToFourierPolySubAssign(p Poly[T], fpOut FourierPoly)

ToFourierPolySubAssign transforms Poly to FourierPoly and subtracts it from fpOut.

func (*FourierEvaluator[T]) ToPoly added in v0.3.0 

func (f *FourierEvaluator[T]) ToPoly(fp FourierPoly) Poly[T]

ToPoly transforms FourierPoly to Poly.

func (*FourierEvaluator[T]) ToPolyAddAssign added in v0.3.0 

func (f *FourierEvaluator[T]) ToPolyAddAssign(fp FourierPoly, pOut Poly[T])

ToPolyAddAssign transforms FourierPoly to Poly and adds it to pOut.

func (*FourierEvaluator[T]) ToPolyAddAssignUnsafe added in v0.3.0 

func (f *FourierEvaluator[T]) ToPolyAddAssignUnsafe(fp FourierPoly, pOut Poly[T])

ToPolyAddAssignUnsafe transforms FourierPoly to Poly and adds it to pOut.

This method is slightly faster than ToPolyAddAssign, but it modifies fp directly. Use it only if you don't need fp after this method (e.g. fp is a buffer).

func (*FourierEvaluator[T]) ToPolyAssign added in v0.3.0 

func (f *FourierEvaluator[T]) ToPolyAssign(fp FourierPoly, pOut Poly[T])

ToPolyAssign transforms FourierPoly to Poly and writes it to pOut.

func (*FourierEvaluator[T]) ToPolyAssignUnsafe added in v0.3.0 

func (f *FourierEvaluator[T]) ToPolyAssignUnsafe(fp FourierPoly, pOut Poly[T])

ToPolyAssignUnsafe transforms FourierPoly to Poly and writes it to pOut.

This method is slightly faster than ToPolyAssign, but it modifies fp directly. Use it only if you don't need fp after this method (e.g. fp is a buffer).

func (*FourierEvaluator[T]) ToPolySubAssign added in v0.3.0 

func (f *FourierEvaluator[T]) ToPolySubAssign(fp FourierPoly, pOut Poly[T])

ToPolySubAssign transforms FourierPoly to Poly and subtracts it from pOut.

func (*FourierEvaluator[T]) ToPolySubAssignUnsafe added in v0.3.0 

func (f *FourierEvaluator[T]) ToPolySubAssignUnsafe(fp FourierPoly, pOut Poly[T])

ToPolySubAssignUnsafe transforms FourierPoly to Poly and subtracts it from pOut.

This method is slightly faster than ToPolySubAssign, but it modifies fp directly. Use it only if you don't need fp after this method (e.g. fp is a buffer).

type FourierPoly 

type FourierPoly struct {
	// Coeffs is represented as float-4 complex vector
	// for efficient computation.
	//
	// Namely,
	//
	//	[(r0, i0), (r1, i1), (r2, i2), (r3, i3), ...]
	//
	// is represented as
	//
	//	[(r0, r1, r2, r3), (i0, i1, i2, i3), ...]
	//
	Coeffs []float64
}

FourierPoly is a polynomial in the fourier domain.

func NewFourierPoly 

func NewFourierPoly(N int) FourierPoly

NewFourierPoly creates a fourier polynomial with degree N with empty coefficients.

Panics when N is not a power of two, or when N is smaller than MinDegree or larger than MaxDegree.

func (FourierPoly) Approx added in v0.3.0 

func (p FourierPoly) Approx(p0 FourierPoly, eps float64) bool

Approx checks if p0 is approximately equal with p, with a difference smaller than eps.

func (FourierPoly) Clear 

func (p FourierPoly) Clear()

Clear clears all the coefficients to zero.

func (FourierPoly) Copy 

func (p FourierPoly) Copy() FourierPoly

Copy returns a copy of the polynomial.

func (*FourierPoly) CopyFrom 

func (p *FourierPoly) CopyFrom(p0 FourierPoly)

CopyFrom copies p0 to p.

func (FourierPoly) Degree 

func (p FourierPoly) Degree() int

Degree returns the degree of the polynomial.

func (FourierPoly) Equals 

func (p FourierPoly) Equals(p0 FourierPoly) bool

Equals checks if p0 is equal with p. Note that due to floating point errors, this function may return false even if p0 and p are equal.

type Poly 

type Poly[T num.Integer] struct {
	Coeffs []T
}

Poly represents the polynomial modulo X^N + 1. N should be power of two.

func From 

func From[T num.Integer](coeffs []T, N int) Poly[T]

From allocates an empty polynomial from given coefficient slice. The given slice is copied, and extended to degree N.

func NewPoly added in v0.2.7 

func NewPoly[T num.Integer](N int) Poly[T]

NewPoly creates a polynomial with degree N with empty coefficients.

Panics when N is not a power of two, or when N is smaller than MinDegree or larger than MaxDegree.

func (Poly[T]) Clear 

func (p Poly[T]) Clear()

Clear clears all the coefficients to zero.

func (Poly[T]) Copy 

func (p Poly[T]) Copy() Poly[T]

Copy returns a copy of the polynomial.

func (*Poly[T]) CopyFrom 

func (p *Poly[T]) CopyFrom(p0 Poly[T])

CopyFrom copies p0 to p.

func (Poly[T]) Degree 

func (p Poly[T]) Degree() int

Degree returns the degree of the polynomial. This is equivalent with length of coefficients.

func (Poly[T]) Equals 

func (p Poly[T]) Equals(p0 Poly[T]) bool

Equals checks if p0 is equal with p.

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.