Why floor(ZZ(n)**(1/QQ(3))) takes very long for some n?

[Georgi Guninski]

I need this for algorithm, so any suggestions are welcome.

For integers n,D I want to compute floor(n^(1/D)) as fast as possible
and as shown below some (n,D) are very slow.

Attaching plaintext.

n=4135340422190108527133182752606793910306723534619675755332171643310314802791545142347849937796753960728550149130318901202353603554858189176970179851673333220841314769020388020037753836288817542714067202084005701685018536848659752398731202783279286632073202778481147916043949125587307688586641948828478767901629384629584034178304164567671900329273192187585008485182935054618038106382493348288991273367049746743429386091419147153035068860655053634785748825627713903831589035744396002760633267750272685987379975419710843565662471192390599867618755419853042713317247350947919886544123771713595599221242126569812992070962560691614134363627231910741799597501433540116321258358786537575586553481667659367813415959773243374148031245348538233136659886568334330024533550149903451206880641591732426714609514884199626575424718596620317859447733931488021906249419989875053407835737350508812379070175649119
time r=floor(ZZ(n)**(1/QQ(3))) #Time: CPU 7.17 s, Wall: 1.93 s
time r2=floor(ZZ(n+n//3)**(1/QQ(3))) #Time: CPU 0.00 s, Wall: 0.01 s
time r2=floor(ZZ(n+randint(n,2*n))**(1/QQ(3))) #Time: CPU 0.01 s, Wall: 0.01 s

[Michael Orlitzky]

On Mon, 2025-09-22 at 20:08 +0300, Georgi Guninski wrote:
> I need this for algorithm, so any suggestions are welcome.
>
> For integers n,D I want to compute floor(n^(1/D)) as fast as possible
> and as shown below some (n,D) are very slow.
>
> Attaching plaintext.
>
> n=4135340422190108527133182752606793910306723534619675755332171643310314802791545142347849937796753960728550149130318901202353603554858189176970179851673333220841314769020388020037753836288817542714067202084005701685018536848659752398731202783279286632073202778481147916043949125587307688586641948828478767901629384629584034178304164567671900329273192187585008485182935054618038106382493348288991273367049746743429386091419147153035068860655053634785748825627713903831589035744396002760633267750272685987379975419710843565662471192390599867618755419853042713317247350947919886544123771713595599221242126569812992070962560691614134363627231910741799597501433540116321258358786537575586553481667659367813415959773243374148031245348538233136659886568334330024533550149903451206880641591732426714609514884199626575424718596620317859447733931488021906249419989875053407835737350508812379070175649119
> time r=floor(ZZ(n)**(1/QQ(3))) #Time: CPU 7.17 s, Wall: 1.93 s

ZZ(n)**(1/QQ(3)) is giving you a symbolic result. Try
(AA(n)^(1/3)).floor() instead.

[Gareth Ma]

I replied to OP instead of the mailing list, oops.

You can use the `gmpy2` module, namely `gmpy2.iroot(n, 3)[0]`.

Maybe this can go in Sage somewhere, maybe a method under ZZ?

[Vincent Macri]

On 2025-09-22 1:06 p.m., Gareth Ma wrote:

I replied to OP instead of the mailing list, oops.

You can use the `gmpy2` module, namely `gmpy2.iroot(n, 3)[0]`.

Maybe this can go in Sage somewhere, maybe a method under ZZ?

I'm not sure if it's using gmpy2, but we do have a method under ZZ for this: n.nth_root(3, truncate_mode=1)[0].

[Dima Pasechnik]

gmpy2 and ZZ are two different interfaces using gmp as a backend.

both gmpy2.iroot and n.nth_root call gmp's mpz_root() directly.

>
> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/sage-devel/ea77469c-e8c1-4f7b-b1c6-fe1ee65050ff%40ucalgary.ca.

[Georgi Guninski]

On Mon, Sep 22, 2025 at 10:06 PM Gareth Ma <grh...@gmail.com> wrote:
>
> I replied to OP instead of the mailing list, oops.
>
> You can use the `gmpy2` module, namely `gmpy2.iroot(n, 3)[0]`.
>

Many thanks to all for the help!