Overflow or Memory error c++

Question

This could be considered a homework question. This problem is wel known: "you have a triangle of numbers and you have to find the greatest sum"

well no problem, I've made a solution in python some time ago, works flawless. But now in c++, the solution is 75256, my answer is 9729. So the problem is that the type short overflows.

So to fix this, I assumed changing my array to type int would solve everything.. but then, when declaring an array a[1001][1001] it freezes (i guess memory error).

anyone know what to do? I tried something with another int, and whenever the value in a got bigger than 32767 it would increment, but my solution then still is off 300? (the code works - tested on many smaller ones)

#include <iostream>
#include <fstream>

int main() {
    std::ofstream fout ("numtri.out");
    std::ifstream fin  ("numtri.in");
    short trifield[1001][1001] = {0};
    int Rows, tmp=0;
    fin >> Rows;
    for (int x = 0; x<Rows;x++) 
        for (int nr = 0; nr<=x;nr++){
            fin >> tmp;
            trifield[x][nr] = tmp;}

    for (int y = (Rows-2); y > -1; y--)
        for (int x = 0; x <= y+1; x++) {
            int a = trifield[y+1][x];
            int b = trifield[y+1][x+1];
            if (a > b) trifield[y][x] += a;
            else       trifield[y][x] += b;
        }
    fout << trifield[0][0] << std::endl;
    return 0;    
}

note: I'm not looking for the solution, just a good way to deal with overflows, examples appreciated!

Have you checked in the debugger what the program is doing when it hits the array and the array is defined as being of type int? — Timo Geusch
– Timo Geusch, Commented May 23, 2011 at 18:34

Howard · Accepted Answer · 2011-05-23 18:38:22Z

3

If you have issues with memory try to assign your array dynamically:

short** trifield = new short[1001][1001];

edited May 23, 2011 at 18:38

answered May 23, 2011 at 18:33

Howard

39.3k9 gold badges68 silver badges85 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Buster Over a year ago

Could you please explain a little more?

Howard Over a year ago

@Buster if you allocate memory directly it is done in stack space. This space generally is quite limited. With dynamical allocation instead you can access much more memory.

Bo Persson Over a year ago

And you also have much more memory if you move the array outside of main. No need for dynamic allocation here, as there is only one array and its size is known.

Andrew · Accepted Answer · 2011-05-23 18:34:26Z

2

You have an array of 1001x1001 shorts... that's 1002001*2 bytes. That's all going on your local stack. Depending on your system that could be TOO big. Try allocating the space for your 'trifield' with a malloc instead. See what that does for you

answered May 23, 2011 at 18:34

Andrew

2,59817 silver badges9 bronze badges

2 Comments

Andrew Over a year ago

and remember, what thou mallocs, thou must set free

user2100815 Over a year ago

And as the question is about C++, don't use malloc anyway.

Bo Persson · Accepted Answer · 2011-05-23 18:39:02Z

1

You get a stack overflow instead of a numeric overflow!

Move the array to static memory outside of main, so it doesn't use the stack.

answered May 23, 2011 at 18:39

Bo Persson

92.9k31 gold badges153 silver badges211 bronze badges

Comments

Jim Clay · Accepted Answer · 2011-05-23 18:40:35Z

1

The way I check for overflow is to check for an obviously bogus result. For instance,

if (myInt + 1 < myInt) {
    // Overflow condition
    cerr << "Overflow" << endl;
}
else {
    myInt++;
}

answered May 23, 2011 at 18:40

Jim Clay

1,0039 silver badges24 bronze badges

Comments

BЈовић · Accepted Answer · 2011-05-23 18:34:46Z

0

Overflowing an int is an UB. Overflowing an unsigned int value is defined in the standard.

So, the only way is to manually check the values before doing the operation, and make sure it doesn't overflow.

answered May 23, 2011 at 18:34

BЈовић

64.7k45 gold badges181 silver badges284 bronze badges

Collectives™ on Stack Overflow

Overflow or Memory error c++

5 Answers 5

3 Comments

2 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

3 Comments

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related