Basic Algorithm Optimization

Question

My current assignment is to create a basic algorithm that finds the magic number (which is 1). The magic number can be found by either dividing an even number by 2 until it's magic, or multiplying an odd number by 3, adding 1, the dividing by 2 until 1. We must do this for each positive integer from 3 up until 5 billion.

MAGIC = 1;

DIV = 2;

START = 3;

MAX = 5000000000;

bool isOdd(int x);
void isMagic(int x);

int main () {

  clock_t startTime = clock();
  cout << "Beginning loop" << endl;

  for (int i = START; i < MAX; i++) 
  {

    if ( isOdd(i) == false ) 
      isMagic(i);
    else if ( isOdd(i) == true )
      isMagic(i);

   }

  clock_t finishTime = clock();
  cout << "Looping took " << double(finishTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;

  return 0;
}


bool isOdd(int x) {

  if( x % DIV == 0 )
    return false;
  else
    return true;

}

void isMagic(int x) {

  if( isOdd(x) == false ) //Is even
  {

    while( x > MAGIC )
    {
        x /= DIV;
    };

  }
  else if( isOdd(x) == true ) //Is odd
  {

    while( x > MAGIC )
    {

      x *= START;
      x += MAGIC;
      x /= DIV;

    };

  }

  return;
}

This works, however, it is rather slow. Even with the -o3 flag in my makefile it takes around 115 seconds to complete the task. My professor stated that a decent time would be ~60 seconds. How would I be able to optimize this?

Answer 1

I think you misunderstood the assignment. The "either dividing an even number by 2 until it's magic, or multiplying an odd number by 3 and adding 1" should be implemeneted as

while( x > 1 )
{
  if( isEven(x) )
  {
    x /= 2;
  }
  else
  {
    x *= 3;
    x += 1;
  }
}

Assuming the validity of Collatz conjecture, this can be further optimized as

x = 1;

Answer 2

Your function runs just once, so if it won't get magic number in one turn it will give you wrong result, also in this case:

 while( x > MAGIC )
{

  x *= START;
  x += MAGIC;
  x /= DIV;

};

when x is 3 or greater u get an infinite loop, and that's why it runs "slow" The correct code will be:

MAGIC = 1;

DIV = 2;

START = 3;

void isMagic(int x) {
   while (x != MAGIC){
         if(isOdd(x)){
               x *= START;
               x++;
         } else {
               x /= DIV;
         }
   }
}

Note that isOdd(x) returns boolean so there is no need in == true

Answer 3

Arguably the most important optimisation you want to implement is not solving the same problem over and over again while checking all numbers from 1 to 5 billion.

Example: when running isMagic(1742), you can run the loop for 179 or so iterations --- or recognize that you have already solved isMagic(871) and finish the check at the second iteration.

And when you solve isMagic(871), you shouldn't just record that you have solved 871, you should record all the numbers you encounter while solving it, which would be 2614 1307 3922 1961 5884 2942 1471 4414 2207 6622 3311 9934 4967 14902 7451 22354 11177 33532 16766 8383 25150 12575 37726 18863 56590 28295 84886 42443 127330 63665 190996 95498 47749 143248 71624 and so on --- that is, many numbers that are larger than the original 871. Finding a way to achieve that is the essence of your assignment.

As a side note, void isMagic(int x) is a rather odd function signature. Normally a name like isXYZ(...) suggests a predicate, that is, a function that returns a boolean. A void function with no side effects can be optimised down to void isMagic(int){}.