Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: C++ 3n+1 Problem

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


    using namespace std;

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

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


    cout<<" "<<cmax;

    return 0;

    int process(int x)
    int count;


    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?
  2. jcsd
  3. Jul 18, 2007 #2
    Unsigned int can go from 0 to 65536. Try using unsigned long.
    BTW, i dont know if there's a 32 bit fundamental datatype ; maybe you're supposed to use user defined data types like arrays
  4. Jul 18, 2007 #3

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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.

    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>).
  5. Jul 18, 2007 #4

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

    cout's or printfs are your friend.
  6. Jul 20, 2007 #5
    How did you find that count? And how do you use uint32_t ?
  7. Jul 20, 2007 #6

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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 231-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>.
  8. Jul 20, 2007 #7
    u should be able to declare it as
    uint32_t...it'd be like using u_int64_t or int64_t.
  9. Jul 20, 2007 #8
    By default, arent int's 2 bits and floats 4 bits, double 8 bits and long double 16 bits?
  10. Jul 20, 2007 #9

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
  11. Jul 20, 2007 #10
    simple test to help you go along way...
  12. Aug 5, 2007 #11
    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 cant spot the major flaw. Could you give me a hint DH?
  13. Aug 5, 2007 #12

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Are you using unsigned long ints everywhere you might have a problem with signed integers? (Hint: the original program is not.)
  14. Aug 6, 2007 #13
    Yes... thats exactly what I did, and it worked... I got 525 as the longest cycle length. Thank you so very much!!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook