bignum

package
v5.0.2 Latest Latest
Warning

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

 Go to latest Published: Nov 28, 2023 License: Apache-2.0 Imports: 8 Imported by: 18

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 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 TanH 

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

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

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 NewComplex 

func NewComplex() (c *Complex)

NewComplex creates a new arbitrary precision complex number

func ToComplex 

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

ToComplex takes a complex128, float64, int, int64, uint, uint64, *big.Int, *big.Float or *Complex and returns a *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() *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) 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.

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, []*Complex or []*big.Float interval: [2]float64{a, b} or *Interval

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.

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
	// 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

	// ScanStep is the size of the default step used to find the extreme points.
	// The smaller this value is, the lower the probability to miss an extreme point is
	// but the longer each iteration will be.
	// A good starting value is 2^{-10}.
	ScanStep *big.Float

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

	// OptimalScanStep is a boolean to use a dynamic update of the scan step during each
	// iteration.
	OptimalScanStep 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.