Calculate 2 ^ 1000 without using BigInt

Question

As some of you may notice, this issue is issue 16 of the Euler Project . I decided to use the new "bigInt" function for C # 4.0, which was pretty simple, but which also does not learn all that I have to. I assume that since it is 2 ^ 1000, there will be some solutions for bit offsets, but I cannot figure out exactly how this will work.

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

Answer 1

Here is a pretty naive way to do this in python, just using a list (or array) of numbers

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 2

The most difficult part of this problem is not the calculation (just start at 1 and double it 1000 times), but showing the answer in decimal form. With this in mind, it might be easier for you to conceptually perform a calculation in some form of BCD representation, such as base-1000. Then do continuous multiplication by 2 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 3

You could hack BigInt yourself, potentially introduce bugs, and probably lead to a much slower solution. A typical implementation is to manually do the math yourself (based on numbers), with some high reason, for example, with numbers 2 ^ 16.

Answer 4

The problem is really converting 2 ^ 1000 to base 10. One simple way is to implement some kind of BCD (binary coded decimal place) of arbitrary length and calculate 2 ^ 1000 in BCD. An array of 250 bytes will be more than enough. Then you just need to write a method to execute * 2 by BCD number of arbitrary length and call it 1000 times). Then extracting and summing the numbers is easy.

It is very simple to implement even in languages ​​like 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

OK here goes:

 1 << 1000 

In a more serious note, you can store an integer 1<<x-1 in an x-bit. To actually calculate 1<<1000 , you will need a 1000-bit processor (technically 1001-bit, but which counts at this point). Since this is not feasible, your only choice is to imitate him (and what bigint does).

Answer 7

Actually nothing to calculate: 2^1000 = (1000...[994]...000)[Base2] . This is the "result".

If you want to know how to save it, your computer does not have the accuracy to store its exact value. So this is either BigInt or the double approximate value of Math.Pow(2, 1000) .

Edit: now I see that the comment simply requires a sum of numbers. See One Solution.

Answer 8

I will try to answer without giving away a lot of code ...

1) Use String to store the product

2) Perform a long multiplication (as 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 is here ... so if anyone finds errors, fix them.