# Tips on projecteuler code optimization

I am working on projecteuler # 14, http://projecteuler.net/problem=14 and my code takes too long to run. Any tips, or hints for a beginner?

Code:

////////////////////////
/// ProjectEuler # 14///
////////////////////////

#include <iostream>
#include <tuple>           //New, shaky on tuple
using namespace std;

bool tester(int n)      //Even number tester//It works 100%
{
bool result = false;
if (n%2 == 0) result = true;
return result;
}

int collatz_counter (int collatz_number)    //Collatz sequence counter//It works 100%
{
int j = collatz_number;
int total = 0;
do
{
if (tester(j))
{
j /=2;
total ++;
}
else
{
j = 3*j +1;
total ++;
}
}while (j!=1);
total +=1;          // To account for the original number itself
}

pair <int n, int m> value_finder (int n)
{
int max = 0;
int max_number = 0;
for (int i = n; i>1; i--)
{
if(collatz_counter(i) > max)
{
max_number = i;
max = collatz_counter(i);
}
}
max_number++;
return{max, max_number};
}

int main (void)
{
int starter;
int x;
cout<<"Enter value :"<<endl;
cin>>starter;
cout<<endl;
int Max = 0;
int Max_Number = 0;
for (x = starter; x>= starter/2 ; x--)
{
int m, n;
tie(m, n) = value_finder(x);
if ( m> Max)
{
Max_Number = n;
Max = m;
}
}

cout<<" The maximum numbers in the collatz sequence is "<<m<<endl;
cout<<" The starting number of the collatz sequence is "<<n<<endl;
system ("pause");
return 0;
}

-

You need to cache already computed values. That's all:

#include <stdio.h>

#define sz 1000000
#define UL unsigned long

UL tb[sz+1];

UL calc(UL n){
if(n < sz){
if(tb[n]) return tb[n];
if(n & 1) return tb[n] = 1 + calc( n + (n << 1) + 1);
return tb[n] = 1 + calc( n >> 1);
}
if(n & 1) return 1 + calc( n + (n << 1) + 1);
return 1 + calc( n >> 1);
}

int main(){
UL max,a,b,i;
max = 0;
tb[1] = 1;
max = 0;
for( i = 1; i <= sz; i++)
if( max < calc(i)) max = tb[i];
printf("%lu\n",max);
return 0;
}

-

Hint

Taking the example from the Project Euler page, if you have computed the Collatz number for 5 in the past and you know it's 6, then when computing Collatz number for 10, you probably don't need to go through the whole chain. You can stop when you reach 5.

It might be interesting to cache the computed value to be able to reuse them.

(Disclaimer : I solved this problem a long time ago and cannot really remember how I did it)

-
I would vote up If I had enough rep points –  user1949723 Jan 16 '13 at 17:12

The other answers have dealt with the important stuff regarding optimisation, I just want to make a couple of more general comments on your code. Firstly, please give your functions more meaningful names: i.e. prefer isEven to tester; secondly, your tester function is needlessly verbose, instead of

bool tester(int n)      //Even number tester//It works 100%
{
bool result = false;
if (n%2 == 0) result = true;
return result;
}


where you're checking a boolean and then assigning a boolean value based on the value of the boolean, you can simply do this:

bool isEven(int n)
{
return (n%2 == 0);
}


it's cleaner, more compact and less error prone. Depending on your compiler, it may even be faster although most modern compilers are smart enough to figure it out when you've got optimisation turned on. As an even more minor point, I'd personally explicitly inline this kind of function and a faster check for the evenness of an integer is to check if the least significant bit is set:

inline bool isEven(int n)
{
return !(n & 1);
}

-