bignum

package
v0.0.1 Latest Latest
Warning

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

 Go to latest Published: Oct 31, 2024 License: Apache-2.0, BSD-3-Clause, ISC, + 1 more Imports: 6 Imported by: 0

Documentation

Overview

Package bignum implements arbitrary precision arithmetic for integers, reals and complex numbers.

Index

Constants

View Source 
const (
	// Monomial : x^(a+b) = x^a * x^b
	Monomial = Basis(0)
	// Chebyshev : T_(a+b) = 2 * T_a * T_b - T_(|a-b|)
	Chebyshev = Basis(1)
)

Variables

This section is empty.

Functions

func ArithmeticGeometricMean 

func ArithmeticGeometricMean(x, y *big.Float) *big.Float

ArithmeticGeometricMean returns the arithmetic–geometric mean of x and y with 2^precisions bits.

func ChebyshevEval 

func ChebyshevEval(x *big.Float, poly []big.Float, inter Interval) (y *big.Float)

ChebyshevEval evaluates y = sum Ti(x) * poly[i], where T0(x) = 1, T1(x) = (2x-a-b)/(b-a) and T{i+j}(x) = 2TiTj(x)- T|i-j|(x).

func Cos 

func Cos(x *big.Float) (cosx *big.Float)

Cos is an iterative arbitrary precision computation of Cos(x) Iterative process with an error of ~10^{−0.60206*k} = (1/4)^k after k iterations. ref : Johansson, B. Tomas, An elementary algorithm to evaluate trigonometric functions to high precision, 2018

func DivRound 

func DivRound(a, b, i *big.Int)

DivRound sets the target i to round(a/b).

func Exp 

func Exp(x *big.Float) (exp *big.Float)

Exp returns exp(x) with 2^precisions bits.

func Log 

func Log(x *big.Float) (ln *big.Float)

Log return ln(x) with 2^precisions bits.

func Log2 

func Log2(prec uint) *big.Float

func Log2ErfC 

func Log2ErfC(x float64, prec uint) (rF64 float64)

Log2ErfC returns log2(1 - erf(x)).

func MonomialEval 

func MonomialEval(x *big.Float, poly []big.Float) (y *big.Float)

MonomialEval evaluates y = sum x^i * poly[i].

func NewFloat 

func NewFloat(x interface{}, prec uint) (y *big.Float)

NewFloat creates a new big.Float element with "prec" bits of precision. Valide types for x are: int, int64, uint, uint64, float64, *big.Int or *big.Float.

func NewInt 

func NewInt(x interface{}) (y *big.Int)

NewInt allocates a new *big.Int. Accepted types are: string, uint, uint64, int64, int, *big.Float or *big.Int.

func OptimalSplit 

func OptimalSplit(logDegree int) (logSplit int)

func Pi 

func Pi(prec uint) *big.Float

Pi returns Pi with prec bits of precision.

func Pow 

func Pow(x, y *big.Float) (pow *big.Float)

Pow returns x^y

func RandInt 

func RandInt(reader io.Reader, max *big.Int) (n *big.Int)

RandInt generates a random Int in [0, max-1].

func Round 

func Round(x *big.Float) (r *big.Float)

Round returns round(x).

func Sign 

func Sign(x *big.Float) (y *big.Float)

func Sin 

func Sin(x *big.Float) (sinx *big.Float)

func SinH 

func SinH(x *big.Float) (sinh *big.Float)

SinH returns hyperbolic sin(x) with 2^precisions bits.

func Stats 

func Stats(values []big.Int, prec uint) [2]float64

func TanH 

func TanH(x *big.Float) (tanh *big.Float)

TanH returns hyperbolic tan(x) with 2^precisions bits.

func ToComplexSlice 

func ToComplexSlice(values interface{}, prec uint, cmplxSlice []Complex) (err error)

ToComplexSlice takes a - []complex32, []complex128 - []float32, []float64, - []int, []int64, []uint, []uint64, - []big.Int - []big.Float - []bignum.Complex and returns a []bignum.Complex set to the given precision.

Types

type Basis 

type Basis int

Basis is a type for the polynomials basis

type Complex 

type Complex [2]big.Float

Complex is a type for arbitrary precision complex number

