Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite

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
    return total;
}

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;
}
share|improve this question

3 Answers

up vote 0 down vote accepted

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;
}
share|improve this answer
up vote 2 down vote

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)

share|improve this answer
I would vote up If I had enough rep points – user1949723 Jan 16 at 17:12
up vote 1 down vote

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);
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.