0

I've been trying to solve this problem (from school) for just about a week now. We're given two numbers, from -(10^100000) to +that.

Of course the simplest solution is to implement written addition, so that's what I did. I decided, that I would store the numbers as strings, using two functions:

int ti(char a) { // changes char to int
    int output = a - 48;
    return output;
}

char tc(int a) { // changes int to char
    char output = a + 48;
    return output;
}

This way I can store negative digits, like -2. With that in mind I implemented a toMinus function:

void toMinus(std::string &a) { // 123 -> -1 -2 -3
    for (auto &x : a) {
        x = tc(-ti(x));
    }
}

I also created a changeSize function, which adds 0 to the beginning of the number until they are both their max size + 1 and removeZeros, which removes leading zeros:

void changeSize(std::string &a, std::string &b) {
    size_t exp_size = std::max(a.size(), b.size()) + 2;
    while (a.size() != exp_size) {
        a = '0' + a;
    }

    while (b.size() != exp_size) {
        b = '0' + b;
    }
}

void removeZeros(std::string &a) {
    int i = 0;    
    for (; i < a.size(); i++) {
        if (a[i] != '0') {
            break;
        }
    }
    a.erase(0, i);
    if (a.size() == 0) {
        a = "0";
    }
}

After all that, I created the main add() function:

std::string add(std::string &a, std::string &b) {
    bool neg[2] = {false, false};
    bool out_negative = false;
    if (a[0] == '-') {
        neg[0] = true;
        a.erase(0, 1);
    }
    if (b[0] == '-') {
        neg[1] = true;
        b.erase(0, 1);
    }

    changeSize(a, b);

    if (neg[0] && !(neg[1] && neg[0])) {
        toMinus(a);
    }
    if(neg[1] && !(neg[1] && neg[0])) {
        toMinus(b);
    }

    if (neg[1] && neg[0]) {
        out_negative = true;
    }

    // Addition
    for (int i = a.size() - 1; i > 0; i--) {
        int _a = ti(a[i]);
        int _b = ti(b[i]);
        int out = _a + _b;
        if (out >= 10) {
            a[i - 1] += out / 10;
        } else if (out < 0) {
            if (abs(out) < 10) {
                a[i - 1]--;
            } else {
                a[i - 1] += abs(out) / 10;
            }
            if (i != 1)
                out += 10;
        }

        a[i] = tc(abs(out % 10));
    }

    if (ti(a[0]) == -1) { // Overflow
        out_negative = true;
        a[0] = '0';
        a[1]--;

        for (int i = 2; i < a.size(); i++) {
            if (i == a.size() - 1) {
                a[i] = tc(10 - ti(a[i]));
            } else {
                a[i] = tc(9 - ti(a[i]));
            }
        }
    }

    if (neg[0] && neg[1]) {
        out_negative = true;
    }

    removeZeros(a);

    if (out_negative) {
        a = '-' + a;
    }

    return a;
}

This program works in most cases, although our school checker found that it doesn't - like instead of

-4400547114413430129608370706728634555709161366260921095898099024156859909714382493551072616612065064

it returned

-4400547114413430129608370706728634555709161366260921095698099024156859909714382493551072616612065064

I can't find what the problem is. Please help and thank you in advance.

