Content deleted Content added
Ou phrontis (talk | contribs) →History: If there's no relation, then the algorithm doesn't "determine whether..."; it just never terminates |
GalacticShoe (talk | contribs) →History: Added links to other articles. |
||
Line 10:
*The Ferguson–Forcade algorithm was published in 1979 by [[Helaman Ferguson]] and [[R.W. Forcade]].<ref>{{MathWorld|urlname=IntegerRelation|title=Integer Relation}}</ref> Although the paper treats general ''n'', it is not clear if the paper fully solves the problem because it lacks the detailed steps, proofs, and a precision bound that are crucial for a reliable implementation.
*The first algorithm with complete proofs was 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 '''HJLS algorithm''', developed by [[Johan Håstad]], Bettina Just, [[Jeffrey Lagarias]], and [[Claus P. Schnorr|Claus-Peter Schnorr]] in 1986.<ref>{{MathWorld|urlname=HJLSAlgorithm|title=HJLS Algorithm}}</ref><ref>Johan Håstad, Bettina Just, Jeffrey Lagarias, Claus-Peter Schnorr: ''Polynomial time algorithms for finding integer relations among real numbers.'' Preliminary version: STACS 1986 (''Symposium Theoret. Aspects Computer Science'') Lecture Notes Computer Science 210 (1986), p. 105–118. ''SIAM J. Comput.'', Vol. 18 (1989), pp. 859–881</ref>
*The '''PSOS algorithm''', developed by Ferguson in 1988.<ref>{{MathWorld|urlname=PSOSAlgorithm|title=PSOS Algorithm}}</ref>
*The '''PSLQ algorithm''', developed by Ferguson and [[David H. Bailey (mathematician)|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 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-first=Barry Arthur |author-last=Cipra |author-link=Barry Arthur Cipra |url=http://www.uta.edu/faculty/rcli/TopTen/topten.pdf |title=The Best of the 20th Century: Editors Name Top 10 Algorithms |journal=SIAM News |volume=33 |issue=4}}</ref> even though it is considered essentially equivalent to HJLS.<ref>Jingwei Chen, Damien Stehlé, Gilles Villard: ''[http://perso.ens-lyon.fr/damien.stehle/downloads/PSLQHJLS.pdf A New View on HJLS and PSLQ: Sums and Projections of Lattices.''], [http://www.issac-conference.org/2013/ ISSAC'13]</ref><ref>Helaman R. P. Ferguson, David H. Bailey and Steve Arno, ANALYSIS OF PSLQ, AN INTEGER RELATION FINDING ALGORITHM: [http://crd-legacy.lbl.gov/~dhbailey/dhbpapers/cpslq.pdf]</ref>
*The LLL algorithm has been improved by numerous authors. Modern LLL implementations can solve integer relation problems with ''n'' above 500.
| |||