Bignum library in C++ - bignum.cpp

//a bignum library written in C++, it can (in theory) calculate with 4 billion digit long numbers
//this is mostly for demonstration purposes, if you need performance, use something like GNU arbitrary precision library
//Implemented by: http://www.youtube.com/user/thecplusplusguy
#include "bignum.h"
bignum::bignum()
{
    size=10;
    num=new int[size];
    for(int i=0;i<size;i++)
        num[i]=0;
    minus=false;
}

bignum::bignum(int a)
{
    size=20;
    if(a<0)
    {
        a*=-1;
        minus=true;
    }else
        minus=false;
    num=new int[size];
    for(int i=0;i<size;i++)
        num[i]=0;
    num[size-1]=a;
    remainder();
}

bignum::bignum(const char* c)
{
    size=strlen(c);
    num=new int[size];
    for(int i=0;i<size;i++)
        num[i]=c[i]-48;
    remainder();
    minus=false;
}

bignum::bignum(const bignum& bn)
{
    if(this==&bn)
        return;
    size=bn.getSize();
    num=new int[size];
    for(int i=0;i<size;i++)
        num[i]=bn.getNum()[i];
//  remainder();    //MAYBE?
    minus=false;
}


bignum::~bignum()
{
    delete[] num;
}

void bignum::remainder()
{
    int m=0;
    for(int i=size-1;i>0;i--)
    {
        if(num[i]>=0)
        {
            num[i-1]+=num[i]/10;
            num[i]=num[i]%10;
        }else
        {
            num[i]*=-1;
            num[i-1]-=num[i]/10+1;
            if(num[i]%10!=0)
                num[i]=10-num[i]%10;
            else
            {
                num[i-1]++;
                num[i]=0;
            }
        }
    }
    /*
    int i=0;
    while(i<size && num[i]==0)
        i++;
    if(num[i]<0)
    {
        minus=true;
        num[i]*=-1;
    }*/
}

void bignum::allocate(int s)
{
        int* num2=new int[s];
        int j=size-1;
        for(int i=0;i<s;i++)
            num2[i]=0;
        for(int i=s-1;i>=0 && j>=0;i--)
            num2[i]=num[j--];
        delete num;
        num=num2;
        size=s;
}

int bignum::getSize() const
{
    return size;
}

int* bignum::getNum() const
{
    return num;
}

int bignum::getNumSize() const
{
    for(int i=0;i<size;i++)
        if(num[i]!=0)
            return size-i;
    return 0;
}

int bignum::numLength(int a)
{
    int i=1;
    while((a/=10)!=0)
        i++;
    return i;
}

bignum bignum::operator+(const bignum& bn)
{
    bignum tmpnum(bn);
    tmpnum+=(*this);
    return tmpnum;
}

bignum bignum::operator+(int a)
{
    bignum tmpnum(a);
    tmpnum+=(*this);
    return tmpnum;
}

bignum bignum::operator+(const char* a)
{
    bignum tmpnum(a);
    tmpnum+=(*this);
    return tmpnum;
}


bignum bignum::operator-(const bignum& bn)
{
    bignum tmpnum(*this);
    tmpnum-=bn;
    return tmpnum;
}

bignum bignum::operator-(int a)
{
    bignum tmpnum(*this);
    tmpnum-=a;
    return tmpnum;
}

bignum bignum::operator-(const char* a)
{
    bignum tmpnum(*this);
    tmpnum-=a;
    return tmpnum;
}

bignum& bignum::operator+=(const bignum& bn)
{
    int s=bn.getSize();
    int m=size>s ? size : s;
//  if(size>s || (num[0]!=0 && bn.getNum()[0]!=0))
        allocate(m+1);
    int j=size-1;
    for(int i=s-1;i>=0;i--)
    {
        num[j]+=bn.getNum()[i];
        j--;
    }
    remainder();
    return (*this);
}

bignum& bignum::operator+=(int a)
{
    num[size-1]+=a;
    remainder();
    return (*this);
}

bignum& bignum::operator+=(const char* a)
{
    bignum bn(a);
    (*this)+=bn;
    return (*this);
}

bignum& bignum::operator-=(const bignum& bn)
{
    int s=bn.getSize();
    int m=size>s ? size : s;
    if(size>s || (num[0]!=0 && bn.getNum()[0]!=0))
        allocate(m+1);
    int j=size-1;
    for(int i=s-1;i>=0;i--)
    {
        num[j]-=bn.getNum()[i];
        j--;
    }
    remainder();
    return (*this);
}


