3
\$\begingroup\$

I made a bigint class that can add unsigned unlimited precision integers by splitting number into chunks less than 9999, and if a part is bigger than 9999 I take mod 10000 and carry 1 to the next part.

The adding function looks a bit messy as I had to make adjustments for the algorithm if rhs has more/less digits than lhs. Is there a way to make this programm more compact and readable?

class bigint
{
    std::vector<int> parts; 
public:
    bigint(unsigned long long n);
    friend std::ostream& operator<<(std::ostream& os, const bigint& n);
    bigint& operator+=(bigint n);
};

bigint::bigint(unsigned long long n)
{
    while(n != 0)
    {
        parts.push_back(n%10000);
        n/=10000;
    }
}

std::ostream& operator<<(std::ostream& os, const bigint& n)
{
    for(auto it = n.parts.rbegin(); it != n.parts.rend(); ++it)os << (*it);
    return os;
}

bigint& bigint::operator+=(bigint n)
{
    auto a = parts.begin(), b = n.parts.begin();
    int carry = 0;
    while(a != parts.end() && b != n.parts.end())
    {
        *a+=*b+carry;
        carry = 0;
        if(*a > 9999)
        {
            *a = *a%10000;
            carry = 1;
        }
        ++a; ++b;
    }

    // If rhs has more digits than lhs
    if(a == parts.end() && b != n.parts.end())
    {
        while(b != n.parts.end())
        {
            parts.push_back(0);
            a = --parts.end();
            *a+=*b+carry;
            carry = 0;
            if(*a > 9999)
            {
                *a = *a%10000;
                carry = 1;
            }
            ++a; ++b;
        }
    }

    // If lhs has more digits than rhs
    if(b == n.parts.end() && a != parts.end())
    {
        while(a != n.parts.end() && carry == 1)
        {
            *a+=carry;
            carry = 0;
            if(*a > 9999)
            {
                *a = *a%10000;
                carry = 1;
            }
            ++a;
        }
    }
    if(carry == 1)parts.push_back(1);
    return *this;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ The constructor appears to be missing. Also, there's no obvious means by which to get any data back out of the bigint class. Perhaps you could post at least a minimal set of missing features? \$\endgroup\$ – Edward Jun 1 '15 at 21:12
  • \$\begingroup\$ @Edward Pardon. Just added the constructor and a display function \$\endgroup\$ – Andrew Jun 1 '15 at 22:51
  • \$\begingroup\$ No problem. Now I'm sure you'll get reviews. Welcome to Code Review! \$\endgroup\$ – Edward Jun 1 '15 at 23:44
4
\$\begingroup\$

I have reviewed your code and here is what I've found.

Use const references where practical

The code currently declares its addition function like so:

bigint& bigint::operator+=(bigint n)

This has two problems. First it passes by value, so a new bigint is created on every call. This is quite wasteful of both time and memory. Second, it should actually be a const reference.

bigint& bigint::operator+=(const bigint &n)

Eliminate "magic values"

The values of 10000 and 9999 are sprinkled through the code, but they really ought to be a named constant instead, and specifically a named constant static member.

constexpr static int MAXVAL = 10000;

(I'm using the C++11 constexpr here, but it could be const if you're using some old compiler.)

Also use the same constant everywhere. That is, instead of writing this:

if (*a > 9999)

write this:

if (*a >= MAXVAL)

The advantage is that the compiler can probably generate more efficient code because it only has a single constant instead of two.

Be wary of signed versus unsigned

The individual parts should probably be unsigned rather than signed. Since the sole defined constructor only takes unsigned numbers, it's reasonable to assume that the constituent parts are also unsigned.

Avoid computationally costly operations if practical

If we have two "digits" (digits in quotation marks because they're really base 10000 rather than base 10), each with a maximum value of 9999, then the maximum sum is 19998. This means that the carry can only be 1 or 0 and that the code can be rewritten to eliminate the computationally costly % operator:

{
    *a += *b + carry;
    if (*a >= MAXVAL)
    {
        *a -= MAXVAL;
        carry = 1;
    } else {
        carry = 0;
    }
    ++a; ++b;
}

Eliminate redundant condition checks

In the addition code, the first loop only ends if one of the iterators is at the end. This means that the next couple of lines of code:

// If rhs has more digits than lhs
if(a == parts.end() && b != n.parts.cend())
{
    while(b != n.parts.cend())
    {

Can be simplified to just the enclosed while statement.

Extract identical code into a single place

The code for the addition of digits is repeated three places, which is a very strong hit that it should probably be made into its own member function. One way to do it:

int bigint::digitAdd(int &a, int b, int carry)
{
    a+=b+carry;
    if(a >= MAXVAL)
    {
        a -= MAXVAL;
        carry = 1;
    } else {
        carry = 0;
    }
    return carry;
}

Use for rather than while where appropriate

With the function listed above, the first loop can be rewritten as:

for(carry = 0; a != parts.end() && b != n.parts.cend(); ++a, ++b)
{
    carry = digitAdd(*a, *b, carry);
}

It's already much simpler.

Make sure your constructor always works

If the value passed is 0 the constructor will create no members in the parts vector. You might want to reconsider your logic for that case.

Make sure your operator<< does what you really want

Consider the case in which the value stored is 10007. The current operator<< will print "17" which is probably not what is desired.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.