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

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 2

OK here goes:

1 << 1000

On a more serious note, the most you can hold in an x-bit integer is 1<<x-1. To actually calculate 1<<1000 you'd need a 1000-bit processor (technically 1001-bit, but who's counting at this point). Since that's not feasable, your only choice is to emulate it (and that's what bigint does).

Answer 3

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 4

There's nothing to calculate actually: 2^1000 = (1000...[994]...000)[Base2]. It's a 'result' already.

If you want to know how to store it, you machine doesn't have the precision to store its exact value. So it's either a BigInt, or the double approximate value Math.Pow(2, 1000).

Edit: I see now you from comments just want the sum of the digits. See one of the solutions.

Answer 5

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 6

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 7

I'll try and answer without giving away much code...

1) Use a String to hold the Product

2) Perform Long Multiplication (like you did in school)

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

print prod

Notepad-Coding here...so if anyone finds bugs please correct them.