Re: Time complexity of issquare() function

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

* Karim Belabas [2021-03-12 12:34]:
> * Donald Sitompul [2021-03-12 12:20]:
> > What is the time complexity for the issquare() function?
> 
> Assuming the input is an n-bit integer, the theoretical complexity is O(M(n)),
> where M is the complexity of integer multiplication.
> 
> In practice, the PARI and GMP kernel both implement Schönhage / Strassen
> and M(n) is O(n log(n) loglog(n)).

I forgot a small detail: the native PARI kernel does not implement fast
division. So the complexity without the GMP kernel is O(n^2).

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`