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 回答