Karim Belabas on Fri, 25 Jun 2010 17:51:02 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: worrying comment from John McKay |
* Daniel Allcock [2010-06-25 14:58]: > John McKay told me something unlikely but theoretically worrying, and > I'd like to check into it. Namely, that some integer-to-integer > functions use floating point ops for speed, and that the reconversion > to integers at the end of the calculation isn't or wasn't "properly" > justified. Not quite sure what this means, but of course I do want to > trust my results. What's the story? (If it matters, I'm using 2.4.3 > on a mac, with gmp). 1) Some implementation of the Schoenhage-Strassen algorithm (to multiply large integers, and many other things...) rely on floating point computations which are not rigorous, for the sake of raw speed. This is not the case with the gmp implementation, which is (relatively) "slow" but rigorous. 2) Some numerical algorithms in PARI (e.g. intnum, sumalt) are inherently non rigorous, in the sense that they are correct assuming some analytic properties of their input, which a mathematician could in principle check, but which can't be proven numerically. I don't think you were referring to that, but this is in principle specified in the function documentation. 3) Some a priori algebraic algorithms nevertheless use floating point computations in an unproven context ( in most cases, because using proven bounds would juste mean getting no result at all ). To my knowledge, this is always documented, e.g. ??polgalois Warning. The method used is that of resolvent polynomials and is sensitive to the current precision. The precision is updated internally but, in very rare cases, a wrong result may be returned if the initial precision was not sufficient. In rare cases, this may not be so clear if you only read the function documentation, but it is conspicuous in the manual ( E.g. bnfinit() assumes the truth of the GRH. ) Cheers, K.B. -- Karim Belabas, IMB (UMR 5251) Tel: (+33) (0)5 40 00 26 17 Universite Bordeaux 1 Fax: (+33) (0)5 40 00 69 50 351, cours de la Liberation http://www.math.u-bordeaux1.fr/~belabas/ F-33405 Talence (France) http://pari.math.u-bordeaux1.fr/ [PARI/GP] `