From ddeae250bc6661daafb25ae07f8c2e01b53b0d44 Mon Sep 17 00:00:00 2001
From: tomsmeding <tom.smeding@gmail.com>
Date: Sat, 8 Oct 2016 11:58:59 +0200
Subject: Improve bigint division depth estimate

---
 bigint.cpp | 15 +++++++++------
 bigint.h   |  2 +-
 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();
-- 
cgit v1.2.3-54-g00ecf