Example of optimisation

Declaring the types of variables allow gp2c to perform some optimisations. For example, the following piece of GP code

rho(n)=
{
  local(x,y);

  x=2; y=5;
  while(gcd(y-x,n)==1,
    x=(x^2+1)%n;
    y=(y^2+1)%n; y=(y^2+1)%n
   );
  gcd(n,y-x)
}

generate the following output.

GEN rho(GEN n)
{
  GEN x;
  GEN y;
  x = gdeux;
  y = stoi(5);
  while (gegalgs(ggcd(gsub(y, x), n), 1))
  {
    x = gmod(gaddgs(gsqr(x), 1), n);
    y = gmod(gaddgs(gsqr(y), 1), n);
    y = gmod(gaddgs(gsqr(y), 1), n);
  }
  return ggcd(n, gsub(y, x));
}

The function gsqr, gaddgs, gmod, ggcd, are generic PARI functions that handle gen objects. Since we only want to factor integers with this method, we can declare n, x - y as int:

rho(n:int)=

{

local(x:int,y:int);

  x=2; y=5;
  while(gcd(y-x,n)==1,
    x=(x^2+1)%n;
    y=(y^2+1)%n; y=(y^2+1)%n
   );
  gcd(n,y-x)
}

The new C code output by gp2c is:

GEN rho(GEN n)   /* int */
{
  GEN x;          /* int */
  GEN y;          /* int */
  x = gdeux;
  y = stoi(5);
  while (cmpis(gcdii(subii(y, x), n), 1) == 0)
  {
    x = modii(addis(sqri(x), 1), n);
    y = modii(addis(sqri(y), 1), n);
    y = modii(addis(sqri(y), 1), n);
  }
  return gcdii(n, subii(y, x));
}

Now, the code now uses the more specific functions sqri, addis, modii, and gcdii.

The most efficient way to use typing is to declare some variables as small. This way this variable will be implemented by C long variables, which are faster than PARI integers and do not require garbage collecting. However, you will not be protected from integers overflow. For that reason, gp2c will automatically declare some loop indices as small when the range cannot cause overflow. However gp2c can be too conservative but you can force a loop index to be small with the syntax for(i:small=a,b,...).