Big Integer

In this project we created a class which represents a big integer value. "Big" means, it can hold arbitrary number of digits. We defined the basic operations on that class (operator= and operator+). The class seems to work correctly.

However we have serious efficiency problems. It seems, that operations in main() are terrible slow, and even worse: execution time is non-linear with the number of digits.

Try to detect the bottlenecks, and fix they (in iterative steps).

#include <stdio.h>
#include <string.h>
#include <time.h>

class BigInt
{
    friend class DigitStream;
public:
		BigInt(const char*);
		BigInt(unsigned n = 0);
		BigInt(const BigInt&);
	       ~BigInt()  { delete [] digits; }
    void	operator=(const BigInt&);
    BigInt	operator+(const BigInt&) const;
    void	print(FILE* f = stdout) const;
private:
    char*	digits;
    unsigned	ndigits;
		BigInt(char* d, unsigned n)  { digits = d; ndigits = n; }
};
class DigitStream
{
public:
    DigitStream(const BigInt& n)  { dp = n.digits; nd = n.ndigits; }
    unsigned operator++()  { if ( nd == 0 ) return 0;
									 else           {nd--; return *dp++; } }
private:
    char*		dp;
    unsigned	nd;
};
void BigInt::print(FILE* f) const
{
    for (int i = ndigits-1; i>=0; i--)   fprintf(f, "%c", digits[i]+'0');
}
void BigInt::operator=(const BigInt& n)
{
    if (this == &n)  return;
    delete [] digits;
    unsigned i = n.ndigits;
    digits = new char[ndigits = i];
    char* p = digits;
    char* q = n.digits;
    while(i--) *p++ = *q++;
}
BigInt BigInt::operator+(const BigInt& n) const
{
    unsigned maxDigits = (ndigits>n.ndigits ? ndigits : n.ndigits)+1;
    char* sumPtr = new char[maxDigits];
    BigInt sum(sumPtr, maxDigits);
    DigitStream a(*this);
    DigitStream b(n);
    unsigned i = maxDigits;
    unsigned carry = 0;
    while (i--)
    {
	*sumPtr = (++a) + (++b) + carry;
	if ( *sumPtr >= 10 )
	{
	    carry = 1;
	    *sumPtr -= 10;
	}
	else carry = 0;
	
	sumPtr++;
    }
    return sum;
}
BigInt::BigInt(unsigned n)
{
    char d[3*sizeof(unsigned)+1];
    char* dp = d;
    ndigits = 0;

    do
    {
	*dp++ = n%10;
	n /= 10;
    	ndigits++;
    } 
    while (n > 0);

    digits = new char[ndigits];
    for (register i = 0; i < ndigits; i++) digits[i] = d[i];
}
BigInt::BigInt(const BigInt& n)
{
    unsigned i = n.ndigits;
    digits = new char[ndigits = i];
    char* p = digits;
    char* q = n.digits;
    while (i--)  *p++ = *q++;
}
BigInt::BigInt(const char* digitString)
{
    unsigned n = strlen(digitString);
    if (n != 0)
    {
	digits = new char[ndigits = n];
    	char* p = digits;
    	const char* q = &digitString[n];
    	while (n--) *p++ = *--q - '0';
    }
    else
    {
	digits = new char[ndigits = 1];
	digits[0] = 0;
    }
}

int main()
{
    BigInt b = 1;
    time_t t1 = time(NULL);
    
    for (int i = 1; i <= 50000; ++i)  b = b + 1;
    time_t t2 = time(NULL);
    printf("Elapsed time: %ld\n", t2 - t1);
    //  1000 rec =   1 sec
    //  2000 rec =   7 sec
    //  5000 rec =  38 sec
    //	10000 rec = 150 sec
    //   ... on my old machine :-)
}