20

最近、いくつかの簡単なプロジェクト オイラー問題に取り組み、Ruby と C++ でそれらを解決しています。しかし、コラッツ予想に関する問題 14については、私の C++ コードは終了するまで約 30 分かかりましたが、コードを Ruby に変換すると、9 秒で解決しました。

その違いは私にはまったく信じがたいものです。特に数学的処理では、C++ はほとんど常に Ruby よりも高速であると信じ込まされていました。

私のコードは次のとおりです。

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

実行時間 - 正直わかりませんが、本当に長い時間です。

とルビー:

#!/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 秒。

ここで何が起こっているのか分かりますか？

PS C++ コードは、100,000 に達するまで、Ruby コードよりもかなり高速に実行されます。

4

3 に答える 3

33

あなたはオーバーフローintしているので、終了していません。C++ コードint64_tの代わりに使用します。intおそらくそのために含める必要がありますstdint.h..

于 2013-05-08T19:30:33.920 に答える
3

32 ビット演算では、C++ コードは でオーバーフローしa = 3*a + 1ます。符号付き 32 ビット演算では、a /= 2行が符号ビットを保持するため、問題はさらに複雑になります。

aこれにより、 が 4 に等しくなることがはるかに難しくなり、実際bに 113383 に達すると、aオーバーフローが発生し、ループが終了しなくなります。

64 ビットの算術演算では、a704511 のときに 56991483520 で最大になるため、オーバーフローはありませんb。

数学を見ずに、乗算と符号なし除算の両方がモジュロ 2^32 で機能するため、符号なし 32 ビット演算は「おそらく」機能すると推測します。また、プログラムの実行時間が短いため、値は 64 ビット スペクトルをあまりカバーしないため、値が 2^32 を法とする 4 に等しい場合、それは「おそらく」実際には 4 に等しくなります。

于 2013-05-08T23:45:35.767 に答える