Integer relation algorithm: Difference between revisions

Revision as of 14:55, 24 September 2010

Revision as of 01:30, 10 November 2010

Line 8:

For the case ''n'' = 2, an extension of the [[Euclidean algorithm]] can determine whether there is an integer relation between any two real numbers ''x''₁ and ''x''₂. The algorithm generates successive terms of the [[continued fraction]] expansion of ''x''₁/''x''₂; if there is an integer relation between the numbers then their ratio is rational and the algorithm eventually terminates.

The first general algorithm that was proved to work for all values of ''n'' was the [[Ferguson–Forcade algorithm]], published in 1979 by [[Helaman Ferguson]] and [[R.W. Forcade]].<ref>{{MathWorld|urlname=IntegerRelation|title=Integer Relation}}</ref> Subsequent developments, focussing on improving both efficiency and numerical stability, produced the following algorithms:

*The [[Lenstra–Lenstra–Lovász lattice basis reduction algorithm|'''LLL algorithm''']], developed by [[Arjen Lenstra]], [[Hendrik Lenstra]] and [[László Lovász]] in 1982.<ref>{{MathWorld|urlname=LLLAlgorithm|title=LLL Algorithm}}</ref>

*The '''PSOS algorithm''', developed by Ferguson in 1988.<ref>{{MathWorld|urlname=PSOSAlgorithm|title=PSOS Algorithm}}</ref>

*The '''HJLS algorithm''', developed by Ferguson and [[David H. Bailey|David Bailey]] in 1992.<ref>{{MathWorld|urlname=HJLSAlgorithm|title=HJLS Algorithm}}</ref>

*The '''PSLQ algorithm''', also developed by Ferguson and Bailey in 1992 and substantially simplified by Ferguson, Bailey, and Arno in 1999.<ref>{{MathWorld|urlname=PSLQAlgorithm|title=PSLQ Algorithm}}</ref><ref>[http://crd.lbl.gov/~dhbailey/dhbpapers/pslq.pdf ''A Polynomial Time, Numerically Stable Integer Relation Algorithm''] by [[Helaman Ferguson|Helaman R. P. Ferguson]] and [[David H. Bailey]]; RNR Technical Report RNR-91-032; July 14, 1992</ref>

In 2000 the PSLQ algorithm was selected as one of the "Top Ten Algorithms of the Century" by [[Jack Dongarra]] and Francis Sullivan.<ref>{{cite journal |author=Barry A. Cipra |url=http://amath.colorado.edu/resources/archive/topten.pdf |title=The Best of the 20th Century: Editors Name Top 10 Algorithms |journal=SIAM News |volume=33 |issue=4}}</ref>

Line 31:

==External links==

*[http://oldweb.cecm.sfu.ca/organics/papers/bailey/paper/html/paper.html ''Recognizing Numerical Constants''] by [[David H. Bailey]] and [[Simon Plouffe]]

*[http://crd.lbl.gov/~dhbailey/dhbpapers/tenproblems.pdf ''Ten Problems in Experimental Mathematics''] by [[David H. Bailey]], [[Jonathan Borwein|Jonathan M. Borwein]], Vishaal Kapoor, and [[Eric W. Weisstein]]

{{number theoretic algorithms}}