Vector help, subscript out of range, and basic tutoring

[yogi_bear_79]

Distant learning student. My lab is to write a function to perform
the addition of large integers, with no limit to the number of digits.
(Also have to do a subtraction, division, and multiplication lab). It
is suggested to treat each number as a sequence. This is what I have
so far, this is rough code just to get it working:

1. I can't get the syntax correct on the 'for' statement in the
longAdditon function. No matter what I try I get a run-time error
subscript out of range.

2. Being very much a rookie, I am sure this isn't the prettiest code;
I am open to ideas, hints, etc. Bear in mind that I am basically self
taught here, and more of a systems admin than a programmer.


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

int longAdditon(vector<int> &vOne, vector<int> &vTwo);
string toStr(int &i);

int main ()
{
vector<int> vOne, vTwo;
string one, two;
int x = 0;
size_t r;

cin>>one;
r = one.length();

for (int x = 0; x < r; x++){
vOne.push_back(int(one[x] - '0'));
}

cin>>two;
r = two.length();

for (int x = 0; x < r; x++){
vTwo.push_back(int(two[x] - '0'));
}

longAdditon(vOne, vTwo);
}

int longAdditon(vector<int> &vOne, vector<int> &vTwo)
{
int sum, carryOver = 0;
string results;

for(size_t x = vOne.size()-1; x >= 0; x--){
sum = vOne[x] + vTwo[x] + carryOver;
if(sum >= 10){
carryOver = sum - 9;
sum = 0;
}
else{
carryOver = 0;
}
results = results + toStr(sum);
}
string::reverse_iterator rit;
for ( rit=results.rbegin() ; rit < results.rend(); rit++ )
cout << *rit;

return 0;
}

string toStr(int &i)
{
//convert output double to char
std::string s;
std::stringstream out;
out << i;
s = out.str();
return s;
}

 

[Daniel T.]

Distant learning student.  My lab is to write a function to perform
the addition of large integers, with no limit to the number of digits.
(Also have to do a subtraction, division, and multiplication lab). It
is suggested to treat each number as a sequence.  This is what I have
so far, this is rough code just to get it working:

1.  I can't get the syntax correct on the 'for' statement in the
longAdditon function.  No matter what I try I get a run-time error
subscript out of range.

2.  Being very much a rookie, I am sure this isn't the prettiest code;
I am open to ideas, hints, etc. Bear in mind that I am basically self
taught here, and more of a systems admin than a programmer.

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

int longAdditon(vector<int> &vOne, vector<int> &vTwo);
string toStr(int &i);

int main ()
{
        vector<int> vOne, vTwo;
        string one, two;
        int x = 0;
        size_t r;

        cin>>one;
        r = one.length();

        for (int x = 0; x < r; x++){
                vOne.push_back(int(one[x] - '0'));
        }

        cin>>two;
        r = two.length();

        for (int x = 0; x < r; x++){
                vTwo.push_back(int(two[x] - '0'));
        }

        longAdditon(vOne, vTwo);

}

