C++ 中的双精度（或战俘（2, 1000））

Question

我正在参加 Project Euler，以温习我的 C++ 编码技能，为我们下学期将面临的编程挑战做好准备（因为他们不让我们使用 Python，嘘！）。

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

例如：

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

打印

1071508607186267320948425049060001810561405000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000

Which is missing most of the numbers (from python):

>>> 2**1000

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468 2518714528569231404359845775746985748039345677748242309854210746050623711418779541821530464749835819412673987675591655439 46077062914571196477686542167660429831652624386837205668069376L

Granted, I can write the program with a Python 1 liner

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

that gives me the result immediately, but I'm trying to find a way to do it in C++.有什么指点吗？ （哈哈...）

编辑：

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

Answer 1

如果您只跟踪字符数组中的每个数字，这很容易。将一位数字加倍是微不足道的，如果结果大于 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;
}

Answer 2

您需要一个 bignum 库，例如这个。

Answer 3

您可能需要一个指针（双关语）。

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

Answer 4

C/C++ 对基本数据类型进行操作。您正在使用只有 64 位的 double 来存储 1000 位数字。 double 使用 51 位作为有效数字，使用 11 位作为幅度。

唯一的解决方案是使用其他地方提到的 bignum 之类的库，或者推出自己的库。

Answer 5

更新：我刚刚浏览了欧拉问题网站，发现问题 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

现在编写一个循环。

欧拉计划 = 先思考再计算！

Answer 6

如果你想在实际的基础上做这类事情，你正在寻找一个任意精度的算术包。周围有很多，包括 NTL、lip，GMP 和 MIRACL。

如果您只是想为欧拉计划做点什么，您可以编写自己的代码来求幂。基本思想是将您的大数字存储在相当多的小块中，并在小块之间实现您自己的进位、借用等。

Answer 7

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