Chaz Chaz - 2 months ago 34
C++ Question

Find Magic Numbers C++

Magic Numbers

A positive integer is “magic” if, and only if, it can be reduced to 1 by repeatedly dividing it by 2 if it’s even or multiplying it by 3 and then adding 1 if it’s odd. So, for example, 3 is magic because 3 reduces first to 10 (3*3+1), then to 5 (10/2), then to 16 (5*3+1), then to 8 (16/2), then to 4 (8/2), then to 2 (4/2), and finally to 1 (2/2). The magic numbers hypothesis states that all positive integers are magic, or, formally: ∀x ∈ Z, MAGIC(x) where MAGIC(x) is the predicate “x is magic”.

We are supposed to develop a C++ program to find "Magic Numbers" from 1 to 5 Billion. It is supposed to take 80 seconds or less if being done correctly. Mine takes approximately 2 hours, and the example program we were given would take 14 days. Here is my code, what can I do to speed it up? Am I missing obvious optimization issues?

#include <iostream>
using namespace std;

bool checkMagic(unsigned long number);

int main()
{
for(unsigned long i = 1; i <= 5000000000; i++)
{
if(i % 1000000 == 0)
{
//only print out every 1000000 numbers to keep track, but slow it down
//by printing out every single number
cout<<i<<endl;
}

if(!checkMagic(i))
{
//not magic
cout<<i<<" not a magic number"<<endl;
break;
}
}
}

bool checkMagic(unsigned long number)
{
if(number % 2 == 0)
{
number = number / 2;
}
else
{
number = (number * 3) + 1;
}

if(number != 1)
{
checkMagic(number);
}

return 1;
}

Answer

There are several correct comments stating that the correct approach here for verifying the Collatz conjecture (up to 5B), is through memoization, but the discussion then continued to which data structure is appropriate for the memoization. I think it is possible to do the memoization without any data structures here, using the following small program (which runs in ~40 secs, BTW):

#include <iostream>

using namespace std;

int main()
{
    size_t max_num = 5000000000;
    for(unsigned long i = 1; i <= max_num; i++)
    {   
        if(i % 1000000 == 0)
            cout << i << endl;

        size_t num = i;
        while(num != 1)
        {
           if(num < i)
               break;
           num = num % 2 == 0? num / 2: 3 * num + 1;
        }
    }
}   

The memoization is implicit in the lines

        if(num < i)
            break;

Why does this work? Because the Collatz HOTPO conjecture is

The conjecture is that no matter what number you start with, you will always eventually reach 1.

with, the converse being, that, if a number is not magic, it will loop around forever. Consequently, just by the fact that the iteration is at i, is enough to deduce that no numbers were found below i.

Comments