int longAdditon(vector<int> &vOne, vector<int> &vTwo)
{
        int sum, carryOver = 0;
        string results;

        for(size_t x = vOne.size()-1; x >= 0; x--){

Note, because 'x' is of type size_t, it will *never* be less than 0.
As such,
x >= 0 will always be true.

I suggest you look into vector::rbegin() and vector::rend().

Even better would be to use std::transform to add each element of the
two vectors together, then go through the result and take care of the
carryover as a separate operation.

Lastly, you really should wrap the whole thing into a class...

class BigNum {
public:
explicit BigNum( const std::string& s );
std::string print() const;
};

BigNum add( const BigNum& left, const BigNum& right );

Later, when you learn about operator overloading, you can make it so
that someone can use the '+' to add two bigNums, like this:

BigNum x, y;
// put values in them
BigNum z = x + y;

a BigNumber class is a great way to learn the language.

 

[Paul]

for(size_t x = vOne.size()-1; x >= 0; x--){
sum = vOne[x] + vTwo[x] + carryOver;

In addition, why are you assuming that the vectors are the same size? What
if you entered a 2 digit number in vOne, and a 1 digit number in vTwo? In
that case, you have an illegal access on the very first iteration, since
there is no vTwo[1] available.

- Paul

 

[Barry]

Distant learning student. My lab is to write a function to perform
the addition of large integers, with no limit to the number of digits.
(Also have to do a subtraction, division, and multiplication lab). It
is suggested to treat each number as a sequence. This is what I have
so far, this is rough code just to get it working:

1. I can't get the syntax correct on the 'for' statement in the
longAdditon function. No matter what I try I get a run-time error
subscript out of range.

size_t is "unsigned", so it's never negative, then "i >= 0" is always
true.
you can try

<code>
size_t n = 0;
std::cout << (n -1) << std::endl;
</code>

to see what's going on.

2. Being very much a rookie, I am sure this isn't the prettiest code;
I am open to ideas, hints, etc. Bear in mind that I am basically self
taught here, and more of a systems admin than a programmer.

You can google "BigInterger C++"

 

[Kai-Uwe Bux]

Distant learning student. My lab is to write a function to perform
the addition of large integers, with no limit to the number of digits.
(Also have to do a subtraction, division, and multiplication lab). It
is suggested to treat each number as a sequence. This is what I have
so far, this is rough code just to get it working:

1. I can't get the syntax correct on the 'for' statement in the
longAdditon function. No matter what I try I get a run-time error
subscript out of range.

2. Being very much a rookie, I am sure this isn't the prettiest code;
I am open to ideas, hints, etc. Bear in mind that I am basically self
taught here, and more of a systems admin than a programmer.


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

int longAdditon(vector<int> &vOne, vector<int> &vTwo);
string toStr(int &i);

int main ()
{
vector<int> vOne, vTwo;
string one, two;
int x = 0;
size_t r;

cin>>one;
r = one.length();

for (int x = 0; x < r; x++){
vOne.push_back(int(one[x] - '0'));
}

cin>>two;
r = two.length();

for (int x = 0; x < r; x++){
vTwo.push_back(int(two[x] - '0'));
}

longAdditon(vOne, vTwo);
}

int longAdditon(vector<int> &vOne, vector<int> &vTwo)

You probably want those arguments to be const references.

{
int sum, carryOver = 0;
string results;

for(size_t x = vOne.size()-1; x >= 0; x--){
sum = vOne[x] + vTwo[x] + carryOver;
if(sum >= 10){
carryOver = sum - 9;
sum = 0;
}
else{
carryOver = 0;
}
results = results + toStr(sum);
}
string::reverse_iterator rit;
for ( rit=results.rbegin() ; rit < results.rend(); rit++ )
cout << *rit;

return 0;
}

string toStr(int &i)
{
//convert output double to char

This comment is a lie.

std::string s;
std::stringstream out;
out << i;
s = out.str();
return s;
}

You have settled on an unfortunate convention. You store the number 12353 as

v[0] = 1
v[1] = 2
v[3] = 3
v[4] = 5
v[5] = 3

it would make the implementation of arithmetic much simpler if you did it
the other way around:

v[0] = 3
v[1] = 5
v[2] = 3
v[4] = 2
v[5] = 1

The reason is that you then have

value as a number = sum_i v * 10^i

Recall that addition of integers goes works from the low order digits to the
higher order digits.


As for converting a string into a vector of digits, you could do (using
boost::lambda):

std::transform( str.rbegin(), str.rend(), std::back_inserter( vec ),
_1 - '0' );


Your longAddition() function mixes responsibilities: you should have a
function that computes a sum and a function that converts a long_int into a
string.



Best

Kai-Uwe Bux

 

[yogi_bear_79]

 for(size_t x = vOne.size()-1; x >= 0; x--){
  sum = vOne[x] + vTwo[x] + carryOver;

In addition, why are you assuming that the vectors are the same size?  What
if you entered a 2 digit number in vOne, and a 1 digit number in vTwo?  In
that case, you have an illegal access on the very first iteration, since
there is no vTwo[1] available.

- Paul

Paul,

At the point in the program I am, I have controlled input (i.e. each
vector is same .size). I had thought of it, and figured I could
capture the difference like so:
if (vOne.size() < vTwo.size()){
pad = vTwo.size() - vOne.size();
}
else if (vTwo.size() < vOne.size()){
pad = vOne.size() - vTwo.size();
}

Daniel,
I played with vector::rbegin() and vector::rend(), but didn't really
get anywhere with it, I did change x to a int and everything works.

ALL,

I have the Addition/Subtraction pretty much figured out, just some
cleaning yet. I have no idea how to implement the multiplication &
divison in this style, I can't even imagine how to do it on paper this
way!



Then I thought I would add (pad) amount of zeros to the begining of
the vector that was short. Currently I am not sure how to add the
zeros to the front of the vector.

 

[yogi_bear_79]

 for(size_t x = vOne.size()-1; x >= 0; x--){
  sum = vOne[x] + vTwo[x] + carryOver;

In addition, why are you assuming that the vectors are the same size?  What
if you entered a 2 digit number in vOne, and a 1 digit number in vTwo?  In
that case, you have an illegal access on the very first iteration, since
there is no vTwo[1] available.

- Paul

Paul,

At the point in the program I am, I have controlled input (i.e. each
vector is same .size). I had thought of it, and figured I could
capture the difference like so:
if (vOne.size() < vTwo.size()){
pad = vTwo.size() - vOne.size();


}


else if (vTwo.size() < vOne.size()){
pad = vOne.size() - vTwo.size();


}
Then I thought I would add (pad) amount of zeros to the begining of
the vector that was short. Currently I am not sure how to add the
zeros to the front of the vector.

Daniel,
I played with vector::rbegin() and vector::rend(), but didn't really
get anywhere with it, I did change x to a int and everything works.

ALL,


I have the Addition/Subtraction pretty much figured out, just some
cleaning yet. I have no idea how to implement the multiplication &
divison in this style, I can't even imagine how to do it on paper
this
way!

 

[Daniel T.]

Then I thought I would add (pad) amount of zeros to the begining of
the vector that was short. Currently I am not sure how to add the
zeros to the front of the vector.

Switch to a deque and use push_front.

 

[yogi_bear_79]

Switch to a deque and use push_front.

In only the true dignity of rookie code I wrote this funciton to
handle the diff between vector sizes

vector<int> pad(vector<int> &vSml, vector<int> &vLrg)
{
size_t pad;

pad = vLrg.size() - vSml.size();
vector<int> vTmp(pad,0);
for (int i = 0; i < vSml.size(); i++)
vTmp.push_back(vSml);

return vTmp;
}

OK, Additon & Subtraction are done.....Any hints on the algorithim for
Multiplication & Subtraction??

 

[James Kanze]

Distant learning student. My lab is to write a function to perform
the addition of large integers, with no limit to the number of digits.
(Also have to do a subtraction, division, and multiplication lab). It
is suggested to treat each number as a sequence. This is what I have
so far, this is rough code just to get it working:
1. I can't get the syntax correct on the 'for' statement in the
longAdditon function. No matter what I try I get a run-time error
subscript out of range.
2. Being very much a rookie, I am sure this isn't the prettiest code;
I am open to ideas, hints, etc. Bear in mind that I am basically self
taught here, and more of a systems admin than a programmer.
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
using namespace std;
int longAdditon(vector<int> &vOne, vector<int> &vTwo);
string toStr(int &i);
int main ()
{
vector<int> vOne, vTwo;
string one, two;
int x = 0;
size_t r;
cin>>one;
r = one.length();
for (int x = 0; x < r; x++){
vOne.push_back(int(one[x] - '0'));
}
cin>>two;
r = two.length();
for (int x = 0; x < r; x++){
vTwo.push_back(int(two[x] - '0'));
}
longAdditon(vOne, vTwo);
}
int longAdditon(vector<int> &vOne, vector<int> &vTwo)
{
int sum, carryOver = 0;
string results;
for(size_t x = vOne.size()-1; x >= 0; x--){

Note, because 'x' is of type size_t, it will *never* be less
than 0. As such, x >= 0 will always be true.

The "standard" syntax for such a loop would be:

size_t x = vOne.size() ;
while ( x > 0 ) {
--x ;
// ...
}

Still, better solutions are possible here.

I suggest you look into vector::rbegin() and vector::rend().

Or use a little endian representation, with vector::begin() and
vector::end(). For a number of reasons, that's the way I'd go.

Even better would be to use std::transform to add each element
of the two vectors together, then go through the result and
take care of the carryover as a separate operation.

I'd be interested in seeing how you do that. Determining after
the fact that a carry should have taken place isn't that
obvious. I know how I'd do it, but if for some reason I had to
use such obscure tricks, I'd certainly explain it carefully in
comments. Much better to just be clean and correct (especially
as in this case, the clean solution will also be the fastest).

Lastly, you really should wrap the whole thing into a class...

class BigNum {
public:
explicit BigNum( const std::string& s );
std::string print() const;
};

BigNum add( const BigNum& left, const BigNum& right );

Later, when you learn about operator overloading, you can make
it so that someone can use the '+' to add two bigNums, like
this:

BigNum x, y;
// put values in them
BigNum z = x + y;

a BigNumber class is a great way to learn the language.

I'm not sure; it requires mastering a lot of semi-mathematical
issues that aren't necessarily everyone's cup of tea. (Most of
the problems in getting division correct and sufficently fast
are independent of the language.)

 

[James Kanze]

Switch to a deque and use push_front.

Use a little endian representation and stick with push_back.

In the end, he'll doubtlessly want to change the base from 10;
10 makes very inefficient use of the memory. When he gets
there, he'll have to use the standard conversion routines for
input and output. Until then, nothing prevents him from
inputting as he currently does, then using std::reverse to end
up with a little endian representation.

Not, of course, that using push_back or push_front is a
particularly good idea. I'd go with insert( v.back(), sizeDiff,
0 ). (Or with v.front() as first argument if you stick with big
endian.)

 

[James Kanze]

I have the Addition/Subtraction pretty much figured out, just some
cleaning yet. I have no idea how to implement the multiplication &
divison in this style, I can't even imagine how to do it on paper
this way!

Knuth, vol.2 has a very good explination of this. That's where
I'd start.