2

I need to use vectors to add 2 huge numbers, like this:

(Example: 3049358031 + 1449238031)

I searched everywhere, but I didn't find nothing.

(I have to use only vectors)

I have this code (which is not working):

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector <int> int1;
    vector <int> int2;
    vector <int> final;

    int input1, input2;
    int length = 0, length1 = 0;


    cin >> input1 >> input2;
    cout << "after cin" << endl;

string strNum = to_string(input1);
length = strNum.length();

string strNum1 = to_string(input2);
length1 = strNum.length();

    if(length > length1){
        strNum = to_string(input1);
length = strNum.length();

    } else {
        strNum1 = to_string(input2);
length1 = strNum.length();
    }


    cout << length;

    string q = to_string(input2);

    for(int i = 0; i < length; i++){

        int1[i] = strNum.at(i);
        int2[i] = strNum1.at(i);
    }
    cout << "after ye" << endl;
    for(int i = 0; i < length; i++){
        cout << " " << int1[i];
    }

    return 0;
}

Do I need to use vector<long long>or vector<int>?

NathanOliver
  • 171,901
  • 28
  • 288
  • 402
  • 1
    A typical (4-byte) signed int holds values up to 2147483647. – SingerOfTheFall Oct 23 '15 at 12:25
  • You can take the naive approach and store each digit of the number in a separate element in the vector and then work on the numbers like you would on pencil and paper. – NathanOliver Oct 23 '15 at 12:27
  • ok, thanks. Let's assume char datatype is 8 bits, then can I make use of that to store two 4 bit integer? –  Oct 23 '15 at 12:30
  • @YangYing: You should not assume anything. Use `sizeof` and `CHAR_BIT`. – Christian Hackl Oct 23 '15 at 13:39
  • @NathanOliver I could be trying to store each number in an element of a vector and work the math like a 3rd grader does on their test or he could just need to use std::accumulate or a for loop to add them all together. –  Oct 23 '15 at 15:07
  • @SingerOfTheFall I think you are wrong. Int has 4 bytes and has a range of values of -2.1billion to 2.1billion –  Oct 23 '15 at 15:08

2 Answers2

0
#include <vector>
#include <limits>
#include <cmath>
#include <algorithm>
#include <string>
#include <sstream>
#include <iostream>
#include <stdexcept>
using namespace std;

vector<unsigned> stringToVector(string representation) {
    const unsigned DIGITS_LIMIT = numeric_limits<unsigned>::digits10;
    for (size_t i = DIGITS_LIMIT; i < representation.size(); i += DIGITS_LIMIT + 1)
        representation.insert(i, 1, ' ');
    vector<unsigned> literal;
    stringstream representationStream(representation);
    do {
        unsigned value;
        representationStream >> value;
        literal.push_back(value);
    } while (!representationStream.eof());
    return literal;
}

vector<unsigned> operator + (const vector<unsigned> & x, const vector<unsigned> & y) {
    vector<unsigned> accumulator = (x.size() > y.size())? x : y;
    const vector<unsigned> &increment = (x.size() < y.size())? x : y;
    const unsigned LIMIT = static_cast<unsigned>(pow(10, numeric_limits<unsigned>::digits10));
    const unsigned LITTLE_SIZE = min(accumulator.size(), increment.size());
    for (size_t i = 0; i < LITTLE_SIZE; ++i) {
        const unsigned UNTIL_LIMIT = LIMIT - accumulator[i];
        if (UNTIL_LIMIT > increment[i])
            accumulator[i] += increment[i]; 
        else {
            accumulator[i] = increment[i] - UNTIL_LIMIT;
            size_t j;
            for (j = i + 1; j < accumulator.size() && accumulator[j] == LIMIT; ++j)
                accumulator[j] = 0;
            if (j < accumulator.size())
                ++accumulator[j];
            else
                accumulator.push_back(1);
        }
    }
    return accumulator;
}

inline istream &operator >> (istream & in, vector<unsigned> & bigInteger) {
    string str;
    if (in >> str)
        bigInteger = stringToVector(str);
    else
        throw runtime_error("Input big integer failure"); // TODO treat this failure
    return in;
}

inline ostream &operator << (ostream & out, const vector<unsigned> & result) {
    for (vector<unsigned>::const_reverse_iterator it = result.rbegin(); it != result.rend(); ++it)
        out << *it;
    return out;
}


main() {
    vector<unsigned> x, y, result;
    cout << "x = ";
    cin >> x;
    cout << "y = ";
    cin >> y;
    result = x + y;
    cout << x << " + " << y << " = " << result << endl;
}
David Kennedy
  • 370
  • 2
  • 12
  • If `representationStream >> value;` fails, what should be pushed into `literal`? Is it necessary to copy the vector to stream it out? – Neil Kirk Oct 23 '15 at 22:17
  • I'm converting the string with the big number to a vector of integers, it's necessary for the sum operation. I'm searching a standard feature to simplify, but at moment it's what i need. User input validation isn't done because it's not the question here. What you say about fail? – David Kennedy Oct 23 '15 at 23:05
  • 1
    Use `ostream &operator << (ostream &out, const vector& result)` and see http://stackoverflow.com/questions/5431941/why-is-while-feof-file-always-wrong – Neil Kirk Oct 24 '15 at 17:43
  • Thank's @NeilKirk. Copy the vector on output operation isn't necessary. – David Kennedy Oct 24 '15 at 18:49
  • `representationStream >> value` can't really fail, because the stream is based on the local variable `string representation`, no other streams are operating on `representation`, but again thanks for enlightening quote. – David Kennedy Oct 24 '15 at 18:56
  • 1
    The string passed to `stringToVector` may not contain ints as expected. That could cause a failure. – Neil Kirk Oct 24 '15 at 19:33
  • It's really! @NeilKirk – David Kennedy Oct 25 '15 at 20:53
0

MPZ is your friend:

To set your large number e.g.

 mpz_set_str (MP_INT *integer, char *initial_value, int base)

And do your thing

  std::string add_large( char const * in1, char const * in2, int const SIZE)
  {
  MP_INT integ1, integ2, result;
  mpz_set_str (&integ1, in2, 10);
  mpz_set_str (&integ2, in2, 10);
  mpz_add (&result, &integ1, &integ2);
  char output[SIZE];
  mpz_get_str (output, 10, &result);
  return output;
  }
g24l
  • 3,055
  • 15
  • 28