Integer relation algorithm: Difference between revisions

Revision as of 02:02, 4 February 2014

Revision as of 02:03, 4 February 2014

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 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 detailed steps, proofs, and a precision bound; 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-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. Computing'', Vol. 18 (1989), p. 859–881</ref>