不使用 BigInt 计算 2^1000 之和

Question

你们中的一些人可能会注意到这个问题是来自 问题 16 href="http://projecteuler.net/" rel="nofollow noreferrer">欧拉项目。我已经使用 C# 4.0 的新“bigInt”功能解决了这个问题，该功能相当简单，但也没有真正学习我应该学习的所有内容。我假设因为它是 2 ^ 1000 ，所以会有某种位移解决方案，但我无法弄清楚它到底是如何工作的。

有谁知道不使用bigint计算2^1000的方法吗？

Answer 1

这个问题最难的部分不是计算（只是从 1 开始，然后加倍 1000 次），而是以十进制显示答案。考虑到这一点，您可能会发现在概念上更容易以某种形式的 BCD 表示形式（例如 base-1000）执行计算。然后执行 2 的长乘法一千次。这是一个Python解决方案：

def mul2(n):
    result = []
    carry = 0
    for i in n:
        i = i * 2 + carry
        carry = 0 if i < 1000 else 1
        result.append(i % 1000)
    if carry: result.append(1)
    return result

n = [1]
for _ in range(1000):
    n = mul2(n)

print ''.join('{0:03}'.format(i) for i in reversed(n)).lstrip('0')

Answer 2

这是在 python 中使用数字列表（或数组）来完成此操作的一种相当幼稚的方法

digits = [1]
for n in range(1000):
    newdigits = []
    carry = 0
    for digit in digits:
        s = 2*digit+carry
        carry = s/10
        s = s%10
        newdigits.append(s)
    if carry:
        newdigits.append(carry)
    digits = newdigits
print "".join(map(str,reversed(digits)))

Answer 3

您可以自己实现 BigInt，这可能会引入错误，并可能导致解决方案速度慢得多。典型的实现是自己手动执行数学运算（以每个数字为基础），使用一些高基数，例如基数 2^16 数字。

Answer 4

问题实际上是 2^1000 到基数 10 的转换。一种简单的方法是实现某种任意长度的 BCD（二进制编码十进制）并计算 BCD 中的 2^1000。 250 字节的数组就足够了。然后你只需编写对任意长度的 BCD 数执行 *2 的方法并调用它 1000 次）。然后提取和求和数字就很容易了。

即使使用 C 等语言也很容易实现。

Answer 5

class Program
{
    static void Main(string[] args)
    {
        double sum=0;
        for (int i = 1000; i <=1000; i++)
        {
            double pow = Math.Pow(2, i);
            string power = pow.ToString();
            for (int j = 0; j < power.Length; j++)
            {
                 sum = sum+pow % 10;
                 StringBuilder t = new StringBuilder(pow.ToString());
                 int len = t.Length;
                 if (len != 1)
                 {
                     t.Remove(len - 1, 1);
                 }
                 pow = Convert.ToDouble(t.ToString());
            }
             Console.WriteLine(sum);
                Console.WriteLine();

        }
    }
}

Answer 6

好吧，

1 << 1000

更严肃地说，x 位整数最多可以容纳 1<。要实际计算 1<<1000，您需要一个 1000 位处理器（技术上是 1001 位，但现在谁在数）。由于这是不可行的，您唯一的选择就是模拟它（这就是 bigint 所做的）。

Answer 7

实际上没有什么可计算的：2^1000 = (1000...[994]...000)[Base2]。已经是‘结果’了。

如果您想知道如何存储它，您的机器不具备存储其确切值的精度。因此它要么是 BigInt，要么是双精度近似值 Math.Pow(2, 1000)。

编辑：我现在看到您从评论中只想要数字之和。请参阅解决方案之一。

Answer 8

我将尝试在不给出太多代码的情况下回答...

1）使用字符串来保存乘积

2）执行长乘法（就像您在学校所做的那样）

Prod = "1"
for n = 1 to 1000
        carry = 0
        newprod = ""
        for i = strlen(prod) - 1 to 0 step - 1
                digit = int(prod[i])
                p = digit * 2 + carry
                newprod = (p % 10) & newprod // append
                carry = p / 10
        next
        if( carry > 0) newprod = carry & newprod
        prod = newprod
next

在这里打印产品

记事本编码...所以如果有人发现错误，请纠正它们。