Thread: int overflow

Hi,
This just pops into my head when I tried to generate a large array to be used as an example for my sorting algorithm. Is there a way to catch integer overflow in a loop? or is it better to use unsigned int when you think the for loop will be long? I know it's unlikely for me to use all the int, but it's interesting to see how it's done.

Unsigned integers can overflow too. The only difference is that overflow of an unsigned int has defined results (it wraps around, using modulo arithmetic).

There are three common practices.

1) Design your algorithm to avoid integer overflow (eg if you design the algorithm so the maximum int value ever needed is 4000, you know you will never overflow an int). This can often be done by selecting/enforcing appropriate limits before invoking your algorithm, or by ordering operations to avoid overflows. It is probably the rarest approach used in practice: having to think through what is really needed seems to defeat most programmers.

2) Check every operation before executing it, and take different steps if it would overflow. The trade-off of this is that it requires a run-time overhead - checking operations even if it could reasonably be inferred overflow won't occur.

3) Don't design to avoid overflow, don't check on the fly, and spend lots of time fielding customer complaints when they eventually encounter an overflow. Then spend lots of time finding the cause and retrofitting code to avoid or recover from the problem. Practically, this is done by the majority of programmers - particularly if someone else has to deal with customers or perform downstream maintenance.

Originally Posted by tabstop

What kind of integer overflow are you trying to catch? If you're talking about your loop index then you can compare it with std::numeric_limits::max or whatever C++ calls INT_MAX these days. So you will know ahead of time how many you can handle. (NOTE: This is different than "my array is too big to fit on the stack".) If you mean something else, you may want to be more specific.

I was thinking in term of loop index. I will check out what C++ used for INT_MAX. Now that you mentioned that, I do run into problem with the array too big to fit on the stack.

Code:

#include <iostream>
#include "heap.h"
#include <ctime>
#include <cstdlib>
#define N 3000000
int main()
{
  double arr[N];
  srand(time(0));
  for(int i = 0; i<N; i++)
    arr[i] = double (rand() % 100000 / 3.1 );
  Heap ar(arr,N);
  ar.sort();
  ar.show();
  return 0;
}

It appears that 3mil double values are a big much for my computer to handle. I get SEG FAULT running that code. Is there a way to tell how big an array I could create?

Originally Posted by grumpy

Unsigned integers can overflow too. The only difference is that overflow of an unsigned int has defined results (it wraps around, using modulo arithmetic).

There are three common practices.

I'll follow practice #3 then :-) .

Originally Posted by tabstop

Generally, you get what, about 4K of stack? Something very small, compared to the total memory of the machine. If you want larger, you'll have to do dynamic allocation with new/delete.

Gotcha. Thanks for the info. I didn't know that the stack is that small.

You should be able to change the stack size by using different compiler options.

Hmmm .... you ask about integer overflow, and then it turns into a discussion of stack size versus the size of an array that can be declared. Two different things.

Stack size is also determined by operating system settings, account quotas, etc.

Thank you all for the inputs. I really appreciate it.

Originally Posted by grumpy

Hmmm .... you ask about integer overflow, and then it turns into a discussion of stack size versus the size of an array that can be declared. Two different things.

Stack size is also determined by operating system settings, account quotas, etc.

My apology for veering off the topic of this discussion. I just wanted to learn how using large index could cause overflow in the loop, and this inadvertently leading to not able to create the static array.

Originally Posted by modwind

To be sure that your array has valid size and you are able to iterate through it, use constants instead of defines. The preferable type is "size_t" which is unsigned integer that can fit any possible size of any array.

Here is what your code should look like after adding dynamic allocation of array:

Code:

#include <iostream>
#include "heap.h"
#include <ctime>
#include <cstdlib>
const size_t N=3000000;

int main()
{
  double* arr=new double[N];
  srand(time(0));
  for(size_t i = 0; i<N; i++)
    arr[i] = double (rand() % 100000 / 3.1 );
  Heap ar(arr,N);
  ar.sort();
  ar.show();
  delete arr;
  return 0;
}

However, you can achieve better code using STL containers and algorithms. There is a standart sorting function in C++, why not to use it?

Code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>

const size_t N=3000000;

int main()
{
  std::vector<double> arr(N);
  srand(time(0));
  for(size_t i = 0; i<arr.size(); i++)
    arr[i] = double (rand() % 100000 / 3.1 );
  std::sort(arr.begin(),arr.end());
  for(size_t i = 0; i<arr.size(); i++)
    std::cout<<arr[i]<<std::endl;
  return 0;
}

Thank you Modwin for the advice. I'll be looking into that.