不使用BigInt计算为2^1000的总和

有些人可能会注意到这个问题是problem 16从Project Euler。我已经使用C＃4.0的新“bigInt”功能解决了这个问题，这个功能相当简单，但它并没有真正学习我应该做的所有事情。我假设，因为它是2^1000会有某种位移的解决方案，但我无法弄清楚它的工作原理。不使用BigInt计算为2^1000的总和

有没有人知道一种方法来计算2^1000而不使用bigint？

来源

2010-07-13 Chris G

如果不使用bigint，你打算如何表示答案？ – 2010-07-13 10:41:59

你是指这个问题：http://projecteuler.net/index.php?section=problems&id=16？ – 2010-07-13 10:42:29

@ 0xA3是的数字16 – 2010-07-13 10:44:58

这里是数字

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)))

来源

2010-07-13 10:54:25

对于欧拉工程来说这是一个扰流板，你不应该准备好使用代码。 – kriss 2010-07-13 11:01:15

不，我不同意......我认为这个答案仍然符合'只是蛮力它'的方法。 – Arafangion 2010-07-13 11:02:20

@ kriss，以及我没有错过总结数字的关键步骤; o）。认真地说，如果人们要在这样的问题上作弊，他们将错过项目欧盟的所有乐趣 – 2010-07-13 11:05:38

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

来源

2010-07-13 10:40:55 Arafangion

OK云：

1 << 1000

在一个更严重的是，你最能装在X位的整数1<<x-1。要实际计算1<<1000，你需要一个1000位处理器（技术上是1001位，但是这个数字在计算）。既然这不可行，你唯一的选择就是模仿它（这就是bigint所做的）。

来源

2010-07-13 10:45:12 Blindy

我不这么认为，或者他不会问没有某种形式的计算。编辑：这是回答从马塞洛坎托斯删除的评论。 – Blindy 2010-07-13 10:47:20

软件实现...硬件实现...没有模拟正在进行，只是纯粹的数学。 – Arafangion 2010-07-13 10:48:07

一个相当简单的方式做在python只使用一个列表（或阵列）没有什么实际计算：2^1000 = (1000...[994]...000)[Base2]。这已经是'结果'了。

如果你想知道如何存储它，你的机器没有精确度来存储它的确切值。所以它可以是BigInt或双近似值Math.Pow(2, 1000)。

编辑：我现在看到你来自评论只是想要的数字的总和。查看其中一个解决方案。

来源

2010-07-13 10:57:05 Mau

这个问题中最难的部分不是计算（只需从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')

来源

2010-07-13 10:59:56

只是输入了和你一样的答案，但没有扰流板;-)，无论如何，我确定无论如何都能够让你满意。 – kriss 2010-07-13 11:03:17

糟糕。当我读到问题时，ProjectEuler参考没有注册。 – 2010-07-13 11:47:37

问题是真正的2^1000转化基地10.一个简单的方法可以实现某种BCD的任意长度的（二进制编码的十进制），并计算2^1000 BCD。一个250字节的数组就足够了。然后你只需要编写方法来对任意长度的BCD数字执行* 2并将其调用1000次）。然后提取和总结数字很容易。

这是即使在语言很容易实现，如C.

来源

2010-07-13 11:01:21 kriss

我会试着不放弃太多的代码回答...

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

打印督促

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

来源

2010-07-13 11:03:55 st0le

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(); 

     } 
    } 
}

来源

2012-07-26 12:11:00 Ram

不使用BigInt计算为2^1000的总和

回答

相关问题