Re: Abnormous memory use for gaussian gcd()?

[hermann@stamm-wilbrandt.de]

OK, I did commit initial RSA_numbers_factored.gp.
Most stuff is commented out (to be transpiled to GP) Python code.
But there is section of 2010 Robert Chapman Python code with several 
transpiled functions:
https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/pari/RSA_numbers_factored.gp#L122-L199

The committed version of 36401.gp
https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/pari/36401.gp
determines runtimes for GP gaussian integer gcd() as well as Robert 
Chapman gaussian integer ggcd().

1)
Running "gp < 36401.gp" does have >3G resident ram during execution, 
that is abnormous memory.

2)
Pari/GP ggcd() computing the same as gcd() is much faster!
Even a little faster than Python gaussian integer gcd() runtime from 
previous posting.

$ gp < 36401.gp
...
foobar
%20 =
...
043623666999335032252892271020017690951275097938471301580066569449430[+++]
  ***   last result computed in 1min, 42,646 ms.
%22 =
...
404362366699933503225289227102001769095127509793847130158006656944943[+++]
  ***   last result computed in 12,661 ms.
Goodbye!
$


It seems that Pari/GP gaussian integer gcd() needs some memory and 
runtime improvements.


Regards,

Hermann.

On 2023-06-05 19:40, hermann@stamm-wilbrandt.de wrote:
> Thank you,
>
> that made it work:
>
> $ gp < 36401.gp
> ...
> 0322528922710200176909512750979384713015800665694494304[+++]
>   ***   last result computed in 1min, 41,244 ms.
> Goodbye!
> $
>
> I don't understand the difference yet, this is whole script 36401.gp
> without word wrapping:
>
> assert(b, v, s) = { if(!(b), error(Str(v) Str(s))); }
>
> R(n) = { (10^n - 1) \ 9; }
>
> p = 34 * R(36400) - 42000040044444004000024 * 10^2264 * R(36400) \ 
> R(4550) - 1
>
> sqrtm1 =
> 1185421332012243159428523992750322769458440239813025493580787813469305...
>
> assert(Mod(sqrtm1^2, p) == Mod(p - 1, p), "sqrtm1", "not");
> print("foobar");
>
> g = gcd(p, sqrtm1 + I)
> ##
> assert(real(g)^2 + imag(g)^2 == p, "g", "not sum of squares");
>
>
>
> gp runtime is 7.9x slower than Python with gmpy2.
>
> I eliminated gmpy2, but Python script keeps 7.9x faster than Pari/GP 
> script.
>
> $ diff 36401.py.orig 36401.py
> 11c11
> < from gmpy2 import mpz  # pylint: disable=no-name-in-module
> ---
> > mpz = lambda x: x
> $ python3.9 36401.py
> gcd(p, sqrtm1 + I): 12.798248767852783s
> $
>
>
> What can be the reason for that?
> I ask because I read this (especially the part after "mainly due"):
> https://oeis.org/wiki/PARI/GP#Comparison_to_other_CAS
> In the domain of number theory, PARI/GP is a strong rival to
> well established all-purpose CAS as Maple and Mathematica,
> mainly due to its computational speed, where it typically outperforms
> both of these well known commercial CAS, and its free availability.
>
>
> Regards,
>
> Hermann Stamm-Wilbrandt.
>
> On 2023-06-05 18:18, Bill Allombert wrote:
> > On Mon, Jun 05, 2023 at 05:51:37PM +0200, hermann@stamm-wilbrandt.de 
> > wrote:
> > > Transpiled GP code for 10000-digit number works fine:
> > >
> > > $ gp 10000.gp
> > > ...
> > > 39178247477405595462999004573259238447193580865522753006504996585341802644743745733315578184178833806642718982619192126965967031226198644279480298699929676[+++]
> > >   ***   last result computed in 4,709 ms.
> > > ?
> > >
> > > But even though I give 24G of my laptop's 32G to Pari, computation 
> > > does not
> > > complete.
> > > What am I doing wrong?
> > > Or is this a bug in Pari/GP?
> > > Python 3.9, Pari/GP 2.15.3.
> > >
> > > $ grep ^parisize /etc/gprc
> > > parisizemax = 24G
> > > parisize = 24G
> > > $ gp 36401.gp
> > > Reading GPRC: /etc/gprc
> > > GPRC Done.
> > > ...
> > > parisizemax = 24000000000, primelimit = 500000
> > > foobar
> > >   ***   The result history is empty.
> >
> > When doing 'gp 36401.gp' there is no "result history" (that is "%1 =
> > blah") so referencing it fails.
> > Probably 36401.gp is using ## (or %).
> >
> > I suggest you try
> > ./gp < 36401.gp
> >
> > I do not see anything that suggest there is a memory error.
> >
> > Cheers,
> > Bill.