From: israel@math.ubc.ca (Robert Israel) Subject: Re: maple procedure Date: 20 Oct 1999 22:17:22 GMT Newsgroups: sci.math Keywords: LLL algorithm to find non-trivial integer linear combination of reals .In article <7ukl85$8rj$1@nnrp1.deja.com>, Serge Zlobin writes: > Recently I've read an article and they wrote about maple > lattice-based relations algorithm. The problem is: given some numbers > with a lot of digits and it's needed to find non-trivial linear > combination with integer coefficients. The algorithm is needed to find > new identities. Does somebody know about it? Yes. It's the LLL algorithm (for Lenstra, Lenstra and Lovasz). One good reference is M. Mignotte, Mathematics for Computer Algebra, Springer 1991. In a typical application, given real numbers a, b, c which you suspect have a rational linear relation, you take the vectors v1 = [ A, 1, 0, 0 ], v2 = [ B, 0, 1, 0 ], v3 = [ C, 0, 0, 1 ] where A, B and C are the integers close to 10^m a, 10^m b and 10^m c for some large m, and ask Maple's "lattice" function for an LLL-reduced basis of the lattice { n1 v1 + n2 v2 + n3 v3: n1, n2, n3 integers }. If w = [w0, w1, w2, w3] is one of the vectors returned, then w = w1 v1 + w2 v2 + w3 v3 so w0 = w1 A + w2 B + w3 C. If the w's are small (and the point of the LLL algorithm is to find vectors whose components are small), this probably indicates that w1 a + w2 b + w3 c = 0. For example: > a:= .5707963267; b:= .4142135623; c:= .2967764890; (in a real calculation you'd probably use lots more digits) > A:= trunc(10^10*a); B:= trunc(10^10*b); C:= trunc(10^10*c); v1:= [A,1,0,0]; v2:= [B,0,1,0]; v3:= [C,0,0,1]; readlib(lattice): lattice([v1,v2,v3], integer); and Maple returns: [[0, 3, -7, 4], [9467, 6175, -2306, -8658], [48977, -21367, 7972, 29969]] From the first of these, we see that 3 a - 7 b + 4 c is approximately 0. Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 ============================================================================== From: Raymond Manzoni Subject: Re: PSLQ algorithm Date: Sat, 23 Oct 1999 15:17:00 +0200 Newsgroups: sci.math.symbolic Serge Zlobin wrote: > > Hello, everybody! I want to know is there PSLQ algorithm realized in maple > (or in Mathematica)? Maybe there is such library. The algorithm finds integer > relation between real numbers with some precision. -- With best regards, > Sir-G. > > Sent via Deja.com http://www.deja.com/ > Before you buy. Hi, An implementation is available in Mathematica : R.E. Crandall, Topics in Advanced Scientific Computation, Springer/TELOS, New York http://www.telospub.com/catalog/MATHEMATICS/TASC.html (ftp://ftp.telospub.com/pub/ScientificComputing/TopicsAdvSciComp/Code/AppendixCode/PSLQ.ma) I wrote an implementation in mupad myself (available on request). I wrote C code too (for limited search in double or quadruple precision) Very interesting details may be found here : David H. Bailey and Simon Plouffe, Recognizing Numerical Constants http://www.cecm.sfu.ca/organics/papers/bailey But both implementations are of limited interest now since the LLL implementation is proposed in the quick and free (with C sources) pari/gp number theory package. It is order of magnitudes quicker!! (http://hasse.mathematik.tu-muenchen.de/ntsw/pari/Welcome_e.html) To use this last one in practice : Suppose, for example, that you got a number N with 100 digits and think it may be written as sum of powers of Pi then : \p 110 (you ask for this precision, or more, in computations) lindep([N,1,Pi,Pi^2,Pi^3,Pi^4],100) will return you the coefficients to put before N,1,Pi,.. to obtain a total of 0. If it fails it will tell it you or return non significant great numbers (which usually change with precision and are therefore not reliable) Hoping that these few tips will help you to find quickly many new and nice relations. Raymond Manzoni