20

最近我一直在经历一些简单的项目欧拉问题,并用 Ruby 和 C++ 解决它们。但是对于关于 Collat​​z 猜想的第14题,我的 C++ 代码运行了大约半小时,然后我终止了它,但是当我将代码翻译成 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++ 代码运行速度比 Ruby 代码快很多,直到达到 100,000。

4

3 回答 3

33

你溢出int了,所以它没有终止。在您的 c++ 代码中使用int64_t而不是。int你可能需要包括在内stdint.h..

于 2013-05-08T19:30:33.920 回答
3

在您的情况下,问题是 C++ 实现中的错误(数字溢出)。

但是请注意,在一些内存中进行交易,您可以获得比您正在做的更快的结果......

提示:假设您发现从数字 231 开始需要 127 步才能结束计算,并假设从另一个数字开始,经过 22 步后您会到达 231……您还需要执行多少步?

于 2013-05-08T21:05:44.287 回答
3

使用 32 位算术,C++ 代码在a = 3*a + 1. 使用带符号的 32 位算术,问题变得复杂,因为该a /= 2行将保留符号位。

这使得a永远等于 4 变得更加困难,实际上,当b达到 113383 时,a溢出并且循环永远不会结束。

使用 64 位算术没有溢出,因为a在 56991483520 时达到最大值,而在 704511 时b达到最大值。

不看数学,我推测无符号 32 位算术“可能”会起作用,因为乘法和无符号除法都将以 2^32 为模。鉴于程序的运行时间很短,值不会覆盖太多的 64 位频谱,所以如果一个值等于 4 模 2^32,它“可能”实际上等于 4。

于 2013-05-08T23:45:35.767 回答