Calculate to sum of 2^1000 without using BigInt

Question

As some of you may notice this question is problem 16 from Project Euler. I have solved it using the new "bigInt" feature of C# 4.0 which was fairly straightforward but which is also not really learning everything I should. I am assuming that since it is 2 ^ 1000 there would be some sort of bit shifting solutions but I can't figure out how exactly it would work.

Does anybody know a way to calculate 2^1000 without using bigint?

Answer 1

The hardest part of this problem is not the computation (just start with 1 and double it 1000 times), but displaying the answer in decimal. With this in mind, you might find it conceptually easier to perform the computation in some form of BCD representation, such as base-1000. Then perform long multiplication by 2 a thousand times. Here's a Python solution:

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

Here is a rather naive way to do it in python just using a list(or array) of digits

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

You could implmeent BigInt yourself, potentially introducing bugs and likely result in a much slower solution. A typical implementation is to manually perform the maths yourself (on a per digit basis), with some high base, such as base 2^16 numbers.

Answer 4

The problem is really conversion of 2^1000 to base 10. One easy way could be to implement some kind of BCD (Binary Coded Decimal) of arbitrary length and compute 2^1000 in BCD. An array of 250 bytes would be more than enough. Then you just have to write the method to perform *2 on a BCD number of arbitrary length and call it 1000 times). Then extracting and suming the digits is easy.

That's very easy to implement even in languages such as 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();

        }
    }
}