Modular Exponentiation by inaniwa(not golf)

g[101]={1};
n[333];
p[1000]={2};
v[1000]={1};

m(int*r,int*a,int*b)
{
  int i,j,k;
  int t[1000]={0};

  for(i=0;i<1000;++i){
    for(k=j=0;j<1000-i;++j){
      k=t[i+j]+a[j]*b[i]+k;
      t[i+j]=k%10;
      k/=10;
    }
  }

  memcpy(r,t,sizeof(int)*1000);
}

main()
{
  int i,j,r;

  for(i=0;i<333;++i){
    for(r=j=0;j<101;++j){
      r=r*10+g[j];
      g[j]=r/2;
      r%=2;
    }
    n[i]=r;
  }

  for(i=0;i<333;++i){
    if(n[i]==1) m(v,v,p);
    m(p,p,p);
  }

  for(i=999;i>=0;--i){
    printf("%d",v[i]);
  }
}

Note that non-ascii characters in the above source code will be escaped (such as \x9f).

download

return to the top page