Why is this Ruby code far faster than the equivalent C++ code?

Question

Recently I've been going through some easy project Euler problems and solving them in Ruby and C++. But for Problem 14 concerning the Collatz conjecture, my C++ code went on for about half an hour before I terminated it, though when I translated the code into Ruby, it solved it in nine seconds.

That difference is quite unbelievable to me - I had always been led to believe that C++ was almost always faster than Ruby, especially for mathematical process.

My code is as follows.

C++:

#include <iostream>

using namespace std;

int main ()
{
    int a = 2;
    int b = 2;
    int c = 0;
    while (b < 1000000)
    {

        a = b;
        int d = 2;
        while (a != 4)
        {
            if (a % 2 == 0)
                a /= 2;
            else
                a = 3*a + 1;
            d++;
        }
        if (d > c)
        {
            cout << b << ' ' << d << endl;
            c=d;
        }
        b++;
    }
    cout << c;
    return 0;
}

Run time - I honestly don't know, but it's a really REALLY long time.

and Ruby:

#!/usr/bin/ruby -w

    a = 0
    b = 2
    c = 0
    while b < 1000000
        a = b;
        d = 2
        while a != 4
            if a % 2 == 0
                a /= 2
            else
                 a = 3*a + 1
            end
            d+=1
        end
        if d > c
            p b,d
            c=d
        end
        b+=1
    end
    p c

Run time - approximately 9 seconds.

Any idea what's going on here?

P.S. the C++ code runs a good deal faster than the Ruby code until it hits 100,000.

Answer 1

You're overflowing int, so it's not terminating. Use int64_t instead of int in your c++ code. You'll probably need to include stdint.h for that..

Answer 2

In your case the problem was a bug in C++ implementation (numeric overflow).

Note however that trading in some memory you can get the result much faster than you're doing...

Hint: suppose you find that from number 231 you need 127 steps to end the computation, and suppose that starting from another number you get to 231 after 22 steps... how many more steps do you need to do?