Karim BELABAS on Thu, 17 Apr 2003 20:20:26 +0200 (MEST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: algdep broken in CVS? |
On Mon, 7 Apr 2003, Walter Neumann wrote: > There still seems to be a bug in algdep: > > Some time ago Karim wrote > >>2.2.5 uses PSLQ which either >> * returns a polynomial which evaluates to 0 at the input precision [ I >>have just changed that. It used to be "at realprecision" which led to >>weird results if you changed the precision after approximating your >>algebraic number. Now PSLQ is insensitive to realprecision >> >>or >> >> * returns a real number B and guarantees that no polynomial of height >>less than B can evaluate to 0. > > The following example contradicts this: > > ? \p 50 > realprecision = 57 significant digits (50 digits displayed) > ? a=sqrt(2)+sqrt(3)-5^(1/3) > %1 = 1.4362884232652753529760261931717103356444220186443 > ? algdep(a,12) > %2 = 235*x^12 - 479*x^11 + 361*x^10 - 278*x^9 + 1252*x^8 - 1922*x^7 + > 337*x^6 + 204*x^5 - 549*x^4 - 1096*x^3 + 1491*x^2 - 113*x + 1361 > ? x=a > %3 = 1.4362884232652753529760261931717103356444220186443 > ? eval(%2) > %4 = 2.171420994059481315 E-37 My comment was unduly precise: "evaluates to 0 at the input precision" is something the algorithm cannot guarantee. It's more an expectation than a definition ... The problem is basically as follows: at some point one needs to decide whether some real number is "0 to the current precision". If I make this too stringent, legitimate relations are missed due to roundoff errors; in the other direction I get such artefacts as above. I have added another heuristic to reduce the likelihood of "spurious" relations. It doesn't seem to break anything and it at least cures the problem above. Any regression ? Karim. -- Karim Belabas Tel: (+33) (0)1 69 15 57 48 Dép. de Mathématiques, Bât. 425 Fax: (+33) (0)1 69 15 60 19 Université Paris-Sud http://www.math.u-psud.fr/~belabas/ F-91405 Orsay (France) http://www.parigp-home.de/ [PARI/GP]