diff options
| -rw-r--r-- | bigint.cpp | 77 | ||||
| -rw-r--r-- | bigint.h | 7 | ||||
| -rw-r--r-- | main.cpp | 27 | ||||
| -rw-r--r-- | primes.cpp | 4 |
4 files changed, 105 insertions, 10 deletions
@@ -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 @@ -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&); @@ -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(); } @@ -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; |