Solving C++ 3n+1 Problem - Max Cycle Length w/ Code

[chaoseverlasting]

Im trying to find the maximum cycle length, but the program hangs when i>100000 or so. Here's the code:

#include<iostream>

using namespace std;

int main()
{
unsigned int i, j;
int count, cmax;

int process(int x);
count<<"Enter range:\nFrom: ";
cin>>i;
count<<"\nTo: ";
cin>>j;
count<<i<<" "<<j;

for(;i<=j;i++)
{
count=process(i);
if(count>cmax)
cmax=count;

}
count<<" "<<cmax;

return 0;
}



int process(int x)
{
int count;
for(count=1;x!=1;++count)
{

if(x%2==0)
x/=2;
else
x=3*x+1;

}
return count;
}

I think the values become too large for integers to handle. I was told to assume that the values would not exceed 32 bits, aren't integers 2 bits though?

 

[f(x)]

I think the values become too large for integers to handle. I was told to assume that the values would not exceed 32 bits, aren't integers 2 bits though?

Unsigned int can go from 0 to 65536. Try using unsigned long.
BTW, i don't know if there's a 32 bit fundamental datatype ; maybe you're supposed to use user defined data types like arrays

 

[D H]

Im trying to find the maximum cycle length, but the program hangs when i>100000 or so. Here's the code:

...

I think the values become too large for integers to handle. I was told to assume that the values would not exceed 32 bits, aren't integers 2 bits though?

Using unsigned ints is fine, using ints is not. You aren't using unsigned ints in a very critical calculation. Hint: your problem occurs with i=113383, count=120.

Unsigned int can go from 0 to 65536. Try using unsigned long.
BTW, i don't know if there's a 32 bit fundamental datatype ; maybe you're supposed to use user defined data types like arrays

This is not true with most modern compilers/modern machines. Unsigned ints usually go from 0 to 4294967295 nowadays.

If you want guaranteed size, use uint32_t (#include <stdint.h>).

 

[neurocomp2003]

x=3*x+1;

by pen&paper...calculate when your forloop should terminate given the condition ou have stated

count's or printfs are your friend.

 

[chaoseverlasting]

Using unsigned ints is fine, using ints is not. You aren't using unsigned ints in a very critical calculation. Hint: your problem occurs with i=113383, count=120.

If you want guaranteed size, use uint32_t (#include <stdint.h>).

How did you find that count? And how do you use uint32_t ?

 

[D H]

How did you find that count?

The biggest problem is that you are not using unsigned ints in some very critical places. The maximum value for a signed int (assuming 32 bit integers) is 2³¹-1=2147483647, which means the calculation x = 3*x + 1 will fail when x exceeds than (2147483647-1)/3=715827882. So how did I find when this occurs? I added a test for this event.

BTW, your program has another serious flaw. You should be able to do some simple cases by hand (e.g., 1, 2, 3). Do you get the right answers?

And how do you use uint32_t ?

You don't need this, but simply #include <stdint.h>.

 

[neurocomp2003]

u should be able to declare it as
uint32_t...it'd be like using u_int64_t or int64_t.

 

[chaoseverlasting]

The biggest problem is that you are not using unsigned ints in some very critical places. The maximum value for a signed int (assuming 32 bit integers) is 2³¹-1=2147483647, which means the calculation x = 3*x + 1 will fail when x exceeds than (2147483647-1)/3=715827882. So how did I find when this occurs? I added a test for this event.

BTW, your program has another serious flaw. You should be able to do some simple cases by hand (e.g., 1, 2, 3). Do you get the right answers?



You don't need this, but simply #include <stdint.h>.

By default, arent int's 2 bits and floats 4 bits, double 8 bits and long double 16 bits?

 

[D H]

I take it you mean bytes, not bits. 2 bits doesn't represent much at all: 0,1,2,3, done. 2 bytes represents 0 to 65535.

The answer is still no. An unsigned short int and an unsigned int must be able to hold all integer values from 0 to 65535 (16 bits) while an unsigned long int must be able to hold all integer values from 0 to 4294967295 (32 bits). There is nothing to stop a compiler vendor from doing more than the minimum.

In particular, an "int" is supposed to be the "natural" size for the computer in question. In the days of 186 PCs, the natural word size was 16 bits, so ints were 16 bits on those machines. The natural word size on a 32-bit architecture machine is 32 bits; ints are much more likely to be 32 bits than 16 bits on such machines. Unless you work with a dinosaur, your computer has a 32-bit architecture, minimum, and ints will be 32 bits wide.

 

[neurocomp2003]

simple test to help you go along way...
sizeof(datatype)...

 

[chaoseverlasting]

Im sorry to bring this up again, but I've been busy with college.

Im getting the right results when I run the program up until it hangs (I checked the sample input/output of the problem). I changed the int's to unsigned long int, but I still get the same problem... the program hangs somewhere around n=110000. I can't spot the major flaw. Could you give me a hint DH?

 

[D H]

Are you using unsigned long ints everywhere you might have a problem with signed integers? (Hint: the original program is not.)

 

[chaoseverlasting]

Yes... that's exactly what I did, and it worked... I got 525 as the longest cycle length. Thank you so very much!