Почему этот код Ruby намного быстрее, чем эквивалентный код на С++?

Недавно я проходил несколько простых проблем Эйлера проекта и решая их в Ruby и С++. Но для Проблема 14 относительно гипотезы Collatz мой код на С++ продолжался около получаса, прежде чем я его прекратил, хотя когда я перевел код в Руби, он решил это через девять секунд.

Эта разница для меня совершенно невероятна - мне всегда верили, что С++ почти всегда быстрее Ruby, особенно для математического процесса.

Мой код выглядит следующим образом.

С++:

#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;
}

Время работы - я честно не знаю, но это действительно ДЕЙСТВИТЕЛЬНО долгое время.

и 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

Время работы - примерно 9 секунд.

Любая идея, что здесь происходит?

P.S. код С++ работает намного быстрее, чем код Ruby, пока он не достигнет 100 000.

Ответы

Ответ 1

Вы переполнены int, поэтому он не заканчивается. Используйте int64_t вместо int в вашем коде на С++. Вероятно, вам нужно включить stdint.h для этого.

Ответ 2

В вашем случае проблема была ошибкой в ​​реализации С++ (числовое переполнение).

Обратите внимание, что при торговле некоторой памятью вы можете получить результат намного быстрее, чем вы делаете...

Подсказка: предположим, что вы обнаружите, что из числа 231 вам нужно 127 шагов для завершения вычисления, и предположим, что начиная с другого номера вы получите 231 после 22 шагов... сколько еще шагов вам нужно сделать?

Ответ 3

С 32-разрядной арифметикой код С++ переполняется на a = 3*a + 1. С подписанной 32-разрядной арифметикой проблема усугубляется, потому что строка a /= 2 сохранит бит знака.

Это делает намного сложнее для a когда-либо равным 4, и действительно, когда b достигает 113383, a переполняется, и цикл никогда не заканчивается.

С 64-разрядной арифметикой переполнения нет, потому что a maxes out на 56991483520, когда b равен 704511.

Не глядя на математику, я предполагаю, что 32-разрядная арифметика без знака будет "вероятно" работать, потому что умножение и беззнаковое деление будут работать по модулю 2 ^ 32. И учитывая короткое время работы программы, значения не будут охватывать слишком много из 64-битного спектра, поэтому, если значение равно 4 по модулю 2 ^ 32, оно "вероятно" фактически равно 4.