From 8e7f8300f82f9d93f94813cd717bf2943e5ad07a Mon Sep 17 00:00:00 2001
From: tomsmeding <tom.smeding@gmail.com>
Date: Wed, 5 Oct 2016 21:18:19 +0200
Subject: Now division ACTUALLY works

---
 bigint.cpp | 77 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++-----
 bigint.h   |  7 ++++++
 main.cpp   | 27 ++++++++++++++++++++--
 primes.cpp |  4 ++--
 4 files changed, 105 insertions(+), 10 deletions(-)

diff --git a/bigint.cpp b/bigint.cpp
index 9fdafe0..0827e1e 100644
--- a/bigint.cpp
+++ b/bigint.cpp
@@ -21,10 +21,35 @@ Bigint::Bigint(slongdigit_t v)
 		"longdigit_t should be twice as large as digit_t");
 	v=abs(v);
 	if(v>digits[0])digits.push_back(v>>digit_bits);
+	else if(v==0){
+		digits.clear();
+		sign=1;
+	}
+	checkconsistent();
+}
+
+Bigint::Bigint(longdigit_t v)
+	:digits(1,(digit_t)v),sign(1){
+	if(v>digits[0])digits.push_back(v>>digit_bits);
 	else if(v==0)digits.clear();
 	checkconsistent();
 }
 
