6
\$\begingroup\$

I'm working through some Project Euler problems using C++ and some of the numbers in question are starting to get quite large (21000 for Problem 16) and I need to add some of these large numbers together, so I quickly threw together a string represented (positive) integer adder:

#include <vector>
#include <string>

std::string AddStringNumbers(std::string n1, std::string n2) {
    while (n1.length() < n2.length()) {
        n1 = "0" + n1;
    }
    while (n2.length() < n1.length()) {
        n2 = "0" + n2;
    }

    std::vector<int> sums = std::vector<int>(n1.length(), 0);
    for (int i = 0; i < n1.length(); i++) {
        sums[i] = (n1[i] - '0') + (n2[i] - '0');
    }

    for (int i = sums.size() - 1; i > 0; i--) {
        while (sums[i] > 9) {
            sums[i] -= 10;
            sums[i - 1] += 1;
        }
    }
    if (sums[0] > 9) {
        sums.insert(sums.begin(), 0);
        while (sums[1] > 9) {
            sums[1] -= 10;
            sums[0] += 1;
        }
    }

    std::string o = "";
    for (int i = 0; i < sums.size(); i++) {
        o += (char)('0' + sums[i]);
    }
    return o;
}

Once this was implemented, the solution was simple:

int Problem016(int n) {
    std::string num = "1";
    for (int64_t i = 0; i < n; i++) {
        num = AddStringNumbers(num, num);
    }

    int sum = 0;
    for (int i = 0; i < num.length(); i++) {
        sum += num[i] - '0';
    }
    return sum;
}

Called with:

Problem016(1000);

Is there anything that I can do to improve my AddStringNumbers function? I'm especially interested in the use of storage types other than std::string and what the advantages of doing so would be. It should also be noted that I do have an intention of doing something like this in a class however, as this was quickly thrown together for the solution that's parked for the time being.

I'm less interested in my method of solving Problem 16, however any comments on that would also be appreciated.

\$\endgroup\$
4
\$\begingroup\$

Prepending zeros one at a time is quite inefficient. It could be improved by making a string of the appropriate length in one go:

{
    auto l1 = n1.length();
    auto l2 = n2.length();
    if (l1 < l2)
        n1 = std::string{"0", l2-l1} + n1;
    else if (l1 > l2)
        n2 = std::string{"0",  l1-l2} + n2;
}

Reassembling the string afterwards character by character is also inefficient. This can be improved by telling the string how long it will need to be:

std::string o = "";
o.reserve(sums.size());

The index variables i should be an unsigned type to compare against string length or vector size - I recommend using the same type as those methods return.

Greater gains can be made by keeping the long integer as a chain of digits without adding '0' to make them printable characters at each stage; it also helps to store them in little-endian order (so that any carry gets appended rather than prepended). See Digit-by-digit addition using vectors for a start. You could reduce storage requirements by using base-100 instead of base-10 (char is guaranteed to hold ranging at least from 0 to 127).

\$\endgroup\$
3
\$\begingroup\$

I'm going to ignore that using a string is inefficient for this type of thing (each char could represent 256 values, theoretically, but you only represent 10).