Full code on pastebin

  • 1
    Please post a [mcve] into your question. As well as some inpout samples (short ones and long ones) with the expected output. You can [edit] your question. – Jabberwocky Nov 27 '19 at 18:37
  • Why did you decide to store numbers as strings when `int` exists? – eike Nov 27 '19 at 18:45
  • 2
    These are very big numbers. I assume part of the task of this problem is to implement your own big number arithmetic. – drescherjm Nov 27 '19 at 18:45
  • @eike Because we have a memory limit of 32mb –  Nov 27 '19 at 18:46
  • You could do this with a vector of `ints` and use less memory however it will be more complicated. – drescherjm Nov 27 '19 at 18:47
  • 1
    @AdamSołtan But when you store each digit in a char, you waste most of those 8 bits. Since `log_2(10^100000 * 2) / 8` equals about 41524. Each number needs about 41kb space, when stored in the usual integer format, but with a char for each digit, you need 100000bytes = 100kb for each number. – eike Nov 27 '19 at 18:53
  • https://github.com/faheel/BigInt solves this in a header only library that should not be a problem for your 32mb binary limit. If you don't want to / aren't allowed to use libraries, you could look at the source and implement something similar for yourself – eike Nov 27 '19 at 18:59
  • real bigint libraries never store each digit as a char. [They deal with bigger bases](https://stackoverflow.com/a/23840686/995714) like 2³² or 2⁶⁴ for 32 and 64-bit computers respectively for maximum speed and minimum overhead (virtually zero). In case fast input/output is needed then base 10⁹ or 10¹⁹ for 32 and 64-bit PCs is used instead – phuclv Nov 28 '19 at 00:17

1 Answers1

0

While I think your overall approach is totally reasonable for this problem, your implementation seems a bit too complicated. Trying to solve this myself, I came up with this:

#include <iostream>
#include <limits>
#include <random>
#include <string>

bool greater(const std::string& a, const std::string& b)
{
    if (a.length() == b.length()) return a > b;
    return a.length() > b.length();
}

std::string add(std::string a, std::string b)
{
    std::string out;

    bool aNeg = a[0] == '-';
    if (aNeg) a.erase(0, 1);
    bool bNeg = b[0] == '-';
    if (bNeg) b.erase(0, 1);

    bool resNeg = aNeg && bNeg;
    if (aNeg ^ bNeg && (aNeg && greater(a, b) || bNeg && greater(b, a)))
    {
        resNeg = true;
        std::swap(a, b);
    }

    int i = a.length() - 1;
    int j = b.length() - 1;
    int carry = 0;
    while (i >= 0 || j >= 0)
    {
        const int digitA = (i >= 0) ? a[i] - '0' : 0;
        const int digitB = (j >= 0) ? b[j] - '0' : 0;
        const int sum = (aNeg == bNeg ? digitA + digitB : (bNeg ? digitA - digitB : digitB - digitA)) + carry;
        carry = 0;
        if (sum >= 10) carry = 1;
        else if (sum < 0) carry = -1;

        out = std::to_string((sum + 20) % 10) + out;

        i--;
        j--;
    }
    if (carry) out = '1' + out;
    while (out[0] == '0') out.erase(0, 1);
    if (resNeg) out = '-' + out;
    return out;
}


void test()
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(-std::numeric_limits<int32_t>::max(), std::numeric_limits<int32_t>::max());
    for (int i = 0; i < 1000000; ++i)
    {
        const int64_t a = dis(gen);
        const int64_t b = dis(gen);
        const auto expected = std::to_string(a + b);
        const auto actual = add(std::to_string(a), std::to_string(b));
        if (actual != expected) {
            std::cout << "mismatch expected: " << expected << std::endl;
            std::cout << "mismatch actual  : " << actual << std::endl;
            std::cout << "                a: " << a << std::endl;
            std::cout << "                b: " << b << std::endl;
        }
    }
}

int main()
{
    test();
}

It can potentially be further optimized, but the main points are:

  • If the sign of both numbers is the same, we can do simple written addition. If both are negative, we simply prepend - at the end.
  • If the signs are different, we do written subtraction. If the minuend is greater than the subtrahend, there's no issue, we know that the result will be positive. If, however, the subtrahend is greater, we have to reformulate the problem. For example, 123 - 234 we would formulate as -(234 - 123). The inner part we can solve using regular written subtraction, after which we prepend -.

I test this with random numbers for which we can calculate the correct result using regular integer arithmetic. Since it doesn't fail for those, I'm pretty confident it also works correctly for larger inputs. An approach like this could also help you uncover cases where your implementation fails.

Other than that, I think you should use a known failing case with a debugger or simply print statements for the intermediate steps to see where it fails. The only small differences in the failing example you posted could point at some issue with handling a carry-over.

ahans
  • 1,697
  • 12
  • 19