aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--bigint.cpp15
-rw-r--r--bigint.h2
2 files changed, 10 insertions, 7 deletions
diff --git a/bigint.cpp b/bigint.cpp
index 72a882b..3a36f12 100644
--- a/bigint.cpp
+++ b/bigint.cpp
@@ -325,7 +325,10 @@ Bigint Bigint::operator>>(int sh) const {
int depthrecord;
pair<Bigint,Bigint> Bigint::divmod(const Bigint &div) const {
- pair<Bigint,Bigint> res=divmod(div,1);
+ // cerr<<"divmod("<<hex<<*this<<','<<div<<dec<<')'<<endl;
+ int bitcdiff=bitcount()-div.bitcount();
+ if(bitcdiff<0)bitcdiff=0;
+ pair<Bigint,Bigint> res=divmod(div,1,bitcdiff/29+10);
//cerr<<hex<<*this<<' '<<div<<' ';
//cerr<<dec<<depthrecord<<endl;
//cerr<<" -> "<<hex<<res.first<<' '<<res.second<<dec<<endl;
@@ -336,9 +339,9 @@ inline void record(int depth){
depthrecord=depth;
}
-pair<Bigint,Bigint> Bigint::divmod(const Bigint &div,int depth) const {
- if(depth>100)assert(false);
- //cerr<<"divmod("<<hex<<*this<<','<<hex<<div<<dec<<") depth="<<depth<<endl;
+pair<Bigint,Bigint> Bigint::divmod(const Bigint &div,int depth,int maxdepth) const {
+ if(depth>maxdepth)assert(false);
+ // cerr<<"divmod("<<hex<<*this<<','<<div<<dec<<") depth="<<depth<<" maxdepth="<<maxdepth<<endl;
if(div.digits.size()==0)throw domain_error("Bigint divide by zero");
if(digits.size()==0){record(depth); return make_pair(Bigint::zero,Bigint::zero);}
@@ -436,7 +439,7 @@ pair<Bigint,Bigint> Bigint::divmod(const Bigint &div,int depth) const {
}*/
Bigint rest(*this);
rest-=guess; //also correct for *this and guess negative
- pair<Bigint,Bigint> dm=rest.divmod(div,depth+1);
+ pair<Bigint,Bigint> dm=rest.divmod(div,depth+1,maxdepth);
dm.first+=quotient;
return dm;
}
@@ -454,7 +457,7 @@ pair<Bigint,Bigint> Bigint::divmod(const Bigint &div,int depth) const {
if(cmp==0){record(depth); return make_pair(quotient,Bigint::zero);}
Bigint rest(*this);
rest-=guess;
- pair<Bigint,Bigint> dm=rest.divmod(div,depth+1);
+ pair<Bigint,Bigint> dm=rest.divmod(div,depth+1,maxdepth);
dm.first+=quotient;
return dm;
}
diff --git a/bigint.h b/bigint.h
index 4d6c980..02f3da3 100644
--- a/bigint.h
+++ b/bigint.h
@@ -26,7 +26,7 @@ private:
void normalise();
void checkconsistent();
- std::pair<Bigint,Bigint> divmod(const Bigint&,int depth) const;
+ std::pair<Bigint,Bigint> divmod(const Bigint&,int depth,int maxdepth) const;
public:
Bigint();