253

7
+6  Q:

## Calculate to sum of 2^1000 without using BigInt

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?

+1  A:

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.

A:

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

I don't think so, or he wouldn't ask about calculating it without some sort of bigint. EDIT: that's to answer a deleted comment from Marcelo Cantos.
Software implementation... Hardware implementation... No emulation going on, just pure maths.
+2  A:

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)))
``````
it's a spoiler for Project Euler, you shouldn't Post ready to use code.
Nah, I disagree... I think this answer still qualifies for the 'just brute-force it' approach.
@kriss, well i did miss the critical step of summing the digits ;o). Seriously if people are going to cheat on problems like this, they are going to miss out on all of the fun of project euler
You can always find the code if you look around, you have to WANT to solve the problems yourself
OK, for low numbered problem, the code is allready around anyway.
A:

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.

+3  A:

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')
``````
Was just typing the same answer as you did, but without the spoiler ;-), OK I upvote you anyway.
Oops. The ProjectEuler reference didn't register when I read the question.
+1  A:

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.

A:

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