Re: Abnormous memory use for gaussian gcd()?

[hermann@stamm-wilbrandt.de]

> Now, why the gcd is very slow ? I do not know, but this is a bit 
> artificial
> way to do this computation.
> You could do
> qfbcornacchia(1,p)
>
> ((or if you want to reuse sqrtm1:
> [M,V]=halfgcd(sqrtm1,p);
> V[2]+I*M[2,1]
> which is very fast but quite specific to this case.
> ))
Please see my reply to your other posting wrt. qfbcornacchia(1,p) and 
the time as well as memory problem.


I don't know what you proposed yet, but it correctly computes the sum of 
squares for p given sqrtm1 in single digit milliseconds!!
p and sqrtm1 are 36401 decimal digit numbers ...

$ gp < 3b.gp
...
98529039397711932874293321847452529[+++]
foobar
  ***   last result computed in 4 ms.
done
Goodbye!
$


I added print("done") after the final assert to be sure that go really 
computed the gcd in 4 milliseconds:

3.8.55 halfgcd(x, y):
https://pari.math.u-bordeaux.fr/pub/pari/manuals/2.15.1/users.pdf#page=204

$ diff 36401.gp 3b.gp
13c13
< g = gcd(p, sqrtm1 + I)
---
> [M,V]=halfgcd(sqrtm1,p);
15,19c15,16
< assert(real(g)^2 + imag(g)^2 == p, "g", "not sum of squares");
<
< [x,y] = ggcd([p, 0], [sqrtm1, 1])
< ##
< assert(x^2 + y^2 == p, "x,y", "not sum of squares");
---
> assert(V[2]^2 + M[2,1]^2 == p, "x,y", "not sum of squares");
> print("done");
$


Thank you for all your responses,

Hermann Stamm-Wilbrandt.