CODEWITHSUNDEEP
c++
Tim
Tim

Reputation: 171

C++ Euler-Problem 14 Program Freezing

I'm working on Euler Problem 14: http://projecteuler.net/index.php?section=problems&id=14

I figured the best way would be to create a vector of numbers that kept track of how big the series was for that number... for example from 5 there are 6 steps to 1, so if ever reach the number 5 in a series, I know I have 6 steps to go and I have no need to calculate those steps. With this idea I coded up the following:

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
int main()
{
    vector<int> sizes(1);
    sizes.push_back(1);
    sizes.push_back(2);
    int series, largest = 0, j;
    for (int i = 3; i <= 1000000; i++)
    {
        series = 0;
        j = i;
        while (j > (sizes.size()-1))
        {
            if (j%2)
            {
                j=(3*j+1)/2;
                series+=2;
            }
            else
            {
                j=j/2;
                series++;
            }
        }
        series+=sizes[j];
        sizes.push_back(series);
        if (series>largest)
            largest=series;
        cout << setw(7) << right << i << "::" << setw(5) << right << series << endl;
    }
        cout << largest << endl;
    return 0;
}

It seems to work relatively well for smaller numbers but this specific program stalls at the number 113382. Can anyone explain to me how I would go about figuring out why it freezes at this number?

Is there some way I could modify my algorithim to be better? I realize that I am creating duplicates with the current way I'm doing it: for example, the series of 3 is 3,10,5,16,8,4,2,1. So I already figured out the sizes for 10,5,16,8,4,2,1 but I will duplicate those solutions later.

Thanks for your help!

Upvotes: 4

Views: 1644

Answers (6)

Shashwat Black
Shashwat Black

Reputation: 1002

i stored the length of the chain for every number in an array.. and during brute force whenever i got a number less than that being evaluated for, i just added the chain length for that lower number and broke out of the loop.
For example, i already know the Collatz sequence for 10 is 7 lengths long. now when i'm evaluating for 13, i get 40, then 20, then 10.. which i have already evaluated. so the total count is 3 + 7.
the result on my machine (for upto 1 million) was 0.2 secs. with pure brute force that was 5 seconds.

Upvotes: 0

Winston Ewert
Winston Ewert

Reputation: 45039

The problem is overflow. Just because the sequence starts below 1 million does not mean that it cannot go above 1 million later. In this particular case, it overflows and goes negative resulting in your code going into an infinite loop. I changed your code to use "long long" and this makes it work.

But how did I find this out? I compiled your code and then ran it in a debugger. I paused the program execution while it was in the loop and inspected the variables. There I found that j was negative. That pretty much told me all I needed to know. To be sure, I added a cout << j; as well as an assert(j > 0) and confirmed that j was overflowing.

Upvotes: 1

Eelvex
Eelvex

Reputation: 9133

When i = 113383, your j overflows and becomes negative (thus never exiting the "while" loop).

I had to use "unsigned long int" for this problem.

Upvotes: 1

Simon Nickerson
Simon Nickerson

Reputation: 43169

Have you ruled out integer overflow? Can you guarantee that the result of (3*j+1)/2 will always fit into an int?

Does the result change if you switch to a larger data type?

EDIT: The last forum post at http://forums.sun.com/thread.jspa?threadID=5427293 seems to confirm this. I found this by googling for 113382 3n+1.

Upvotes: 3

IVlad
IVlad

Reputation: 43467

I think you are severely overcomplicating things. Why are you even using vectors for this?

Your problem, I think, is overflow. Use unsigned ints everywhere.

Here's a working code that's much simpler and that works (it doesn't work with signed ints however).

int main()
{

    unsigned int maxTerms = 0;
    unsigned int longest = 0;
    for (unsigned int i = 3; i <= 1000000; ++i)
    {
        unsigned int tempTerms = 1;
        unsigned int j = i;
        while (j != 1)
        {
             ++tempTerms;

             if (tempTerms > maxTerms)
             {
                 maxTerms = tempTerms;
                 longest = i;
             }

             if (j % 2 == 0)
             {
                 j /= 2;
             }
             else
             {
                 j = 3*j + 1;
             }
        }
    }

    printf("%d %d\n", maxTerms, longest);

    return 0;
}

Optimize from there if you really want to.

Upvotes: 1

Sean
Sean

Reputation: 3052

I would try using a large array rather than a vector, then you will be able to avoid those duplicates you mention as for every number you calculate you can check if it's in the array, and if not, add it. It's probably actually more memory efficient that way too. Also, you might want to try using unsigned long as it's not clear at first glance how large these numbers will get.

Upvotes: 0

Related Questions