CODEWITHSUNDEEP
c++math
elder south
elder south

Reputation: 463

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

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.

Upvotes: 20

Views: 1111

Answers (3)

mwfearnley
mwfearnley

Reputation: 3669

With 32-bit arithmetic, the C++ code overflows on a = 3*a + 1. With signed 32-bit arithmetic, the problem is compounded, because the a /= 2 line will preserve the sign bit.

This makes it much harder for a to ever equal 4, and indeed when b reaches 113383, a overflows and the loop never ends.

With 64-bit arithmetic there is no overflow, because a maxes out at 56991483520, when b is 704511.

Without looking at the math, I speculate that unsigned 32-bit arithmetic will "probably" work, because the multiplication and unsigned division will both work modulo 2^32. And given the short running time of the program, values aren't going to cover too much of the 64-bit spectrum, so if a value is equal to 4 modulo 2^32, it's "probably" actually equal to 4.

Upvotes: 3

6502
6502

Reputation: 114579

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?

Upvotes: 3

hexist
hexist

Reputation: 5250

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..

Upvotes: 33

Related Questions