diff options
Diffstat (limited to 'numalgo.cpp')
| -rw-r--r-- | numalgo.cpp | 7 |
1 files changed, 5 insertions, 2 deletions
diff --git a/numalgo.cpp b/numalgo.cpp index 9b1681c..c3bfa1b 100644 --- a/numalgo.cpp +++ b/numalgo.cpp @@ -8,7 +8,7 @@ Bigint gcd(Bigint a,Bigint b){ while(true){ if(a==0)return b; if(b==0)return a; - if(a>=b)a=a.divmod(b).second; + if(a.compareAbs(b)==1)a=a.divmod(b).second; else b=b.divmod(a).second; } } @@ -45,13 +45,16 @@ 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(); int two_over_n=nmod8==1||nmod8==7?1:-1; + if(a==0)return 0; while(a.even()){ res*=two_over_n; a>>=1; @@ -84,7 +87,7 @@ Bigint isqrt(const Bigint &n){ if(xnext==x)break; x=xnext; } - cerr<<iter<<endl; + // cerr<<iter<<endl; assert(iter<maxiter); switch((x*x).compare(n)){ case -1:{ |