bignum& bignum::operator-=(int a)
{
    num[size-1]-=a;
    remainder();
    return (*this);
}

bignum& bignum::operator-=(const char* a)
{
    bignum bn(a);
    (*this)-=bn;
    return (*this);
}

bignum& bignum::operator=(const bignum& bn)
{
    size=bn.getSize();
    delete[] num;
    num=new int[size];
    for(int i=0;i<size;i++)
        num[i]=bn.getNum()[i];
//  remainder();    //maybe?
    return (*this);
}

bignum& bignum::operator=(int i)
{
    size=20;
    delete[] num;
    num=new int[size];
    for(int j=0;j<size;j++)
        num[j]=0;
    num[size-1]=i;
    remainder();
}

bignum& bignum::operator=(const char* a)
{
    delete[] num;
    size=strlen(a);
    num=new int[size];
    for(int i=0;i<size;i++)
        num[i]=a[i]-'0';
}


bignum bignum::operator*(const bignum& bn)
{
    bignum tmpnum(bn);
    tmpnum*=(*this);
    return tmpnum;
}

bignum bignum::operator*(int a)
{
    bignum tmpnum(*this);
    tmpnum*=a;
    return tmpnum;
}


bignum bignum::operator*(const char* a)
{
    bignum tmpnum(*this);
    tmpnum*=a;
    return tmpnum;
}

bignum& bignum::operator*=(const bignum& bn)
{
    int s=bn.getNumSize()+getNumSize();
    if(size<s)
        allocate(bn.getSize()+size);
    int* tmp=new int[bn.getSize()+size];
    for(int i=0;i<bn.getSize()+size;i++)
        tmp[i]=0;
    for(int i=bn.getSize()-1;i>=0;i--)
        for(int j=0;j<size;j++)
        {
            tmp[i+j+1]+=bn.getNum()[i]*num[j];
        }
    int j=size-1;
    for(int i=bn.getSize()+size-1;i>=0 && j>=0;i--)
        num[j--]=tmp[i];
    delete[] tmp;
    remainder();
    return (*this);
}

bignum& bignum::operator*=(int a)
{
    int n=numLength(a);
    int s=n+getNumSize();
    if(size<s)
        allocate(n+size);
    int* tmp=new int[n+size];
    for(int i=0;i<n+size;i++)
        tmp[i]=0;
    int cur;
    for(int i=n-1;i>=0;i--)
    {
        cur=a%10;
        for(int j=0;j<size;j++)
        {
            tmp[i+j+1]+=cur*num[j];
        }
        a/=10;
    }
    int j=size-1;
    for(int i=n+size-1;i>=0 && j>=0;i--)
        num[j--]=tmp[i];
    delete[] tmp;
    remainder();
    return (*this);
}

bignum& bignum::operator*=(const char* a)
{
    bignum bn(a);
    (*this)*=bn;
    return (*this);
}


bignum bignum::operator/(const bignum& bn)
{
    bignum tmpnum(*this);
    tmpnum/=bn;
    return tmpnum;
}



bignum bignum::operator/(int a)
{
    bignum tmpnum((*this));
    tmpnum/=a;
    return tmpnum;
}


bignum bignum::operator/(const char* a)
{

    bignum tmpnum((*this));
    tmpnum/=a;
    return tmpnum;
}




bignum bignum::operator%(const bignum& bn)
{
    bignum tmpnum(*this);
    tmpnum%=bn;
    return tmpnum;
}



bignum bignum::operator%(int a)
{
    bignum tmpnum((*this));
    tmpnum%=a;
    return tmpnum;
}


bignum bignum::operator%(const char* a)
{

    bignum tmpnum((*this));
    tmpnum%=a;
    return tmpnum;
}





bignum& bignum::operator/=(int a)
{
    if(a==0)
        return (*this);
    int maradek=0;
    int* tmp=new int[size];
    for(int i=0;i<size;i++)
        tmp[i]=0;
    int i=0;
    int j=0;
    while((maradek/a)==0 && i<size)
    {
        maradek*=10;
        maradek+=num[i];
        i++;
    }
    while(i<=size)
    {
        tmp[j++]=maradek/a;
        maradek=maradek%a;
        maradek*=10;
        maradek+=num[i];
        i++;
    }
    int k=size-1;
    for(i=0;i<size;i++)
        num[i]=0;
    for(i=j-1;i>=0;i--)
        num[k--]=tmp[i];
    remainder();
    delete[] tmp;
    return (*this);
}


