1

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);
}
David Alber
  • 17,624
  • 6
  • 65
  • 71
Sam
  • 105
  • 1
  • 1
  • 12
  • 1
    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 Dec 07 '11 at 15:50
  • 4
    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: http://msdn.microsoft.com/en-us/library/tdkhxaks(v=vs.71).aspx – asawyer Dec 07 '11 at 15:52
  • 9
    `void main()` makes me cry. – Mat Dec 07 '11 at 15:54
  • 2
    `totalcounter` is at least 4 megabytes large! – Lightness Races in Orbit Dec 07 '11 at 16:04
  • 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 Dec 07 '11 at 16:42
  • You may want to implement the inverse of the collatz function with a (or many, if you wanna go bananas) sliding window of discovered numbers. – bitmask Dec 07 '11 at 16:52
  • I have got the answer. I am just marking one as answer, but everyone's coding techniques, suggestions and recommendations were useful and will continue to be. – Sam Dec 09 '11 at 13:55

3 Answers3

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!

Community
  • 1
  • 1
mwigdahl
  • 16,268
  • 7
  • 50
  • 64
  • `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. – bitmask Dec 07 '11 at 16:45
  • @bitmask: unless he's running a debug build, which for a novice in MSVC is likely – Mooing Duck Dec 07 '11 at 17:36
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).

Mike Seymour
  • 249,747
  • 28
  • 448
  • 644
  • 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. – Sam Dec 09 '11 at 14:05
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.

Blastfurnace
  • 18,411
  • 56
  • 55
  • 70