なぜこのRubyコードは、同等のC++コードよりもはるかに高速ですか？

Question

最近、私はいくつかの簡単なプロジェクトのオイラー問題を解決し、RubyとC++でそれらを解決してきました。しかし、Collat​​zの推測に関するProblem 14については、コードをRubyに翻訳して9秒で解決しましたが、C++コードは終了する前に約30分間続きました。

その違いは私には信じられないほどです - 私はいつも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; 
} 

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

と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. C++コードはRubyコードよりも速く実行され、100,000に達するまで続きます。

Answer 1

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

Answer 2

問題は、C++実装（数値オーバーフロー）のバグでした。

注意は、しかし、あなたがやっているよりもはるかに高速に結果を得ることができ、いくつかのメモリ内のその取引...

ヒント：あなたは数231から、あなたが計算を終了する127の手順が必要であることを見つけると仮定し、仮定します別の番号から始まって、22ステップ後に231に達すると...何ステップ以上のステップが必要ですか？

Answer 3

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

これは、aが4に等しくなることをはるかに困難にし、実際にbが113383に達すると、aがオーバーフローし、ループは終了しません。 64ビット演算で

aが56991483520で実施maxesため、オーバーフローが存在しないbは数学を見ず704511.

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