2
$\begingroup$

I found this question on a Chinese programmer forum. They solved it by brute-force method like 2 ** 10000[99] in python. The solution is 9. I’m wondering if we can solve it in a better way? Do we have to calculate $2^{10000}$ first?

I don’t even know what tags I should put. Any suggestions or modifications would be appreciated.

$\endgroup$
4
  • $\begingroup$ Yeah, thank you for pointing out. It should be $2^{10000}$ $\endgroup$ – user8314628 Apr 18 '20 at 7:03
  • 1
    $\begingroup$ A 'better' way would be a lot trickier—brute force seems like the simplest answer to this question, and knowing programmers, they'd probably leave it at that. Your question should be 'another way' or 'a way that uses less processing power.' $\endgroup$ – Lt. Commander. Data Apr 18 '20 at 7:11
  • $\begingroup$ It is not clear which $100^{th}$ digit you are referring to? Is it the one counting from the left or counting from the right? By brute force, it seems you are referring to the $100^{th}$ most significant digit (i.e. digit counting from the left). $$2^{10000} = {\small\begin{align} & 19950631168807583848837421626835850838234968318861\\ & 9245485200894985294388302219466319199616840361945\color{red}{9}\\ & 7899...\end{align}} $$ $\endgroup$ – achille hui Apr 18 '20 at 7:48
  • $\begingroup$ If that is the case, in principle, you can compute $\log_{10} 2$ accurate up to $100 + $ decimals, multiply by $10000$, take the fractional part, raise $10$ to that power and look at the $99^{th}$ decimal place of the result. However, it is not clear whether this will be simpler than compute the $2^{10000}$ directly. $\endgroup$ – achille hui Apr 18 '20 at 7:50
2
$\begingroup$

There is no need to compute $2^{10000}$ in full. You can perform all multiplies keeping only the $m$ most significant digits. If you implement truncated multiplication, you obtain the result after $13$ squarings and $4$ multiplies.

$m$ must be a little larger than $100$ to shield against truncation errors. Unfortunately, I am unable to compute the minimum $m$ required.

Taking $m=110$, I obtained the number

$$\begin{align}&1995063116\ 8807583848\ 8374216268\ 3585083823\ 4968318861\\&9245485200\ 8949852943\ 8830221946\ 6319199616\ 840361945\color{red}9\\&7899331113\end{align}$$

$\endgroup$
1
$\begingroup$

In my opinion the only optimization would be to calcultate $2^{10000}$ in a smarter way:

$$2^{10000}=2^{8192}\times2^{1024}\times2^{512}\times2^{256}\times2^{16}$$

In python:

p16=2**16
p256=p16**16
p512=p256**2
p1024=p512**2
p8192=p1024**8
res=p8192*p1024*p512*p256*p16
print(str(res)[99])

Bigger exponents are evaluaed by using already calculated values of the smaller exponents.

The code prints 9.

$\endgroup$
5
  • $\begingroup$ Doesn't the Python exponentiation function have this built-in ? $\endgroup$ – Yves Daoust Apr 18 '20 at 8:28
  • $\begingroup$ @YvesDaoust Honestly, I don't know. Python source is not the easiest reading. $\endgroup$ – Oldboy Apr 18 '20 at 10:35
  • $\begingroup$ Powers by successive squarings is old as the World. $\endgroup$ – Yves Daoust Apr 18 '20 at 13:48
  • $\begingroup$ @YvesDaoust Multi-threading is also as old as world but Python does not support it. $\endgroup$ – Oldboy Apr 19 '20 at 9:34
  • $\begingroup$ Guys who develop arbitrary precision arithmetic know what they are doing. Computing powers by straight iteration is just not thinkable. $\endgroup$ – Yves Daoust Apr 19 '20 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.