Re: sqrtnint algorithm improvement for huge arguments (plus memory leak issue)

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

* Jérôme Raulin [2018-01-10 21:01]:
[...]
> (20:23) gp > a=10^1000000; \\ 1 million decimal digits !
> time = 27 ms.
> (20:24) gp > sqrtint(a);
> time = 39 ms.
> (20:24) gp > sqrtnint(a,12);
> time = 208 ms.
> (20:24) gp > sqrtnint(a,123);
> time = 127 ms.
> (20:24) gp > sqrtnint(a,1234);
> time = 172 ms.
> (20:24) gp > sqrtnint(a,12345);
[...]
>   *** sqrtnint: Warning: increasing stack size to 640000000.
> time = 10,236 ms.
> (20:24) gp > sqrtnint(a,123456);
[...]
>   ***   at top-level: sqrtnint(a,123456)
>   ***                 ^------------------
>   *** sqrtnint: the PARI stack overflows !
>   current stack size: 1000001536 (953.676 Mbytes)
>   [hint] you can increase 'parisizemax' using default()

Indeed, the initial guess was far off in this case. I committed a fix to
master by making it ceil( exp(log(a)/n) ) [ computed with 64 bits of accuracy ]:

(23:07) gp > a=10^1000000;
time = 12 ms.
(23:07) gp > sqrtint(a);
time = 24 ms.
(23:07) gp > sqrtnint(a,12);
time = 156 ms.
(23:07) gp > sqrtnint(a,123);
time = 88 ms.
(23:07) gp > sqrtnint(a,1234);
time = 72 ms.
(23:07) gp > sqrtnint(a,12345);
time = 56 ms.
(23:07) gp > sqrtnint(a,123456);
time = 24 ms.

Thanks for the hint and the detailed analysis !

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