bignum& bignum::operator/=(const bignum& bn)
{
    bignum r(*this);
    bignum dd(bn);
    bignum q(0);
    while(dd<=r)
        dd*=2;
    while(dd!=bn)
    {
        dd/=2;
        q*=2;
        if(dd<=r)
        {
            r-=dd;
            q+=1;
        }
    }
    int j=size-1;
    for(int i=0;i<size;i++)
        num[i]=0;
    for(int i=q.getSize()-1;i>=0 && j>=0;i--)
        num[j--]=q.getNum()[i];
    return (*this);

}

bignum& bignum::operator/=(const char* c)
{
    bignum bn(c);
    (*this)/=bn;
    return (*this);
}


bignum& bignum::operator%=(const bignum& bn)
{
    bignum r(*this);
    bignum dd(bn);
//  bignum q(0);
    while(dd<=r)
        dd*=2;
    while(dd!=bn)
    {
        dd/=2;
    //  q*=2;
        if(dd<=r)
        {
            r-=dd;
    //      q+=1;
        }
    }
    int j=size-1;
    for(int i=0;i<size;i++)
        num[i]=0;
    for(int i=r.getSize()-1;i>=0 && j>=0;i--)
        num[j--]=r.getNum()[i];
    return (*this);

}

bignum& bignum::operator%=(const char* c)
{
    bignum bn(c);
    (*this)%=bn;
    return (*this);
}

bignum& bignum::operator%=(int a)
{
    bignum bn(a);
    (*this)%=bn;
    return (*this);
}



bool bignum::operator==(const bignum& bn) const
{
    if(bn.getNumSize()!=getNumSize())
        return false;
    int j=bn.getSize()-1;
    for(int i=size-1;i>=0 && j>=0;i--)
    {
        if(bn.getNum()[j--]!=num[i])
            return false;
    }
    return true;
}
bool bignum::operator==(int n) const
{
    bignum bn(n);
    return (*this)==bn;
}

bool bignum::operator==(const char* c)  const
{
    bignum bn(c);
    return (*this)==bn;
}


bool bignum::operator>(const bignum& bn) const
{
    if(bn.getNumSize()>getNumSize())
        return false;
    if(bn.getNumSize()<getNumSize())
        return true;
    int j=bn.getSize()-bn.getNumSize();
    for(int i=size-getNumSize();i<size;i++)
    {
        if(num[i]!=bn.getNum()[j])
            return num[i]>bn.getNum()[j];
        j++;
    }
    return false;
}

bool bignum::operator>(int n)  const
{
    bignum bn(n);
    return (*this)>bn;
}

bool bignum::operator>(const char* c)    const
{
    bignum bn(c);
    return (*this)>bn;
}


bool bignum::operator<(const bignum& bn) const
{
    return !((*this)>bn) && bn!=(*this);
}

bool bignum::operator<(int n) const
{
    bignum bn(n);
    return (*this)<bn;
}

bool bignum::operator<(const char* c)    const
{
    bignum bn(c);
    return (*this)<bn;
}



bool bignum::operator<=(const bignum& bn)  const
{
    return !((*this)>bn);
}

bool bignum::operator<=(int n)  const
{
    bignum bn(n);
    return (*this)<=bn;
}

bool bignum::operator<=(const char* c)   const
{
    bignum bn(c);
    return (*this)<=bn;
}



bool bignum::operator>=(const bignum& bn)  const
{
    return !((*this)<bn);
}

bool bignum::operator>=(int n)  const
{
    bignum bn(n);
    return (*this)>=bn;
}

bool bignum::operator>=(const char* c)   const
{
    bignum bn(c);
    return (*this)>=bn;
}


bool bignum::operator!=(const bignum& b)  const
{
    return !(*this==b);
}
bool bignum::operator!=(int n)  const
{
    return !(*this==n);
}

bool bignum::operator!=(const char* c)  const
{
    return !(*this==c);
}



bignum& bignum::operator++()
{
    num[size-1]++;
    remainder();
    return (*this);
}

bignum& bignum::operator--()
{
    num[size-1]--;
    remainder();
    return (*this);
}



std::ostream& operator<<(std::ostream& in,const bignum& num)
{
    bool b=false;
    for(int i=0;i<num.getSize();i++)
    {
        if(!b && num.getNum()[i]!=0)
            b=true;
        if(b)
            in << num.getNum()[i];
    }
    if(!b)
        in << 0;
    return in;
}