Karim Belabas on Fri, 12 Mar 2021 12:34:43 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Time complexity of issquare() function


* 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)).

If you're interested in other inputs, please be more specific :-)

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