c++ - mas - php paiza io

¿Por qué este código Ruby es mucho más rápido que el código C++ equivalente?

Question

Recientemente he estado revisando algunos problemas de Euler de proyectos fáciles y resolviéndolos en Ruby y C ++. Pero para el Problema 14 relacionado con la conjetura de Collatz, mi código C ++ continuó durante aproximadamente media hora antes de que lo terminara, aunque cuando traduje el código a Ruby, lo resolvió en nueve segundos.

Esa diferencia es bastante increíble para mí: siempre me habían hecho creer que C ++ era casi siempre más rápido que Ruby, especialmente para el proceso matemático.

Mi código es el siguiente.

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

Tiempo de ejecución - Honestamente no lo sé, pero es un tiempo realmente REALMENTE largo.

y 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

Tiempo de ejecución - aproximadamente 9 segundos.

¿Alguna idea de lo que está pasando aquí?

PD: el código C ++ se ejecuta mucho más rápido que el código Ruby hasta que alcanza los 100.000.

Answer 1

Con aritmética de 32 bits, el código C ++ se desborda en a = 3*a + 1 . Con una aritmética de 32 bits firmada, el problema se complica, porque la línea a /= 2 conservará el bit de signo.

Esto hace que sea mucho más difícil que a sea igual a 4, y de hecho, cuando b alcanza 113383, a desborda y el bucle nunca termina.

Con la aritmética de 64 bits no hay desbordamiento, porque a maxes out en 56991483520, cuando b es 704511.

Sin mirar las matemáticas, especulo que la aritmética sin signo de 32 bits "probablemente" funcionará, porque la multiplicación y la división sin signo funcionarán en el módulo 2 ^ 32. Y dado el corto tiempo de ejecución del programa, los valores no cubrirán demasiado del espectro de 64 bits, por lo que si un valor es igual a 4 módulo 2 ^ 32, es "probablemente" realmente igual a 4.

Answer 2

En su caso, el problema fue un error en la implementación de C ++ (desbordamiento numérico).

Sin embargo, tenga en cuenta que al intercambiar memoria puede obtener el resultado mucho más rápido de lo que está haciendo ...

Sugerencia: suponga que encuentra que desde el número 231 necesita 127 pasos para finalizar el cálculo, y suponga que al comenzar con otro número que llega a 231 después de 22 pasos ... ¿cuántos pasos más necesita realizar?

Answer 3

Estás desbordando int , así que no está terminando. Use int64_t lugar de int en su código c ++. Probablemente deba incluir stdint.h para eso ..