diff options
author | tomsmeding <tom.smeding@gmail.com> | 2016-10-08 13:46:59 +0200 |
---|---|---|
committer | tomsmeding <tom.smeding@gmail.com> | 2016-10-08 13:52:05 +0200 |
commit | 00c059d4554f70fc52d94ff1d5dd28976bf857fb (patch) | |
tree | 40d5ddc83133892a87503b370bebf2cb9990ebef /numalgo.cpp | |
parent | 264fb4b2bb5480a28646a8465013647b2e034cf4 (diff) |
Code cleanup
Diffstat (limited to 'numalgo.cpp')
-rw-r--r-- | numalgo.cpp | 8 |
1 files changed, 0 insertions, 8 deletions
diff --git a/numalgo.cpp b/numalgo.cpp index 38184b1..ee77afc 100644 --- a/numalgo.cpp +++ b/numalgo.cpp @@ -25,10 +25,8 @@ Bigint gcd(Bigint a,Bigint b){ Bigint egcd(const Bigint &a,const Bigint &b,Bigint &x,Bigint &y){ Bigint x2(0),y2(1),r(a),r2(b); x=1; y=0; - //cerr<<x<<"\t * "<<a<<"\t + "<<y<<"\t * "<<b<<"\t = "<<r<<endl; while(r2!=0){ pair<Bigint,Bigint> dm=r.divmod(r2); - //cerr<<x2<<"\t * "<<a<<"\t + "<<y2<<"\t * "<<b<<"\t = "<<r2<<" (q = "<<dm.first<<')'<<endl; Bigint xn=x-dm.first*x2; Bigint yn=y-dm.first*y2; x=x2; x2=xn; @@ -54,11 +52,9 @@ Bigint expmod(const Bigint &b,const Bigint &e,const Bigint &m){ int jacobiSymbol(Bigint a,Bigint n){ //https://en.wikipedia.org/wiki/Jacobi_symbol#Calculating_the_Jacobi_symbol - // cerr<<"jacobiSymbol("<<a<<','<<n<<')'<<endl; assert(n>0&&n.odd()); int res=1; while(true){ - // cerr<<" a="<<a<<" n="<<n<<endl; a=a.divmod(n).second; if(a<0)a+=n; int nmod8=n.divmod(Bigint(8)).second.lowdigits(); @@ -79,14 +75,10 @@ Bigint isqrt(const Bigint &n){ assert(n>=0); if(n<=1)return n; const int maxiter=20; //empirically, this should happen around 3.5 million bits in n. (niter ~= -1.87+1.45ln(bits)) - // __asm("int3\n\t"); - // cout<<"bitcount="<<n.bitcount()<<" maxiter="<<maxiter<<endl; Bigint x(n); x>>=n.bitcount()/2; - // cerr<<"isqrt("<<hex<<n<<"); x = "<<x<<dec<<endl; int iter; for(iter=0;iter<maxiter;iter++){ - // cerr<<"x="<<hex<<x<<dec<<endl; Bigint xnext(x*x); // xnext = x - (x*x-n)/(2*x) [Newton's method] xnext-=n; xnext>>=1; |