std::string AddStringNumbers(std::string n1, std::string n2) {

This is a big red flag for me. You are using std::string to represent your numbers; use a class instead. Defining a class is quick and easy:

class BigNumber {
    std::string value_;

public:
    explicit BigNumber(std::string value)
        : value_{ std::move(value) }
    {}

    std::string const& value() const { return value_; }
};

BigNumber operator+(BigNumber const& lhs, BigNumber const& rhs);

You could even define the operator+ function inline. To put it simply, "stringly typed" values should be avoided.


std::string AddStringNumbers(std::string n1, std::string n2) {

You also take n1 and n2 by value. This means that the strings have to be copied in (sometimes they can be moved, but for many cases, copied). All that copying is wasteful when you really don't need a copy. Take them by const& instead to save the copies.


Small things to note:

  1. sums.insert(sums.begin(), 0). Inserting something into the beginning of a string or a vector is inefficient. This is because every element has to be copied and shifted over one to the right. Try to avoid this if at all possible.
  2. n1.length(). I recommend using n1.size() as it's more consistent with other standard library containers, but that comes down to personal preference.

Your algorithm:

  1. Make the strings the same length (e.g. "0000193" and "1234567")
  2. Compute the sums for each digit (1, 2, 3, 4, 6, 15, 10)
  3. Transfer carries (from the right) (1, 2, 3, 4, 7, 6, 0)
  4. Convert back into a string

This algorithm is wasteful. The algorithm for addition that we learn in primary school is usually something more like:

  1. Right align the numbers
  2. From the right:
    1. Add the two digits, plus the carry if there is one.
    2. Write the ones digit below in the result.
    3. Write the tends digit above in the carry

This immediately gives two observations:

  1. You don't need to pad the strings; if we could just iterate from the right side of the strings, it would work.
  2. You don't need to compute sums for each digit before constructing the entire string; we can compute and construct as we go.

Point 1:

Luckily for us, std::string has something that allows us to iterate in reverse: rbegin(). string.rbegin() returns an iterator. So we can write this:

auto n1Iter = n1.rbegin();
auto n2Iter = n2.rbegin();

auto n1End = n1.rend();
auto n2End = n2.rend();

Note that auto means that we don't have to write out the type, which would be something like std::string::reverse_iterator (or since we take the string as const&, std::string::const_reverse_iterator). I strongly recommend using auto in almost all places.

Also note that if you stored your numbers backward, the work would be slightly easier.

Point 2:

We can estimate the resulting size we need as max(n1.size(), n2.size()) + 1. This might be 1 more digit than we need, though.

std::string result;
result.resize(std::max(n1.size(), n2.size()) + 1);
auto resultIter = result.rbegin(); // This iterator is modifiable; we can store results into it

We need to keep track of the carry:

int carry = 0; // You might want to use std::uint8_t or other types, but int will work

Now we can iterate over the two strings:

// We have to consider that either number could be smaller.
// You could also ensure that n1Iter/End always refer to the shorter
// or longer string, which might simplify the following logic a bit
while (n1Iter != n1End && n2Iter != n2End) {
    int digitSum = (*n1Iter - '0') + (*n2Iter - '0') + carry;
    carry = digitSum / 10;
    int digit = digitSum % 10;

    *resultIter = static_cast<char>(digit + '0');

    ++resultIter;
    ++n1Iter;
    ++n2Iter;
}

Note that instead of (char)(digit + '0'), I used static_cast<char>(...). It is recommended in C++ that you use the appropriate cast.

auto remainingIter = (n1Iter == n1End) ? n2Iter : n1Iter;
auto remainingEnd = (n1Iter == n1End) ? n2End : n1End;

while (remainingIter != remainingEnd) {
    int digitSum = (*remainingIter - '0') + carry;
    carry = digitSum / 10;
    int digit = digitSum % 10;

    *resultIter = static_cast<char>(digit + '0');

    ++resultIter;
    ++remainingIter;
}

At this point, the string will contain the sum, plus possibly an irrelevant char at the beginning, which we have to detect and remove if necessary:

return result[0] == '\0' ? result.substr(1) : result;

Putting it all together:

class BigNumber {
    std::string value_;

public:
    explicit BigNumber(std::string value)
        : value_{ std::move(value) }
    {}

    std::string const& value() const { return value_; }
};

BigNumber operator+(BigNumber const& lhs, BigNumber const& rhs) {
    auto const& n1 = lhs.value();
    auto const& n2 = rhs.value();

    auto n1Iter = n1.rbegin();
    auto n2Iter = n2.rbegin();

    auto n1End = n1.rend();
    auto n2End = n2.rend();

    std::string result;
    result.resize(std::max(n1.size(), n2.size()) + 1);
    auto resultIter = result.rbegin();

    int carry = 0;

    while (n1Iter != n1End && n2Iter != n2End) {
        int digitSum = (*n1Iter - '0') + (*n2Iter - '0') + carry;
        carry = digitSum / 10;
        int digit = digitSum % 10;

        *resultIter = static_cast<char>(digit + '0');

        ++resultIter;
        ++n1Iter;
        ++n2Iter;
    }

    auto remainingIter = (n1Iter == n1End) ? n2Iter : n1Iter;
    auto remainingEnd = (n1Iter == n1End) ? n2End : n1End;

    while (remainingIter != remainingEnd) {
        int digitSum = (*remainingIter - '0') + carry;
        carry = digitSum / 10;
        int digit = digitSum % 10;

        *resultIter = static_cast<char>(digit + '0');

        ++resultIter;
        ++remainingIter;
    }

    return BigNumber{
        result[0] == '\0' ? result.substr(1) : result
    };
}
\$\endgroup\$

Your Answer

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