README
¶
This is a library and a command line tool for using the PSLQ integer relation algorithm.
It is used to find relations of the form
a[0]*x[0] + a[1]*x[1] + a[2]*x[2] + ... a[n]*x[n] = 0
where a[] are floating point big.Float values to a given precision
and x[] are integer big.Int values.
The algorithm will tell you that a relation exists, or not within certain bounds.
NB This requires Go >= 1.5 for big.Float support.
Install
Install using go get
go get github.com/ncw/pslq/...
and this will install the library and build the pslq binary in
$GOPATH/bin.
Using the library
See the go doc for details, in particular the example.
Using the binary
Usage pslq [Options]
Where file should contain decimal numbers, one per line. White space is ignored, as are comment lines starting with '#'.
If more than one file is passed in then they are concatenated
If file is '-' then stdin will be read
Options:
-iterations int
Number of iterations to use max (default 1000)
-prec uint
Precision to use (default 64)
-verbose
Print lots of stuff while running
License
This is free software under the terms of the MIT license (check the LICENSE file included in this package).
Portions of the code have been ported from the SymPy source code. These are identified in the relevant files and these parts are additionally licensed under the SymPy Licence (see the SymPy-LICENSE file).
Contact and support
The project website is at:
There you can file bug reports, ask for help or contribute patches.
Authors
- SymPy Development Team - original code that was ported to Go
- Nick Craig-Wood nick@craig-wood.com
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
Source Files
Directories