Find Magic Numbers C++

Question

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 1

This question basically asks to verify the Collatz Conjecture up to 5B.

I think the key here is, for each number n we are checking, to view the optimistic scenario and the pessimistic scenario, and to check the optimistic one before reverting to the pessimistic one.

In the optimistic scenario, as we we modify n according to the n / 2 ; 3n + 1 rule, the sequence of numbers will:

• in a finite number of steps become smaller than n (in which case we can check what we know about that smaller number).

• will not cause an overflow in the steps.

(on which, as TonyK correctly notes, we cannot rely (even not on the first)).

So, for the optimistic scenario, we can use the following function:

#include <unordered_set>
#include <set>
#include <iostream>
#include <memory>
#include <list>
#include <gmp.h>

using namespace std;

using found_set = unordered_set<size_t>;

bool fast_verify(size_t i, size_t max_tries, const found_set &found) {
    size_t tries = 0;
    size_t n = i;
    while(n != 1) {
        if(++tries == max_tries ) 
            return false;

        if(n < i)
            return found.empty() || found.find(i) == found.end();
        if(n % 2 == 0)
            n /= 2;
        else if(__builtin_mul_overflow (n, 3, &n) || __builtin_add_overflow(n, 1, &n))
            return false;
    }   

    return true;
}

Note the following:

1. The function only attempts to verify the conjecture for the number it receives. If it returns true, it has been verified. If it returns false, it just means it hasn't been verified (i.e., it does not mean it has been disproved).

2. It takes a parameter max_tries, and only verifies up to this number of steps. If the number has been exceeded, it does not try to discern whether this is part of an infinite loop or not - it just returns that verification failed.

3. It takes an unordered_set of known numbers that have failed (of course, if the Collatz conjecture is true, this set will always be empty).

4. It detects overflow via __builtin_*_overflow. (Unfortunately, this is gcc specific, then. A different platform might require a different set of such functions.)

Now for the slow-but-sure function. This function uses the GNU MP multi-precision arithmetic library. It checks for an infinite loop by maintaining the sequence of numbers it has already encountered. This function returns true if the conjecture has been proved for this number, and false if has been disproved for this number (note the difference from the previous fast verification).

bool slow_check(size_t i) {
    mpz_t n_; 
    mpz_init(n_);

    mpz_t rem_;
    mpz_init(rem_);

    mpz_t i_; 
    mpz_init(i_);

    mpz_set_ui(i_, i); 
    mpz_set_ui(n_, i); 

    list<mpz_t> seen;

    while(mpz_cmp_ui(n_, 1) != 0) {
        if(mpz_cmp_ui(n_, i) < 0)
            return true;
        mpz_mod_ui(rem_, n_, 2); 
        if(mpz_cmp_ui(rem_, 0) == 0) {
            mpz_div_ui(n_, n_, 2); 
        }   
        else {
            mpz_mul_ui(n_, n_, 3); 
            mpz_add_ui(n_, n_, 1); 
       }   
       seen.emplace_back(n_);
       for(const auto &e0: seen)
           for(const auto &e1: seen)
               if(&e0 != &e1 && mpz_cmp(e0, e1) == 0)
                   return false;
   }   

   return true;
}

Finally, main maintains an unordered_set of the disproven numbers. for each number, it optimistically tries to verify the conjecture, then, if it fails (for overflow or exceeding the number of iterations), uses the slow method:

int main()
{
    const auto max_num = 5000000000;
    found_set found;

    for(size_t i = 1; i <= max_num; i++) {
        if(i % 1000000000 == 0)
            cout << "iteration " << i << endl;

        auto const f = fast_verify(i, max_num, found);
        if(!f && !slow_check(i))
            found.insert(i);
    }

    for(auto e: found)
        cout << e << endl;
}

---

Running the full code (below) gives:

$ g++ -O3 --std=c++11 magic2.cpp -lgmp && time ./a.out
iteration 1000000000
iteration 2000000000
iteration 3000000000
iteration 4000000000
iteration 5000000000

real    1m3.933s
user    1m3.924s
sys 0m0.000s

$ uname -a
Linux atavory 4.4.0-38-generic #57-Ubuntu SMP Tue Sep 6 15:42:33 UTC 2016 x86_64 x86_64 x86_64 GNU/Linux
$ sudo lshw | grep -i cpu
      *-cpu
           description: CPU
           product: Intel(R) Core(TM) i7-4720HQ CPU @ 2.60GHz
           bus info: cpu@0
           version: Intel(R) Core(TM) i7-4720HQ CPU @ 2.60GHz
           capabilities: x86-64 fpu fpu_exception wp vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf eagerfpu pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm epb tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts cpufreq

I.e., no disproven numbers found, and the running time at ~64 seconds.

---

Full code:

#include <unordered_set>
#include <set>
#include <iostream>
#include <memory>
#include <list>
#include <gmp.h>

using namespace std;

using found_set = unordered_set<size_t>;

bool fast_verify(size_t i, size_t max_tries, const found_set &found) {
    size_t tries = 0;
    size_t n = i;
    while(n != 1) {
        if(++tries == max_tries )
            return false;

        if(n < i)
            return found.empty() || found.find(i) == found.end();
        if(n % 2 == 0)
            n /= 2;
        else if(__builtin_mul_overflow (n, 3, &n) || __builtin_add_overflow(n, 1, &n))
            return false;
    }   

    return true;
}

bool slow_check(size_t i) {
    mpz_t n_; 
    mpz_init(n_);

    mpz_t rem_;
    mpz_init(rem_);

    mpz_t i_; 
    mpz_init(i_);

    mpz_set_ui(i_, i); 
    mpz_set_ui(n_, i); 

    list<mpz_t> seen;

    while(mpz_cmp_ui(n_, 1) != 0) {
        if(mpz_cmp_ui(n_, i) < 0)
            return true;
        mpz_mod_ui(rem_, n_, 2); 
        if(mpz_cmp_ui(rem_, 0) == 0) {
            mpz_div_ui(n_, n_, 2); 
        }   
        else {
            mpz_mul_ui(n_, n_, 3); 
            mpz_add_ui(n_, n_, 1); 
       }   
       seen.emplace_back(n_);
       for(const auto &e0: seen)
           for(const auto &e1: seen)
               if(&e0 != &e1 && mpz_cmp(e0, e1) == 0)
                   return false;
   }   

   return true;
}


int main()
{
    const auto max_num = 5000000000;
    found_set found;

    for(size_t i = 1; i <= max_num; i++) {
        if(i % 1000000000 == 0)
            cout << "iteration " << i << endl;

        auto const f = fast_verify(i, max_num, found);
        if(!f && !slow_check(i))
            found.insert(i);
    }

    for(auto e: found)
        cout << e << endl;

    return 0;
}