Re: Time complexity of issquare() function

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

To: pari-users@pari.math.u-bordeaux.fr
Subject: Re: Time complexity of issquare() function
From: Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>
Date: Fri, 12 Mar 2021 12:34:37 +0100
Delivery-date: Fri, 12 Mar 2021 12:34:43 +0100
Dkim-signature: v=1; a=rsa-sha256; c=simple/simple; d=math.u-bordeaux.fr; s=mail; t=1615548879; bh=GhCXy/61qDbP75keY79dSxmkh3URULX4D/PEY2D2Hes=; h=Date:From:To:Subject:References:In-Reply-To:From; b=aOGAVirKoNDmr5/LPFiPtZv+uHdQUAmlusX49wn7To27S6nTZGDDODQY00uYXBF0n BjASgW4DeB8Omu3il2aKt3fJx2cGqarGlgzvxUIdip0PAEMycZxwcaGCdNbPfOHzLz SWg3fjf8g9SoR68hSbibN1lB8xlW5Iy2CPFHjy4o=
In-reply-to: <CAAgL=bBwhRWD_N1OejHVyz+S90+Y_ObFKvVaHJGqk60mHMf+Mg@mail.gmail.com>
Mail-followup-to: pari-users@pari.math.u-bordeaux.fr
References: <CAAgL=bBwhRWD_N1OejHVyz+S90+Y_ObFKvVaHJGqk60mHMf+Mg@mail.gmail.com>

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

Follow-Ups:
- Re: Time complexity of issquare() function
  - From: Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>

References:
- Time complexity of issquare() function
  - From: Donald Sitompul <sitompulquest@gmail.com>

Prev by Date: Re: Time complexity of issquare() function
Next by Date: Re: Time complexity of issquare() function
Previous by thread: Re: Time complexity of issquare() function
Next by thread: Re: Time complexity of issquare() function
Index(es):
- Date
- Thread