Efficient algorithms - Lecture 6
Prev
Next
Topic: BigNum Operations
There are often situations when you need to operate on numbers greater than the maximum values we use in the compilers.
Then, written operations on the so-called Bignums must come to the rescue.
Bignums are numbers that do not fit into the ranges of normal variables. For example, numbers with 100 digits. Such numbers are realized by keeping the "digits" (in some base, not necessarily decimal) in an array, and the operations performed on them are operations called "written" in mathematics (e.g., written addition).
Below is a sample implementation of the BigNum class (for large natural numbers) in C++ with comments, which can be used to implement many problems with really large numbers:
// BigNum structure implementation, that performs arithmetic of large numbers:
struct BigNum {
// Macro to eliminate leading zeros
#define REDUCE() while(len>1 && cyf[len-1]==0) len--;
// Base at which the calculation is performed and the number of zeros in the base
static const int BASE=1000000000, BD=9;
// The variable len represents the current length of the number (number of digits) and al represents the size of the memory allocated for storing digits of the number
int len, al;
// Pointer to number digit array
LL* cyf;
// Constructor of a number with value v and allocated memory for l digits
BigNum(int v=0, int l=2) {
len=1; al=l;
cyf = new LL[al];
REP(x,al) cyf[x]=0;
cyf[0]=v;
if (v>=BASE) przen(1);
}
// Constructor assigning a value to another number of type BigNum
BigNum(const BigNum &a) {
len=al=a.len;
cyf = new LL[al];
REP(x,al) cyf[x]=a.cyf[x];
}
// Destructor
~BigNum(){delete cyf;}
// Function takes as parameter number of digits demand and if demand is bigger than current size of digits array then it reallocates
void Res(int l) {
if (l>al) {
l=max(l,2*al);
LL* n = new LL[l];
REP(x,l) n[x] = x>=al ? 0 : cyf[x];
delete cyf;
cyf = n;
al = l;
}
}
// The function transfers to older digits the overflow resulting from the operation. It is the only place in the whole structure where this operation is performed. The parameter specifies the number of digits to which the excess should be transferred
void przen(int p) {
int x=0;
for(;x<p || cyf[x]<0 || cyf[x]>=BASE;x++) {
Res(x+2);
if(cyf[x]<0){LL i=(-cyf[x]-1)/BASE+1; cyf[x]+=i*BASE; cyf[x+1]-=i;}else
if(cyf[x]>=BASE){LL i=cyf[x]/BASE; cyf[x]-=i*BASE; cyf[x+1]+=i;}
}
len=max(len,x+1);
REDUCE();
}
// This is where the implementation of operators begins. Rewriting this part of the code is not required - you should only rewrite the operators you use. Some operators use other operators - in such cases, it is written next to each operator, which operators it requires to implement.
// The following macro allows you to shorten the notation of operator headers
#define OPER1(op) bool operator op (const BigNum &a) const
/* Operatory porownawcze */
OPER1(==) {
if(a.len!=len) return 0;
REP(x,len) if(cyf[x]!=a.cyf[x]) return 0;
return 1;
}
OPER1(<) {
if(len!=a.len) return len<a.len;
int x=len-1;
while(x && a.cyf[x]==cyf[x]) x--;
return cyf[x]<a.cyf[x];
}
OPER1(>) { return a<*this; } /* Needs < */
OPER1(<=) { return !(a<*this); } /* Needs < */
OPER1(>=) { return !(*this<a); } /* Needs < */
OPER1(!=) { return !(*this==a); } /* Needs == */
// Operations for integer numbers
/* Operatory Bignum - Int */
BigNum &operator=(int a) {
REP(x,len) cyf[x]=0;
len=1; cyf[0]=a;
if (a>=BASE) przen(1);
return *this;
}
void operator+=(int a){cyf[0]+=a; przen(1);}
void operator-=(int a){cyf[0]-=a; przen(1);}
void operator*=(int a){REP(x,len) cyf[x]*=a; przen(len);}
int operator/=(int a) { /* <b> Zwraca reszte z dzielenia </b> */
LL w=0;
FORD(p,len-1,0){w=w*BASE+cyf[p]; cyf[p]=w/a; w=w%a;}
REDUCE();
return w;
}
int operator%(int a) {
LL w=0;
FORD(p,len-1,0) w=(w*BASE+cyf[p])%a;
return w;
}
// Operations on BigNums only
/* Operators Bignum - Bignum */
#define OPER2(op) BigNum& operator op (const BigNum &a)
OPER2(+=) {
Res(a.len);
REP(x,a.len) cyf[x]+=a.cyf[x];
przen(a.len);
return *this;
}
OPER2(-=) {
REP(x,a.len) cyf[x]-=a.cyf[x];
przen(a.len);
return *this;
}
OPER2(*=) {
BigNum c(0,len+a.len);
REP(x,a.len) {
REP(y,len) c.cyf[y+x]+=cyf[y]*a.cyf[x];
c.przen(len+x);
}
*this=c;
return *this;
}
OPER2(/=) { /* Needs operatora <, += (BigNum) , *= (BigNum) , <<=, + (BigNum) , * (BigNum), << */
int n=max(len-a.len+1,0);
BigNum d(0,n), prod;
FORD(i,n-1,0) {
int l=0, r=BASE-1;
while(l<r) {
int m=(l+r+1)/2;
if (*this < prod+(a*m<<i))
r=m-1;
else
l=m;
}
prod+=a*l<<i;
d.cyf[i]=l;
if (l) d.len = max(d.len, i+1);
}
*this=d;
return *this;
}
OPER2(%=) { /* Needs operatora <, += (BigNum) , -= (BigNum) *= (BigNum) , /= (BigNum) <<=, + (BigNum) , * (BigNum), << */
BigNum v=*this;
v/=a;
v*=a;
*this -= v;
return *this;
}
OPER2(=) {
Res(a.len);
FORD(x, len-1, a.len) cyf[x]=0;
REP(x,a.len) cyf[x]=a.cyf[x];
len=a.len;
return *this;
}
// Operators for reading and writing numbers
// The function assigns to BigNum the value of a number from the passed vector, written at base p
/* Reading - writing operators */
void read(const vector<int> &v,int p) { /* Needs += (int), *= (int) */
*this=0;
FORD(x,v.size()-1,0) {
*this *= p;
*this += v[x];
}
}
// Function that gives to the BigNum value of numer that is written in base 10
BigNum &operator=(string a) { /* Needs = (int) */
int s=a.length();
*this=0;
Res(len=s/BD+1);
REP(x,s) cyf[(s-x-1)/BD]=10*cyf[(s-x-1)/BD]+a[x]-'0';
REDUCE();
return *this;
}
// Function prints the value of a BigNum written on base 10
void write() const {
printf("%d", int(cyf[len-1]));
FORD(x,len-2,0) printf("%0*d", BD, int(cyf[x]));
}
// The function writes the value of the number written on base 10 to the buffer
void write(char *buf) const {
int p = sprintf(buf, "%d", int(cyf[len-1]));
FORD(x,len-2,0) p += sprintf(buf+p, "%0*d", BD, int(cyf[x]));
}
vector<int> write(int pod) const { /* Needs /= (int), = (BigNum) */
vector<int> w;
BigNum v;
v=*this;
while(v.len>1 || v.cyf[0]) w.PB(v/=pod);
return w;
}
/* Other operators */
// Right shift operator by n digits to the right
BigNum &operator<<=(int ile) {
if(cyf[0]==0 && len==1) return *this;
Res(len+ile);
FORD(x,len-1,0) cyf[x+ile]=cyf[x];
REP(x,ile) cyf[x]=0;
len+=ile;
return *this;
}
// Right shift operator by n digits to the left
BigNum &operator>>=(int ile) {
if(ile>=len) ile=len;
REP(x,len-ile) cyf[x]=cyf[x+ile];
FOR(x,len-ile,ile) cyf[x]=0;
len-=ile;
if(len==0) len=1;
return *this;
}
BigNum sqrt() { /* Needs <, += (BigNum), *= (BigNum), <<= (int), + (BigNum), * (BigNum), << (int) */
int n=(len+1)/2;
BigNum a(0,n), sq;
FORD(i,n-1,0) {
int l=0, r=BASE-1;
while(l<r) {
int m=(l+r+1)/2;
if (*this < sq+(a*2*m<<i)+(BigNum(m)*m<<2*i))
r=m-1;
else
l=m;
}
sq+=(a*2*l<<i)+(BigNum(l)*l<<2*i);
a.cyf[i]=l; a.len=n;
}
return a;
}
// Macros for reducing headers of the following operators
#define OPER3(op) BigNum operator op(const BigNum &a) const {BigNum w=*this; w op ## = a; return w; }
#define OPER4(op) BigNum operator op(int a) {BigNum w = *this; w op ## = a; return w; }
OPER3(+); /* Needs += (BigNum) */
OPER3(-); /* Needs -= (BigNum) */
OPER3(*); /* Needs *= (BigNum) */
OPER3(/); /* Needs operatora <, += (BigNum) , *= (BigNum) , /= (BigNum) <<=, + (BigNum) , * (BigNum), << */
OPER3(%); /* Needs operatora <, += (BigNum) , -= (BigNum), *= (BigNum) , /= (BigNum), %= (BigNum), <<=, + (BigNum) , * (BigNum), << */
OPER4(<<); /* Needs <<= (int) */
OPER4(>>); /* Needs >>= (int) */
};
Below is an example implementation of the Integer class (for large integers) with comments that can be used to implement tasks:
// An integer implementation based on the BigNum type
int Signum(int x){return x>0?1:(x==0?0:-1);}
int Abs(int x){return x>=0?x:-x;}
struct Integer{
BigNum x;
int sgn; //Integer sign: -1 for negatives, 0 for zero, 1 for positive
// Constructor, taking as parameters the absolute value and the sign of the number to be created
Integer(const BigNum &a, const int &znak) {x = a; sgn = znak;}
Integer(const BigNum &a){x = BigNum(a); sgn = a > BigNum(0);}
// Constructor creating a variable equal to the number a
Integer(const int &a = 0){x = BigNum(Abs(a)); sgn = Signum(a);}
// The operator returns a number with the opposite sign
Integer operator- () const {return Integer(x, sgn*-1);}
// Comparative operators
bool operator<(const Integer &b) const{
if (sgn != b.sgn) return sgn < b.sgn;
if (sgn == -1) return b.x < x;
return x < b.x;
}
bool operator==(const Integer &b) const{return sgn == b.sgn && x == b.x;}
// Macros to shorten operator headers
#define OPER5(op) Integer operator op (const Integer &b) const
OPER5(-) {return *this + (-b);}
OPER5(+) {
if (sgn == -1) return -(-(*this) + (-b));
if (b.sgn >= 0) return Integer(x + b.x, min(1, sgn + b.sgn));
if (x < b.x) return Integer(b.x - x, -1);
return Integer(x - b.x, x > b.x);
}
OPER5(*){ return Integer(x*b.x, sgn*b.sgn);}
OPER5(/){ return Integer(x/b.x, sgn*b.sgn);}
OPER5(%){ return sgn == -1 ? Integer((b.x - (x % b.x)) % b.x) : Integer(x % b.x); }
#define OPER6(op) Integer &operator op ## = (const Integer &b) {return *this = *this op b;}
OPER6(+)
OPER6(-)
OPER6(*)
OPER6(/)
OPER6(%)
// Function writes an Integer number written with base 10 to the standard output
void write() const{if (sgn==-1) printf("-"); x.write();}
};
Below is an example implementation of the Frac class for measurable numbers with large numerators and denominators, along with comments, which can be used to implement tasks:
BigNum NatNWD(const BigNum &a,const BigNum& b){return b==BigNum(0) ? a: NatNWD(b, a%b);}
struct Frac{
Integer a,b;
Frac(const Integer &aa=0,const Integer &bb=1){
a = aa; b = bb;
if(b<0) { a=-a; b=-b; }
Integer d = Integer(NatNWD(aa.x,bb.x));
a/=d; b/=d;
}
bool operator<(const Frac&x) const { return a*x.b < x.a*b;}
bool operator==(const Frac&x) const { return a == x.a && b == x.b;}
#define OPER7(op) Frac operator op (const Frac &x) const
OPER7(+){ return Frac(a*x.b+b*x.a,b*x.b); }
OPER7(-){ return Frac(a*x.b-b*x.a,b*x.b); }
OPER7(*){ return Frac(a*x.a,b*x.b); }
OPER7(/){ return Frac(a*x.b,b*x.a); }
bool isZero(){return a==Integer(0);}
void write(){a.write();printf("/");b.write();}
#define OPER8(op) Frac &operator op ## =(const Frac &b) {return *this = *this op b;}
OPER8(+)
OPER8(-)
OPER8(*)
OPER8(/)
};
For the above codes to work, headers from the so-called "UW library" are also required:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <string>
#include <vector>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define MP make_pair
#define FOR(v,p,k) for(int v=p;v<=k;++v)
#define FORD(v,p,k) for(int v=p;v>=k;--v)
#define REP(i,n) for(int i=0;i<(n);++i)
#define VAR(v,i) __typeof(i) v=(i)
#define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i)
#define PB push_back
#define ST first
#define ND second
#define SIZE(x) (int)x.size()
#define ALL(c) c.begin(),c.end()
Task to do
There are 4 tasks with operations on large numbers: Integer Inquiry, Bishop, Paying in Byteland, Pierwiastkowanie (square root).