func ToComplex 

func ToComplex(value interface{}, prec uint) (cmplx *Complex)

ToComplex takes a - complex32, complex128 - float32, float64, - int, int64, uint, uint64, - *big.Int, big.Int, - *big.Float, big.Float - *bignum.Complex, bignum.Complex and returns a *bignum.Complex set to the given precision.

func (*Complex) Add 

func (c *Complex) Add(a, b *Complex) *Complex

Add adds two arbitrary precision complex numbers together

func (*Complex) Clone 

func (c *Complex) Clone() (clone *Complex)

Clone returns a new copy of the target arbitrary precision complex number

func (*Complex) Complex128 

func (c *Complex) Complex128() complex128

Complex128 returns the arbitrary precision complex number as a complex128

func (*Complex) Imag 

func (c *Complex) Imag() *big.Float

Imag returns the imaginary part as a big.Float

func (*Complex) Int 

func (c *Complex) Int() (bInt *big.Int)

Int returns the real part of the complex number as a *big.Int.

func (*Complex) IsInt 

func (c *Complex) IsInt() bool

IsInt returns true if both the real and imaginary parts are integers.

func (*Complex) IsReal 

func (c *Complex) IsReal() bool

func (*Complex) IsZero 

func (c *Complex) IsZero() bool

IsZero return true if the receiver is zero

func (*Complex) Neg 

func (c *Complex) Neg(a *Complex) *Complex

Neg negates a and writes the result on c.

func (*Complex) Prec 

func (c *Complex) Prec() uint

func (*Complex) Real 

func (c *Complex) Real() *big.Float

Real returns the real part as a big.Float

func (*Complex) Set 

func (c *Complex) Set(a *Complex) *Complex

Set sets an arbitrary precision complex number

func (*Complex) SetComplex128 

func (c *Complex) SetComplex128(x complex128) *Complex

func (*Complex) SetPrec 

func (c *Complex) SetPrec(prec uint) *Complex

func (*Complex) Sub 

func (c *Complex) Sub(a, b *Complex) *Complex

Sub subtracts two arbitrary precision complex numbers together

func (*Complex) Uint64 

func (c *Complex) Uint64() (u64 uint64)

Uint64 returns the real part of the complex number as an uint64.

func (*Complex) Zero 

func (c *Complex) Zero() *Complex

Zero sets the receiver to zero.

type ComplexMultiplier 

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

ComplexMultiplier is a struct for the multiplication or division of two arbitrary precision complex numbers

func NewComplexMultiplier 

func NewComplexMultiplier() (cEval *ComplexMultiplier)

NewComplexMultiplier creates a new ComplexMultiplier

func (*ComplexMultiplier) Mul 

func (cEval *ComplexMultiplier) Mul(a, b, c *Complex)

Mul evaluates c = a * b.

func (*ComplexMultiplier) Quo 

func (cEval *ComplexMultiplier) Quo(a, b, c *Complex)

Quo evaluates c = a / b.

type Interval 

type Interval struct {
	Nodes int
	A, B  big.Float
}

Interval is a struct storing information about interval for a polynomial approximation. Nodes: the number of points used for the interpolation. [A, B]: the domain of the interpolation.

type MetaData 

type MetaData struct {
	Basis
	Interval
	IsOdd  bool
	IsEven bool
}

type Polynomial 

type Polynomial struct {
	MetaData
	Coeffs []Complex
}

func ChebyshevApproximation 

func ChebyshevApproximation(f interface{}, interval Interval) (pol *Polynomial)

ChebyshevApproximation computes a Chebyshev approximation of the input function, for the range [-a, b] of degree degree. f.(type) can be either :

  • func(Complex128)Complex128
  • func(float64)float64
  • func(*big.Float)*big.Float
  • func(*Complex)*Complex

The reference precision is taken from the values stored in the Interval struct.

func NewPolynomial 

func NewPolynomial(basis Basis, coeffs interface{}, interval interface{}) *Polynomial

NewPolynomial creates a new polynomial from the input parameters: basis: either `Monomial` or `Chebyshev` coeffs: []Complex128, []float64, []bignum.Complex or []big.Float interval: [2]float64{a, b} or *Interval

