int overflow

This is a discussion on int overflow within the C++ Programming forums, part of the General Programming Boards category; Hi, This just pops into my head when I tried to generate a large array to be used as an ...

  1. #1
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    460

    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.
    Last edited by nimitzhunter; 12-11-2010 at 08:48 PM.
    "All that we see or seem
    Is but a dream within a dream." - Poe

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  3. #3
    Registered User
    Join Date
    Jun 2005
    Posts
    6,678
    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.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Sunshine, and read this, this, and this before posting again.

  4. #4
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    460
    Quote Originally Posted by tabstop View Post
    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?


    Quote Originally Posted by grumpy View Post
    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 :-) .
    "All that we see or seem
    Is but a dream within a dream." - Poe

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  6. #6
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    460
    Quote Originally Posted by tabstop View Post
    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.
    "All that we see or seem
    Is but a dream within a dream." - Poe

  7. #7
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    You should be able to change the stack size by using different compiler options.
    "I am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008

    "the internet is a scary place to be thats why i dont use it much." - billet, 03/17/2010

  8. #8
    Registered User
    Join Date
    Jun 2005
    Posts
    6,678
    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.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Sunshine, and read this, this, and this before posting again.

  9. #9
    Registered User modwind's Avatar
    Join Date
    Dec 2010
    Posts
    15
    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;
    }

  10. #10
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    460
    Thank you all for the inputs. I really appreciate it.

    Quote Originally Posted by grumpy View Post
    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.

    Quote Originally Posted by modwind View Post
    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.
    "All that we see or seem
    Is but a dream within a dream." - Poe

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Formatting Issue?
    By matthewlane in forum C Programming
    Replies: 1
    Last Post: 11-15-2010, 05:55 PM
  2. Producer/Consumer - problems creating threads
    By hansel13 in forum C Programming
    Replies: 47
    Last Post: 08-20-2010, 03:02 PM
  3. Working with random like dice
    By SebastionV3 in forum C++ Programming
    Replies: 10
    Last Post: 05-26-2006, 10:16 PM
  4. Replies: 2
    Last Post: 03-24-2006, 08:36 PM
  5. Half-life SDK, where are the constants?
    By bennyandthejets in forum Game Programming
    Replies: 29
    Last Post: 08-25-2003, 12:58 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21