Dlaczego ten kod Ruby jest znacznie szybszy niż odpowiadający mu kod C++?

Question

Niedawno przechodziłem przez kilka prostych problemów związanych z projektem Eulera i rozwiązywanie ich w Ruby i C++. Ale dla Problem 14 co do domysłów Collatza, mój kod C++ działał przez około pół godziny, zanim go zakończyłem, jednak kiedy przetłumaczyłem kod na Ruby, rozwiązał go w dziewięć sekund.

Ta różnica jest dla mnie niewiarygodna - zawsze przekonano mnie, że C++ jest prawie zawsze szybszy niż Ruby, szczególnie w przypadku procesów matematycznych.

Mój kod jest następujący.

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

czas Run - Szczerze mówiąc, nie wiem, ale to naprawdę bardzo długi czas.

Ruby: czas

#!/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 - około 9 sekund.

Masz pojęcie, co się tutaj dzieje?

P.S. kod C++ działa znacznie szybciej niż kod Ruby, dopóki nie osiągnie 100 000.

Answer 1

Przepełniłeś int, więc to się nie kończy. Użyj int64_t zamiast int w swoim kodzie C++. Prawdopodobnie będziesz musiał dołączyć stdint.h do tego ..

Answer 2

W twoim przypadku problem był błędem w implementacji C++ (przepełnienie numeryczne).

Uwaga jednak, że handel w pewnym pamięci można uzyskać wynik znacznie szybciej niż robisz ...

Podpowiedź: załóżmy, można zauważyć, że od numeru 231 trzeba 127 kroków w celu zakończenia obliczeń, i załóżmy że zaczynając od innego numeru, uzyskujesz 231 po 22 krokach ... ile jeszcze musisz zrobić kroków?

Answer 3

Z 32-bitową arytmetyką, kod C++ przepełnia się na a = 3*a + 1. W przypadku podpisanej 32-bitowej arytmetyki problem jest komplikowany, ponieważ linia a /= 2 zachowuje bit znaku.

To sprawia, że ​​znacznie trudniej a kiedykolwiek równy 4, a nawet gdy b osiągnie 113383, a przepełnienia i nigdy pętla kończy.

Z 64-bitowej arytmetyki nie ma przepełnienia, ponieważ a maxes się na 56991483520, gdy b jest 704511.

bez patrzenia na matematyce, I spekulują, że niepodpisane 32-bitowa arytmetyka będzie „prawdopodobnie” dzieło, ponieważ mnożenie i niepodpisany podział będą działać modulo 2^32. Biorąc pod uwagę krótki czas działania programu, wartości nie będą obejmować zbyt wiele spektrum 64-bitowego, więc jeśli wartość jest równa 4 modulo 2^32, to "prawdopodobnie" faktycznie równa się 4.