func (*Polynomial) Affine 

func (p *Polynomial) Affine(a, b interface{}) *Polynomial

func (*Polynomial) ChangeOfBasis 

func (p *Polynomial) ChangeOfBasis() (scalar, constant *big.Float)

ChangeOfBasis returns change of basis required to evaluate the polynomial Change of basis is defined as follow:

  • Monomial: scalar=1, constant=0.
  • Chebyshev: scalar=2/(b-a), constant = (-a-b)/(b-a).

func (*Polynomial) Clone 

func (p *Polynomial) Clone() *Polynomial

func (*Polynomial) Degree 

func (p *Polynomial) Degree() int

Degree returns the degree of the polynomial.

func (*Polynomial) Depth 

func (p *Polynomial) Depth() int

Depth returns the number of sequential multiplications needed to evaluate the polynomial.

func (*Polynomial) Evaluate 

func (p *Polynomial) Evaluate(x interface{}) (y *Complex)

Evaluate takes x a *big.Float or *big.Complex and returns y = P(x). The precision of x is used as reference precision for y.

func (*Polynomial) EvaluateModP 

func (p *Polynomial) EvaluateModP(xInt, PInt *big.Int) (yInt *big.Int)

EvaluateModP evalutes the polynomial modulo p, treating each coefficient as integer variables and returning the result as *big.Int in the interval [0, P-1].

func (*Polynomial) Factorize 

func (p *Polynomial) Factorize(n int) (pq, pr *Polynomial)

Factorize factorizes p as X^{n} * pq + pr.

func (*Polynomial) Float64 

func (p *Polynomial) Float64() (coeffs []float64)

Float64 returns the coefficients of the receiver in a float64 slice.

func (*Polynomial) Prec 

func (p *Polynomial) Prec() uint

type PolynomialBSGS 

type PolynomialBSGS struct {
	MetaData
	Coeffs [][]*Complex
}

type Remez 

type Remez struct {
	RemezParameters
	Degree int

	MaxErr, MinErr *big.Float

	Nodes     []point
	Matrix    [][]big.Float
	Vector    []big.Float
	Coeffs    []big.Float
	Iteration int
	// contains filtered or unexported fields
}

Remez implements the optimized multi-interval minimax approximation algorithm of Lee et al. (https://eprint.iacr.org/2020/552). This is an iterative algorithm that returns the minimax polynomial approximation of any function that is smooth over a set of interval [a0, b0] U [a1, b1] U ... U [ai, bi].

func NewRemez 

func NewRemez(p RemezParameters) (r *Remez)

NewRemez instantiates a new Remez algorithm from the provided parameters.

func (*Remez) Approximate 

func (r *Remez) Approximate(maxIter int, threshold float64)

Approximate starts the approximation process. maxIter: the maximum number of iterations before the approximation process is terminated. threshold: the minimum value that (maxErr-minErr)/minErr (the normalized absolute difference between the maximum and minimum approximation error over the defined intervals) must take before the approximation process is terminated.

func (*Remez) ShowCoeffs 

func (r *Remez) ShowCoeffs(prec int)

ShowCoeffs prints the coefficient of the approximate prec: the bit precision of the printed values.

func (*Remez) ShowError 

func (r *Remez) ShowError(prec int)

ShowError prints the minimum and maximum error of the approximate prec: the bit precision of the printed values.

type RemezParameters 

type RemezParameters struct {
	// Function is the function to approximate.
	// It has to be smooth in the defined intervals.
	Function func(x *big.Float) (y *big.Float)

	// Basis is the basis to use.
	// Supported basis are: Monomial and Chebyshev
	Basis Basis

	// Intervals is the set of interval [ai, bi] on which to approximate
	// the function. Each interval also define the number of nodes (points)
	// that will be used to approximate the function inside this interval.
	// This allows the user to implement a separate algorithm that allocates
	// an optimal number of nodes per interval.
	Intervals []Interval

	// Prec defines the bit precision of the overall computation.
	Prec uint

	// Prints things, bruteforces extrema, generate graphs of the error, interval, nodes & extrema
	// (must be configured manually in this file)
	Debug bool
}

RemezParameters is a struct storing the parameters required to initialize the Remez algorithm.

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.