aboutsummaryrefslogtreecommitdiff
path: root/numalgo.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'numalgo.cpp')
-rw-r--r--numalgo.cpp7
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:{