hermann on Mon, 05 Jun 2023 21:42:20 +0200


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

Re: Abnormous memory use for gaussian gcd()?


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.