aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--bigint.cpp77
-rw-r--r--bigint.h7
-rw-r--r--main.cpp27
-rw-r--r--primes.cpp4
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;