Documentation ¶
Overview ¶
The PSLQ algorithm for integer relation detection.
According to Wikipedia: An integer relation algorithm is an algorithm for finding integer relations. Specifically, given a set of real numbers known to a given precision, an integer relation algorithm will either find an integer relation between them, or will determine that no integer relation exists with coefficients whose magnitudes are less than a certain upper bound.
This can be used to identify an unknown real number as being a linear combination of some known constants. For example the original formula for finding the n-th hexadecimal digit of Pi was found using the PSLQ algorithm.
See the example for usage, or use the command line tool in the pslq sub-package.
Example ¶
package main import ( "fmt" "log" "math" "math/big" "github.com/ncw/pslq" ) func main() { in := make([]big.Float, 4) in[0].SetFloat64(10.978081862745977) // Unknown number in[1].SetFloat64(math.Pi) // Some constants it might be in[2].SetFloat64(math.E) in[3].SetFloat64(math.Log(2)) pslq := pslq.New(64).SetMaxSteps(1000) out, err := pslq.Run(in) if err != nil { log.Fatal(err) } for i := range out { d := &out[i] if d.Sign() != 0 { fmt.Printf("%+d * %.10f\n", d, &in[i]) } } fmt.Printf("= 0\n") // The output shows that // 7 * in[0] - 21 * pi - 4 * e = 0 // => in[0] = 3 * pi + 4 * e / 7 }
Output: +7 * 10.9780818627 -21 * 3.1415926536 -4 * 2.7182818285 = 0
Index ¶
- Variables
- type Pslq
- func (e *Pslq) NearestInt(x *big.Float, res *big.Int)
- func (e *Pslq) Run(x []big.Float) ([]big.Int, error)
- func (e *Pslq) SetMaxCoeff(maxcoeff *big.Int) *Pslq
- func (e *Pslq) SetMaxSteps(maxsteps int) *Pslq
- func (e *Pslq) SetTarget(target uint) *Pslq
- func (e *Pslq) SetVerbose(verbose bool) *Pslq
- func (e *Pslq) Sqrt(n, x *big.Float)
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ( ErrorPrecisionExhausted = errors.New("precision exhausted") ErrorBadArguments = errors.New("bad arguments: need at least 2 items") ErrorPrecisionTooLow = errors.New("precision of input is too low") ErrorToleranceRoundsToZero = errors.New("tolerance is zero") ErrorZeroArguments = errors.New("all input numbers must be non zero") ErrorArgumentTooSmall = errors.New("one or more arguments are too small") ErrorNoRelationFound = errors.New("could not find an integer relation") ErrorIterationsExceeded = errors.New("ran out of iterations looking for relation") )
Errors
Functions ¶
This section is empty.
Types ¶
type Pslq ¶
type Pslq struct {
// contains filtered or unexported fields
}
Pslq environment - may be reused and used concurrently
func New ¶
Create a new environment for evaluating Pslq at the given precision. This can be re-used multiple times and used concurrently after it has been set up.
If the algorithm fails at a given precision (doesn't give an answer or ErrorNoRelationfound), it will be necessary to try again with an increased precision.
func (*Pslq) NearestInt ¶
NearestInt set res to the nearest integer to x
func (*Pslq) Run ¶
Given a vector of real numbers x = [x_0, x_1, ..., x_n], this uses the PSLQ algorithm to find a list of integers [c_0, c_1, ..., c_n] such that
|c_1 * x_1 + c_2 * x_2 + ... + c_n * x_n| < tolerance
and such that max |c_k| < maxcoeff. If no such vector exists, Pslq returns one of the errors in this package depending on whether it has run out of iterations, precision or explored up to the maxcoeff. The tolerance defaults to 3/4 of the precision.
This is a fairly direct translation of the pseudocode given by David Bailey, "The PSLQ Integer Relation Algorithm": http://www.cecm.sfu.ca/organics/papers/bailey/paper/html/node3.html
If a result is returned, the first non-zero element will be positive
func (*Pslq) SetMaxCoeff ¶
SetMaxCoeff sets the maximum size of the parameter to be searched for - default 1000
func (*Pslq) SetMaxSteps ¶
SetMaxSteps sets the maximum number of steps of the algorithm to be run. Default 100. Run will return ErrorIterationsExceeded if this is too small.
func (*Pslq) SetTarget ¶
SetTarget sets the target precision of the result.
By default this is 3/4 of the precision
func (*Pslq) SetVerbose ¶
SetVerbose if passed a true parameter then Run will log its progress