5
\$\begingroup\$

I'm trying to find maximum the Collatz sequence between 1 and 1000000. I wrote the following code below. I guess it is correct but it is extremely slow. Can you give me a few hints to make it faster?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool myfn(int i, int j) { return i<j; }

int collatz(int x);

int main()
{
    vector <int> myvector;
    for(int i = 1; i < 1000000; i++)
    {
        myvector.push_back(collatz(i));
    }

    cout<<*max_element(myvector.begin(),myvector.end(),myfn);


    return 0;

}

int collatz(int x)
{
    int counter = 1;


    while(1)
    {
        if(x == 1)
            break;

        if(x % 2 == 0)
        {
            x = x / 2;
            counter++;
        }
        else
        {
            x = 3 * x + 1;
            counter++;
        }
    }

    return counter;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Just a minor point: x = x / 2 can be shortened to x /= 2. \$\endgroup\$ – Jamal Jan 24 '14 at 2:47
7
\$\begingroup\$

Your program is non-portable, since an int is only guaranteed to hold numbers up to 32767. I would change your data type to unsigned long long; otherwise, collatz(159487) will overflow.


Your while condition is clumsy.

while(1)
{
    if(x == 1)
        break;
    …
}

should just be

while (x != 1)
{
    …
}

The key insight is that if you already know, for example, the value of collatz(37), then collatz(74) is just 1 + collatz(74 / 2), and you can reuse the previously computed result. Therefore, your collatz() function should have access to the results vector — either

  1. pass it in by reference, or
  2. make the vector an instance variable, and the function a method of the class.

It turns out that recursion works quite well for this problem: every chain will terminate in a few hundred steps, so your function call chains will be at most a few hundred frames deep. Using recursion allows you to cache the result for every number along the chain, which you can't do using iteration.

#include <iostream>
#include <limits>
#include <stdexcept>
#include <vector>

int collatz(unsigned long long n, std::vector<int> &results) {
    int c;
    if (n == 1) {
        return 1;
    } else if (n < results.size() && results[n]) {
        return results[n];
    } else if (n % 2 == 0) {
        c = 1 + collatz(n / 2, results);
    } else if (n >= (std::numeric_limits<unsigned long long>::max() - 1) / 3) {
        throw std::overflow_error("Overflow");
    } else {
        c = 1 + collatz(3 * n + 1, results);
    }
    if (n < results.size()) {
        results[n] = c;
    }
    return c;
}

int main() {
    const unsigned long long N = 1000000ULL;
    std::vector<int> results(N);
    int max = 0, max_i;
    for (unsigned long long i = 1; i < N; ++i) {
        results[i] = collatz(i, results);
        // std::cout << "collatz(" << i << ") = " << results[i] << std::endl;
        if (max < results[i]) {
            max = results[i];
            max_i = i;
        }
    }
    std::cout << "Max: " << max_i << " with " << max << " steps" << std::endl;
    return 0;
}

By packaging your code into a class, you can let main() not worry about some of the details:

template <typename T>
class Collatz {
  public:
    Collatz(T limit) : limit(limit), results(limit) {}

    int operator[](T n) {
        int c;
        if (n == 1) {
            return 1;
        } else if (n < results.size() && results[n]) {
            return results[n];
        } else if (n % 2 == 0) {
            c = 1 + (*this)[n / 2];
        } else if (n >= (std::numeric_limits<T>::max() - 1) / 3) {
            throw std::overflow_error("Overflow");
        } else {
            c = 1 + (*this)[3 * n + 1];
        }
        if (n < results.size()) {
            results[n] = c;
        }
        return c;
    }

    const T limit;

  private:
    std::vector<int> results;
};    

int main() {
    Collatz<unsigned long long> collatz(1000000ULL);
    int max = 0, max_i;
    for (unsigned long long i = 1; i < collatz.limit; ++i) {
        // std::cout << "collatz(" << i << ") = " << collatz[i] << std::endl;
        if (max < collatz[i]) {
            max = collatz[i];
            max_i = i;
        }
    }
    std::cout << "Max: " << max_i << " with " << max << " steps" << std::endl;
    return 0;
}
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ make the vector an instance variable, and the function a method of the class. Can you make this a little bit more clear? I couldn't understand. Thanks for such a helpful answer by the way. \$\endgroup\$ – jason Jan 23 '14 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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