20

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.

9
  • 8
    Change that endl to "\n", since it performs a flush of the stream and unbuffered IO is really slow. May 8, 2013 at 19:27
  • How do you compile the C++?
    – selalerer
    May 8, 2013 at 19:28
  • will do, but when it gets to higher numbers it can be as much as a few minutes between prints and the difference of endl and "\n" becomes negligable May 8, 2013 at 19:29
  • 1
    I like this question because the assumption was way out there. Shows much about assumptions! May 8, 2013 at 20:37
  • 2
    This code is not equivalent and you don't even post your compiler settings.
    – Ed S.
    May 8, 2013 at 21:02

3 Answers 3

33

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

10
  • as far as i can tell that makes no noticeable difference May 8, 2013 at 19:33
  • 4
    Improve your answer, explaining why he is overflowing int.
    – fotanus
    May 8, 2013 at 19:34
  • 2
    buuuut, it looks like unsigned long did the trick, and in .539 seconds. i guess i should do more study on datatypes. May 8, 2013 at 19:35
  • 7
    Specifically, while (a != 4) will never complete when a is large enough to overflow the math in that loop. May 8, 2013 at 19:37
  • 3
    More specifically the loop when b=901118 seems to take a to the limits.
    – stardust
    May 8, 2013 at 19:41
3

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?

4
  • yeah, i thought about saving values into an array when d > 100 but then i thought, do i really want to check against a large array for every iteration of every number number under one million? I suppose that if i kept everything sorted and used a binary search and only checked once 'a' falls below a threshhold (probably 'b') it would make it run faster, but when it solves in half a second that just doesn't appeal to me, although i would do so if this were part of a larger program and was called often May 8, 2013 at 21:22
  • What about storing the count for b into count[b]? No need to "search" ;-)
    – 6502
    May 8, 2013 at 21:41
  • Is integer overflow really a bug in C++ implementation? Isn't it undefined behaviour?
    – Alvin Wong
    May 9, 2013 at 0:46
  • @AlvinWong: It is a bug in the implementation of the algorithm. The bug is not considering integer overflow would happen with those numbers. When writing in C or C++ you simply are not expected to do integer overflow, if you do then your code is buggy.
    – 6502
    May 9, 2013 at 6:09
3

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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