Re: Diophantine matters

clicliclic@xxxxxxxxxx wrote:
Robert Israel schrieb:
clicliclic@xxxxxxxxxx writes:

How do you decide whether two real numbers a,b are related by a rational
factor p, where a*p = b? Suppose the numbers are only known to finite
precision, say thirty decimal digits.

One strategy is to calculate the continued fraction for the quotient
b/a, and to see if one of the successive rational approximants equals
b/a to (almost) thirty decimal digits, while the combined number of
digits in its numerator and denominator remains significantly below
thirty.

Now, what would be a good strategy to decide whether three real numbers
a,b,c are related by two rational factors p,q, where a*p + b*q = c? Or
four numbers, or five, etc.?

Look up the LLL (Lenstra, Lenstra, Lovasz) and PSLQ (Partial Sum of Least
Squares) algorithms.

For example, in Maple 13:

Digits:= 30:
L:= [1., 2.78838211157540371710574518532, 2.42559455216300418672182398066,
2.42928300559800284992107700363]:

M:= IntegerRelations[PSLQ](LF);
M := [-380, -611, 169, 689]

add(M[i]*L[i], i=1..4);
0.


Thanks. According to Wikipedia at

<http://en.wikipedia.org/wiki/Integer_relation_algorithm>,

the PSLQ algorithm is more recent, and therefore likely to be better
("substantially simplified in 1999", "selected as one of the Top Ten
Algorithms of the Century").

Wikipedia and Wolfram Mathworld give these references:

- H.R.P. Ferguson and D.H. Bailey: A Polynomial Time, Numerically Stable
Integer Relation Algorithm; RNR Technical Report RNR-91-032, July 14,
1992.

- H.R.P. Ferguson, D.H. Bailey, and S. Arno: Analysis of PSLQ, An
Integer Relation Finding Algorithm; Math. Comput. 68, 351-369, 1999.

But so far I haven't seen an explicit statement of the PSLQ algorithmn
on the internet - either as mathematical formulae or as computer code.
In particular, P. Zimmerman's implementation using GMP at

<http://www.loria.fr/~zimmerma/free/pslq-1.0.c>

seems no longer available :(. Could this algorithm (or perhaps the LLL
one) be implemented in one afternoon, or is this a much more complicated
affair?

Martin.

May be the followings helps (also see the comment by Zimmermann)
http://trac.sagemath.org/sage_trac/ticket/853 and on his homepage
http://www.loria.fr/~zimmerma/free/ there seem to versions for
higher precision libraries

Note that Robert increased precision to 30 Digits, which usually
is something one needs.
.

Quantcast