# Thread: c wont run my

1. ## c wont run my

hi forum
i've been trying to solve this problem:
The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

the code i've written looks like this:
Code:
```#include <stdio.h>
#include <stdlib.h>

int main()
{
int *a, seq, maxseq=1, i, j, num=1;
a=malloc(1000000 * sizeof(int));
if(a==NULL){
printf("........!");
return 1;
}
a[1]=1;
for(i=2; i<1000000; i++){
seq=0;
j=i;
while(j>=i){
if(j%2)
j=3*j+1;
else
j/=2;
seq++;
}
seq+=a[j];
a[i]=seq;
if(seq>maxseq){
maxseq=seq;
num=i;
}
}
free(a);
printf("%d",num);

return 0;
}```
the problem is every time i try to run it i get a message that says:
"code.c has stopped working" and it shuts down... it works when i run it up to 100,000
or so but it wont work for 1,000,000- can anyone help??
btw im using code::blocks with GNU GCC compiler, dont know if thats relevant..

2. Originally Posted by ajl913
hi forum
i've been trying to solve this problem:
[I]The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)
This one intrigues me... I ran your code and here's a screen snip of what I got...

Attachment 10356

This is happening right at the end of your while (j <= i) and it's being caused by
accessing the array in seq += a[j]; although I don't see exactly why you're doing that.

3. Aren't you supposed to be stopping at j == 1?

4. the program adds the sequence in place a[j] to what it counted so far to save time..
once i know the number has reached a previous number which i already checked i can just add that numbers sequence

5. thanks tater i changed i and j to unsigned longs and now it works

6. thanks tater i changed i and j to unsigned longs and now it works
Except that's not the problem.

The problem with invoking undefined behavior is that you could "fix" something entirely unrelated, and get positive results. Commontater's access violation message is more typical of out of bounds array access.

What do we have in the program that looks like that?
Code:
``` a[1]=1;
for(i=2; i<1000000; i++){```
The acceptable range for an array is from 0 to n-1, inclusive. In this case, n is one million.

7. Originally Posted by whiteflags
Except that's not the problem.

The problem with invoking undefined behavior is that you could "fix" something entirely unrelated, and get positive results. Commontater's access violation message is more typical of out of bounds array access.

What do we have in the program that looks like that?
Code:
``` a[1]=1;
for(i=2; i<1000000; i++){```
The acceptable range for an array is from 0 to n-1, inclusive. In this case, n is one million.
In this case if he starts the *calculations* at 0 or 1 it just hangs.

As for the array... totally unnecessary... I elminated that from the program and got this...

Attachment 10357

Code:
```#include "global.h"
#include <errorx.h>
#includ <windows.h>

int _cdecl main(int argc, char *argv[])
{

unsigned int seq, maxseq=0, i, j, num=0;
unsigned int ticks;

ticks= GetTickCount();

for(i=2; i<1000000; i++){
seq=0;
j = i;
while(j >= i){
if(j & 1)
j=(j * 3) + 1;
else
j /= 2;
seq++;
}
if(seq>maxseq){
maxseq=seq;
num=i;
}
}
ticks = GetTickCount() - ticks;
printf("\nThe longest sequence results from %d, taking %d iterations\n",num,maxseq);
printf("Runtime = %d milliseconds\n\n",ticks);
return 0; }```

8. Ok one more pass, this time altering the code to correctly bring j down to 1...

Attachment 10358

Code:
```#include "global.h"
#include <errorx.h>
#include <windows.h>

int _cdecl main(int argc, char *argv[])
{ unsigned int ticks;
unsigned int seq, maxseq=0, i, num=0;
register unsigned int j;

ticks= GetTickCount();

for(i=2; i<1000000; i++)
{ seq=0;
j = i;
while(j > 1)
{ if(j & 1)
j=(j * 3) + 1;
else
j /= 2;
seq++; }
if(seq>maxseq){
maxseq=seq;
num=i;
}
}
ticks = GetTickCount() - ticks;
printf("\nThe longest sequence results from %d, taking %d iterations\n",num,maxseq);
printf("Runtime = %d milliseconds\n\n",ticks);
return 0; }```
With j as a register variable it took nearly 200ms off the time.
Using & instead of % to check for odd numbers saved an additional 80ms.

9. Originally Posted by CommonTater
With j as a register variable it took nearly 200ms off the time.
That is surprising since conventional wisdom is that the register keyword is useless because modern compilers are able to determine very well what variables should take advantage of registers.

10. Originally Posted by laserlight
That is surprising since conventional wisdom is that the register keyword is useless because modern compilers are able to determine very well what variables should take advantage of registers.
I was surprised too... However, there may have been a secondary effect here... In PellesC before the register keyword is used, you have to enable other optimizations ("Increase Speed More", in the IDE Ox and Ot at the command line) I didn't check, but it's entirely possible the gain was more due to those flags than the keyword.

EDIT: I checked with the optimizations on then with and without the register keyword... about 12ms faster with the keyword, so apparently it does matter (a little bit) on PellesC. But your compiler's mileage may vary

That was fun... Thanks to the OP for giving me a challenge today!

11. Some compilers make no effort to optimize unless you say so explicitly, so they generate code in a very formulaic and not-so-efficient way, meaning they don't make best use of registers. But they will try to honor the register keyword if you say so. It appears that can often be trumped by optimizations however. We had an interesting discussion going about this a few weeks ago: http://cboard.cprogramming.com/c-pro...ster-loop.html.

12. Oh, and is the OP aware that even for some numbers below 1,000,000, they will climb beyond the bounds of a 32-bit int before resolving to 1? There are likely going to be overflow issues in his/her code to consider. If possible, use something like uint64_t.

13. Originally Posted by anduril462
Oh, and is the OP aware that even for some numbers below 1,000,000, they will climb beyond the bounds of a 32-bit int before resolving to 1? There are likely going to be overflow issues in his/her code to consider. If possible, use something like uint64_t.
The overflow was the original problem... So yes it's a real concern.
No errors with unsigned ints though.