Re: worrying comment from John McKay

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* 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]
`