Segfault with array declaration

[BlackSheep]

I've gone through the following code multiple times to figure out why I was getting a segfault on every run, but nothing worked. I tried making the "arr" declaration global, which didn't change anything. I also put a cout statement after the declaration to see if something else was causing the fault, but it didn't print anything, so it must be "arr" that's causing the trouble. I even tried just using 100 000 ints, but that didn't help either. I'm on Ubuntu 11.10, and it's for Project Euler problem 14 if it matters. Thanks for any help.

#include <iostream>

int main()
{
int *arr = new int[1000000];
//Put std::cout<<"Check"; here, nothing.
for(int i = 1; i <= 1000000;++i)
{
int temp = i,count = 0;
while(temp != 1)
{
if(temp & 0x01){temp = temp*3+1;}
else{temp/=2;if(temp < i){count+=arr[temp-1];temp = 1;}}
++count;
}
arr[i-1] = count;
}
int max = 0,index = 0;
for(int i = 0; i < 1000000; ++i)
{
if(arr[i] > max){index = i;max = arr[i];}
}
std::cout<<index+1<<":"<<max<<std::endl;
delete[] arr;
}

[giannhssdra]

You are trying to access beyond the array.
If you have an array with 10 elements that means that you can access them from 0-9 but not 10.

In the first for you have you are trying to read the arr[1000000] element wich doesnt exist.

Try this

for( int i = 0 ; i < 1000000 ; i++ ) {
          //rest of your code
         }

[Peter87]

I think the problem is that temp gets too large so that is overflows.

[BlackSheep]

I know I'm initializing int i to 1, but I make sure to subtract 1 every time I use it to access an element in the array. Thanks though!

EDIT: @Peter87 Well I did do the "sanity check" right after initializing "arr", and I never got anything printed, so the error must be with the array, I just don't know why, and what to do.

[roberts]

I did a quick debug and temp is ending up as a negative number(-906427974 in fact), so when you do:

	count+=arr[temp-1];

you're accessing into a negative subscript. I have a feeling

temp = temp*3+1;

is overflowing the limits of a signed integer. No proof yet, but I think it's likely.

[BlackSheep]

Wow, thanks so much guys! I just ran it in MVC++ and I was indeed getting integer overflow! Changed temp to long long and everything worked perfectly! What threw me off was that my check didn't print! Thanks again!

[Peter87]

If you did something like this

if (temp < 0)
{
	// do something
}

the compiler probably optimized away the whole if statement. Signed overflow is undefined and there is no other way temp could get negative so the compiler is free to assume the code in the if statement will never run.