Louis . Granboulan on Mon, 9 Feb 1998 14:02:23 +0100


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

gcd of large numbers.


We use "gerepile" in "mppgcd"'s internal loop.
This is useful for integers of 10000 digits.
-- Ptitboul

*** src/basemath/arith1.c.orig	Sat Feb  7 17:11:30 1998
--- src/basemath/arith1.c	Mon Feb  9 13:44:30 1998
***************
*** 859,865 ****
  GEN
  mppgcd(GEN a, GEN b)
  {
!   long av,st,v,w;
    GEN t;
  
    if (typ(a) != t_INT || typ(b) != t_INT) err(arither1);
--- 859,865 ----
  GEN
  mppgcd(GEN a, GEN b)
  {
!   long av,lim,st,v,w;
    GEN t;
  
    if (typ(a) != t_INT || typ(b) != t_INT) err(arither1);
***************
*** 876,886 ****
--- 876,894 ----
    w=vali(b); if (w) b=shifti(b,-w);
    if (w<v) v=w;
  
+   lim = (av+bot)>>1;
    for(;;)
    { 
      t=subii(a,b); st=signe(t); if (!st) break;
      setsigne(t,1); t=shifti(t,-vali(t));
      if (st>0) a=t; else b=t;
+     if (low_stack(lim, (av+bot)>>1))
+     {
+       GEN *gptr[2];
+       if(DEBUGMEM>1) err(warnmem,"mppgcd");
+       gptr[0]=&a; gptr[1]=&b;
+       gerepilemany(av,gptr,2);
+     }
    }
    avma=av; return shifti(a,v); /* safe, stack big enough */
  }