C/C++ Stackoverflow error in array of 1 million

Question

I am using VC++ 2010. I have written a short program to get Collatz conjecture chain for 1 million numbers in an long int array and get the highest number in series. When I try to run the code, I get stack overflow exception.

How should I get past this?

//Might have took un-needed headers
#include "stdafx.h"
#include "stdio.h"
#include "conio.h"
#include "iostream"
#include "fstream"
#include "string"
#include "list"
using namespace std;


//traverse the array for max term 
long int max_array(long int a[], long int num_elements)
{
    long int i, max=-32000;
    for (i=0; i<num_elements; i++)
    {
        if (a[i]>max)
        {
            max=a[i];
        }
    }
    return(max);
}

//recursive function to calculate and count based on Collatz_conjecture
long int Collatz( long int c1, long int currentcounter)
{
    if ( c1 == 1) return currentcounter;
    if ( c1 % 2 ==0)
    {
        currentcounter++;
        Collatz (c1/2, currentcounter);
    }
    else
    {
        currentcounter++;
        Collatz((3*c1)+1, currentcounter);
    }
}

void main()
{   
    long int  totalcounter[1000000]={0},t1,max;

    for (long  int i=1;i<1000001;i++)
    {
        totalcounter[i]++;
        totalcounter[i]=Collatz(i,totalcounter[i]); 
        printf("Collatz count of no: %li is %li \n",i,totalcounter[i]);
    }
    max = max_array(totalcounter, 1000000);
    printf("The max is %d\n", max);
}

fire up your favorite debugger and step through the code. then update your question with the result if you don't understand what is happening. — Fredrik Pihl
– Fredrik Pihl, Commented Dec 7, 2011 at 15:50
Well first I would not be recusring 1,000,000 times. It's obviously blowing your stack. You have two options - rewrite it to not use recursion, or increase your stack size: msdn.microsoft.com/en-us/library/tdkhxaks(v=vs.71).aspx — asawyer
– asawyer, Commented Dec 7, 2011 at 15:52
There's an off by 1 error in the loop as well, C++ & C is 0 indexed, init i to 0 and loop until i < 1000000. — Ylisar
– Ylisar, Commented Dec 7, 2011 at 16:42

Community · Accepted Answer · 2017-05-23 12:00:52Z

3

Stack memory is consumed by both automatic variables and recursive function calls. You use large amounts of both.

You can replace recursion with iteration (Way to go from recursion to iteration) and you can replace your automatic variable (the giant array) with a heap-allocated one (using new).

Doing both of these things should help you here. Just make sure when you go to an iterative approach for your Collatz function that you use a heap-allocated stack so you don't get the same problem all over again!

edited May 23, 2017 at 12:00

CommunityBot

11 silver badge

answered Dec 7, 2011 at 16:11

mwigdahl

16.6k7 gold badges52 silver badges64 bronze badges

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

2 Comments

bitmask Over a year ago

Collatz seems to be tail-recursive. As far as I know any decent compiler should implement this as iteration. But the large data on the stack is probably the problem.

Mooing Duck Over a year ago

@bitmask: unless he's running a debug build, which for a novice in MSVC is likely

Mike Seymour · Accepted Answer · 2011-12-07 16:30:00Z

2

The stack is typically of a fixed, fairly small size - perhaps a few megabytes. You are doing two things which could easily cause too much stack use:

Creating an automatic array of several megabytes
Calling a recursive function with no bounds on the recursion depth; unless the compiler is able to optimise the function into a loop, then each recursive call creates a new stack frame, so you will run out of stack if the Collatz path is too long.

The first can be fixed by using a dynamic array for the counters:

std::vector<long int> totalcounter;

or by not storing all the results, just the largest you've found after each iteration.

The second can be fixed by either checking that the compiler does optimise out the recursion, or implementing it iteratively; something like this (untested):

long int Collatz(long int c1)
{
    long int counter = 0;
    while (c1 != 1) {
        ++counter;
        c1 = (c1 % 2 == 0) ? c1/2 : 3*c1+1;
    }
    return counter;
}

(If you do decide to keep your recursive implementation, then you'll need to either pass currentcounter by reference, or update it with the return value of each recursive call and remember to return a value in all cases. Also, your array indexes in main() should run from 0 to N-1, not from 1 to N. And main() must return int, although you can leave out the return statement if you want).

edited Dec 7, 2011 at 16:30

answered Dec 7, 2011 at 16:16

Mike Seymour

256k30 gold badges467 silver badges658 bronze badges

1 Comment

Sam Over a year ago

Yes, I had to use vector to get the results. Also, your function to remove the recursion was copies as is except for one change. At i=113383 c1 value was crossing the max value allowed to be stored in a long int. I converted it to long long and saw that the value was 2482111348. One most important thing that I learned from your comment was I did not really need to store the values of c1. I am just storing the max value and the number that yields the max value I am adding the answer. Thanks again.

Blastfurnace · Accepted Answer · 2011-12-07 18:34:26Z

1

In computing the Collatz chain for such large numbers you are overflowing a long int. I assume that's why your recursive function is faulting. Try changing your c1 parameter to a 64-bit type such as long long.

I just tested this and when you reach the value 704511 the chain ranges as high as 56991483520. By the way, this is Project Euler problem 14.

Edit:

Move your declaration of the array totalcounter[] outside the main() function to make it a global. It's simply too large (~4MB) for automatic storage on the stack. Other alternatives would be to dynamically allocate the array or use std::vector.

Example of your code working here.

edited Dec 7, 2011 at 18:34

answered Dec 7, 2011 at 17:06

Blastfurnace

18.7k57 gold badges61 silver badges73 bronze badges

2 Comments

Sam Over a year ago

Tried changing long to long long but still its giving me an error.

Blastfurnace Over a year ago

@SameerShah: Added additional fix and link to a working example.

Collectives™ on Stack Overflow

C/C++ Stackoverflow error in array of 1 million

3 Answers 3

2 Comments

1 Comment

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related