Walter Neumann on Sat, 19 Apr 2003 14:41:43 -0400 (EDT) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: algdep broken in CVS? |
On Thu, 17 Apr 2003, Karim BELABAS wrote: > 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. > Still not working: a=sqrt(2)+sqrt(3)-5^(1/2)+2^(1/4)*I algdep(a,16) gives *** precision too low in lindep. regardless of input precision (I tried \p = 120, 500, 1000) Even when the PSLQ algorithm works, it seems to be slower than the LLL on most examples. --walter