2

我在 Project Euler 上工作，以提高我的 C++ 编码技能，为下学期我们将面临的编程挑战做准备（因为他们不让我们使用 Python，嘘！）。

我在#16，我正在尝试找到一种方法来保持 2¹°°° 的真实精度

例如：

int main(){
    double num = pow(2, 1000);
    printf("%.0f", num):
    return 0;
}

印刷

10715086071862673209484250490600018105614050000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

缺少大部分数字（来自python）：

>>> 2**1000

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376L

当然，我可以使用 Python 1 衬垫编写程序

sum(int(_) for _ in str(2**1000))

这立即给了我结果，但我正试图找到一种在 C++ 中实现它的方法。任何指针？（哈哈...）

编辑：

标准库之外的东西对我来说毫无价值——在这些比赛中只允许使用死树代码，而且我可能不会打印出 10,000 行外部代码......

4

7 回答 7

8

如果您只跟踪 char 数组中的每个数字，这很容易。加倍一个数字是微不足道的，如果结果大于 10，你只需减去 10 并在下一个数字上加一个进位。从值 1 开始，循环加倍函数 1000 次，就完成了。您可以使用 预测您需要的位数ceil(1000*log(2)/log(10))，或者只是动态添加它们。

剧透警告：看来我必须在任何人相信我之前显示代码。这是一个 bignum 的简单实现，有两个函数，Double 和 Display。为了简单起见，我没有把它作为一个类。数字以小端格式存储，最低有效位在前。




typedef std::vector<char> bignum;

void Double(bignum & num)
{
    int carry = 0;
    for (bignum::iterator p = num.begin();  p != num.end();  ++p)
    {
        *p *= 2;
        *p += carry;
        carry = (*p >= 10);
        *p -= carry * 10;
    }
    if (carry != 0)
        num.push_back(carry);
}

void Display(bignum & num)
{
    for (bignum::reverse_iterator p = num.rbegin();  p != num.rend();  ++p)
        std::cout << static_cast<int>(*p);
}

int main(int argc, char* argv[])
{
    bignum num;
    num.push_back(1);
    for (int i = 0;  i < 1000;  ++i)
        Double(num);
    Display(num);
    std::cout << std::endl;
    return 0;
}
于 2010-08-02T16:22:51.300 回答
3

你需要一个 bignum 库，比如这个。

于 2010-08-02T15:31:08.190 回答
3

您可能在这里需要一个指针（双关语）

在 C++ 中，您需要创建自己的 bigint 库才能执行与 python 中相同的操作。

于 2010-08-02T15:31:27.527 回答
2

C/C++ operates on fundamental data types. You are using a double which has only 64 bits to store a 1000 bit number. double uses 51 bit for the significant digits and 11 bit for the magnitude.

The only solution for you is to either use a library like bignum mentioned elsewhere or to roll out your own.

于 2010-08-02T15:37:03.093 回答
2

更新：我刚刚浏览到欧拉问题网站，发现问题 13 是关于对大整数求和。迭代的方法会在短时间内变得非常棘手，所以我建议使用问题 #13 中的代码，你应该已经解决了这个问题，因为2**N => 2**(N-1) + 2**(N-1)

使用 bignums 是作弊，而不是解决方案。此外，您不需要计算 2**1000 或类似的东西来获得结果。我给你一个提示：

取 2**N 的前几个值：

0 1 2 4 8 16 32 64 128 256 ...

现在为每个数字写下其数字的总和：

1 2 4 8 7 5 10 11 13 ...

您应该注意到 (x~=y表示 x 和 y 具有相同的数字总和)

1+1=2, 1+(1+2)=4, 1+(1+2+4)=8, 1+(1+2+4+8)=16~=7 1+(1+2+4+8+7)=23~=5

现在写一个循环。

欧拉计划 = 计算前思考！

于 2010-08-02T16:07:38.250 回答
1

If you want to do this sort of thing on a practical basis, you're looking for an arbitrary precision arithmetic package. There are a number around, including NTL, lip, GMP, and MIRACL.

If you're just after something for Project Euler, you can write your own code for raising to a power. The basic idea is to store your large number in quite a few small pieces, and implement your own carries, borrows, etc., between the pieces.

于 2010-08-02T15:33:24.803 回答
0

本质上不pow(2, 1000)只是 2 左移 1000 次吗？它应该在双浮点中具有精确的二进制表示。它不应该需要一个 bignum 库。

于 2010-08-02T15:38:32.767 回答