Karim BELABAS on Thu, 28 Sep 2000 14:12:01 +0200 (MET DST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: >0 ? |
[Keith Briggs:] > Is there a function or algorithm in pari which will decide > if a given element x of a number field (expressed on an integral > basis) is positive, without doing any floating-point arithmetic? 1) if r_1 = 1, you can compute Norm(x) [ sign(norm(nfbasistoalg(nf,x))) ] (this remains a cheap test even when r_1 > 1) 2) you can compute the minimal polynomial of x [ y = charpoly(nfbasistoalg(nf,x)); pol = y / gcd(y,y') ] then use polsturm(pol, 0) == poldegree(pol) to check the number of positive real roots [ there are more efficient algorithms for real roots than Sturm's (e.g Uspensky's), but they are not implemented in the distributed version yet ] 3) You could also get a guaranteed answer by computing the roots of pol. This uses floating point arithmetic but produces a proven output (i.e if you ask for 100 exact decimals, you obtain them), so given an initial approximation of the roots, you can obtain a proof that they are indeed of the expected sign. Of course, multiplying by nf[5][1] is the fastest way (which is used in the PARI code) but it neither avoids floating point arithmetic, nor provides a guaranteed output. Hope this helps, Karim. __ Karim Belabas email: Karim.Belabas@math.u-psud.fr Dep. de Mathematiques, Bat. 425 Universite Paris-Sud Tel: (00 33) 1 69 15 57 48 F-91405 Orsay (France) Fax: (00 33) 1 69 15 60 19 -- PARI/GP Home Page: http://www.parigp-home.de/