+Bigint::Bigint(sdigit_t v)
+	:digits(1,abs(v)),sign(v>=0?1:-1){
+	if(v==0){
+		digits.clear();
+		sign=1;
+	}
+	checkconsistent();
+}
+
+Bigint::Bigint(digit_t v)
+	:digits(1,v),sign(1){
+	if(v==0)digits.clear();
+	checkconsistent();
+}
+
 void Bigint::add(Bigint &a,const Bigint &b){
 	if(a.digits.size()<b.digits.size())a.digits.resize(b.digits.size());
 	int sz=a.digits.size();
@@ -121,13 +146,46 @@ void Bigint::checkconsistent(){
 }
 
 Bigint& Bigint::operator=(slongdigit_t v){
-	digits.resize(1);
+	digits.clear();
+	if(v==0){
+		sign=1;
+		checkconsistent();
+		return *this;
+	}
 	sign=v>=0?1:-1;
 	v*=sign;
 	digits[0]=v;
 	if(v>digits[0])digits.push_back(v>>digit_bits);
-	shrink();
-	normalise();
+	checkconsistent();
+	return *this;
+}
+
+Bigint& Bigint::operator=(longdigit_t v){
+	digits.clear();
+	if(v!=0){
+		digits.push_back((digit_t)v);
+		if(v>digits[0])digits.push_back(v>>digit_bits);
+	}
+	checkconsistent();
+	return *this;
+}
+
+Bigint& Bigint::operator=(sdigit_t v){
+	digits.clear();
+	if(v==0)sign=1;
+	else {
+		sign=v>=0?1:-1;
+		v*=sign;
+		digits.push_back(v);
+	}
+	checkconsistent();
+	return *this;
+}
+
+Bigint& Bigint::operator=(digit_t v){
+	digits.clear();
+	sign=1;
+	if(v!=0)digits.push_back(v);
 	checkconsistent();
 	return *this;
 }
@@ -335,20 +393,27 @@ pair<Bigint,Bigint> Bigint::divmod(const Bigint &div,int depth) const {
 		divhead>>=digit_bits-__builtin_clz(div.digits.back());
 		//cerr<<"divhead="<<hex<<divhead<<dec<<endl;
 		longdigit_t factor=thishead2/(divhead+1); //+1 to make sure the quotient guess is <= the actual quotient
+		// cerr<<"factor="<<factor<<" thishead2="<<thishead2<<" divhead="<<divhead<<endl;
 		quotient=factor;
-		quotient<<=thisbtc-digit_bits-divbtc; //shift amount may be negative if thisbtc and divbtc < digit_bits apart
+		quotient<<=thisbtc-digit_bits-divbtc; //shift amount may be negative if thisbtc and divbtc are less than digit_bits apart
+		if(quotient==0)quotient=1; //prevents against (HUGE+1)/HUGE where HUGE==HUGE
 		quotient.sign=sign*div.sign;
 		guess=quotient*div;
+		// cerr<<"quotient = "<<hex<<quotient<<dec<<endl;
+		// cerr<<"guess = "<<hex<<guess<<dec<<endl;
 	} else { //divbtc<digit_bits, but *this is large
 		//take 2 digits of *this and all of div
 		int spill=__builtin_clz(digits.back());
-		longdigit_t thishead2=((longdigit_t)digits.back()<<(spill+digit_bits))|(digits[digits.size()-2]<<spill);
+		longdigit_t thishead2=((longdigit_t)digits.back()<<(spill+digit_bits))|((longdigit_t)digits[digits.size()-2]<<spill);
 		if(spill>0)thishead2|=digits[digits.size()-3]>>(digit_bits-spill);
-		longdigit_t factor=thishead2/(div.digits.back()+1); //+1 to make sure the quotient guess is <= the actual quotient
+		longdigit_t factor=thishead2/div.digits[0];
+		//cerr<<"factor="<<factor<<endl;
 		quotient=factor;
 		quotient<<=thisbtc-2*digit_bits;
 		quotient.sign=sign*div.sign;
+		//cerr<<"quotient="<<hex<<quotient<<dec<<endl;
 		guess=quotient*div;
+		//cerr<<"guess= "<<hex<<guess<<dec<<endl;
 	}
 	//cerr<<"guess= "<<hex<<guess<<" quotient="<<quotient<<dec<<endl;
 #endif
diff --git a/bigint.h b/bigint.h
index 76f5415..f5f3f17 100644
--- a/bigint.h
+++ b/bigint.h
@@ -8,6 +8,7 @@
 class Bigint{
 public:
 	using digit_t=uint32_t;
+	using sdigit_t=int32_t;
 	using longdigit_t=uint64_t;
 	using slongdigit_t=int64_t;
 	static const int digit_bits=8*sizeof(digit_t);
@@ -30,11 +31,17 @@ public:
 	Bigint();
 	Bigint(const Bigint&)=default;
 	Bigint(Bigint&&)=default;
+	explicit Bigint(sdigit_t);
+	explicit Bigint(digit_t);
 	explicit Bigint(slongdigit_t);
+	explicit Bigint(longdigit_t);
 
 	Bigint& operator=(const Bigint&)=default;
 	Bigint& operator=(Bigint&&)=default;
 	Bigint& operator=(slongdigit_t);
+	Bigint& operator=(longdigit_t);
+	Bigint& operator=(sdigit_t);
+	Bigint& operator=(digit_t);
 
 	Bigint& operator+=(const Bigint&);
 	Bigint& operator-=(const Bigint&);
diff --git a/main.cpp b/main.cpp
index 380fd0f..491e67b 100644
--- a/main.cpp
+++ b/main.cpp
@@ -107,6 +107,7 @@ void repl(int argc,char **argv){
 			break;
 		}
 	}
+	if(in!=&cin)delete in;
 }
 
 void testisqrt(int argc,char **argv){
@@ -128,7 +129,7 @@ void testisqrt(int argc,char **argv){
 
 void performrsa(){
 	PrivateKey privkey;
-	Bigint p(1000000007),q(3000000019);
+	Bigint p(1000000007),q(3000000019U);
 	privkey.pub.mod=3000000040000000133LL;
 	privkey.pub.exp=65537;
 	{
@@ -161,6 +162,27 @@ void pseudolist(bool(*func)(const Bigint&)){
 	cout<<endl;
 }
 
+void listprimes(){
+	int n=0;
+	Bigint x(3);
+	x*=x;
+	x*=x;
+	x*=x;
+	x*=x;
+	x*=x;
+	x*=x;
+	x*=x;
+	Bigint y(x+10000);
+	cout<<x<<' '<<y<<endl;
+	for(Bigint i(x);i<=y;i+=1){
+		if(bailliePSW(i)){
+			cout<<i<<endl;
+			n++;
+		}
+	}
+	cout<<n<<endl;
+}
+
 int main(int argc,char **argv){
 	(void)argc;
 	(void)argv;
@@ -172,5 +194,6 @@ int main(int argc,char **argv){
 	// strongLucasPrime(Bigint(5));
 	// cout<<strongLucasPrime(Bigint(5777))<<endl;
 	// pseudolist(strongPseudoPrime2);
-	pseudolist(strongLucasPrime);
+	// pseudolist(strongLucasPrime);
+	listprimes();
 }
diff --git a/primes.cpp b/primes.cpp
index d259939..934d886 100644
--- a/primes.cpp
+++ b/primes.cpp
@@ -154,7 +154,7 @@ bool strongLucasPrime(const Bigint &n){
 	// cerr<<"ok"<<endl;
 
 	//now begin the actual sequence algorithm
-#if 0
+#if 1
 	int s=0;
 	Bigint d(n);
 	d+=1;
@@ -198,7 +198,7 @@ bool strongLucasPrime(const Bigint &n){
 		}
 	}
 	if(U==0)return true;
-#if 0
+#if 1
 	if(V==0)return true; //r=0 check
 	for(int r=1;r<s;r++){
 		V*=V;
-- 
cgit v1.2.3-54-g00ecf