2
$\begingroup$

Following my answer to this question I wondered how WolframAlpha would tell me, so promptly and with so many decimal places, the result of

$$\left(\frac{2^{64}-1}{2^{64}}\right)^{2^{56}}$$

I thought that maybe WolframAlpha would take the log of that, and compute instead

$$2^{56}\cdot\log{\left(\frac{2^{64}-1}{2^{64}}\right)}$$

and then exponentiate it. But how would it still compute the logarithm of that number, and how would it then multiply with such a big number, and then raise $e$ to that power? I think I may have read somewhere (not exactly sure if my mind is tricking me) that computers use things like Taylor series for those calculations. But even if they do, those series are infinite sums! How do they do it?

Basically, my question comes down to:

What are the most common tricks/shortcuts/manipulations/approximations/... that computers do in order to provide precise answers in near-immediate time? I am thinking about things like big factorials, trigonometric functions, exponentiation, logarithms, ... Is there any good (and light), recommendable literature on this topic?

(P.S. I was not so sure of how to tag this question; if you have a suggestion, drop it in the comment section)

$\endgroup$
  • $\begingroup$ $\left(\dfrac{2^{64}-1}{2^{64}}\right)^{2^{64}}$ is extremely close to $e^{-1}$ though this is not how Wolfram Alpha did it $\endgroup$ – Henry Jan 15 '17 at 0:53
  • $\begingroup$ @Henry the exponent just so happens to be $2^{56}$. That number is roughly $0.9961$ as calculated by WolframAlpha. But even if it were very close to that, how would a computer find that and calculate it? $\endgroup$ – RGS Jan 15 '17 at 0:55
  • $\begingroup$ I am just saying that I would do an approximation of $e^{-1/2^8} =\exp( -0.00390625)\approx 0.99610136947011749$. Wolfram Alpha suggest that this is less than $10^{-21}$ from the value you asked for $\endgroup$ – Henry Jan 15 '17 at 1:08
  • 1
    $\begingroup$ $x^N$ can be calculated with about $\log_2{N}$ multiplications. So why are you surprised that WolframAlpha managed to do $56$ or so multiplications fairly quickly? $\endgroup$ – Rob Arthan Jan 15 '17 at 1:29
  • $\begingroup$ @RobArthan I am not exactly surprised; I just don't know how it works. Now that you talk about that I recall that one can indeed rewrite the exponent with base $2$. But that is very specific about my case. What if I wanted a factorial? Or the sine of a cosine? $\endgroup$ – RGS Jan 15 '17 at 1:31
1
$\begingroup$

A key issue is that Mathematica (lurking in the background of WolframAlpha) uses high precision arithmetic to do the computations. Roughly, most computers work with 53 bits to represent the digits of a number. This works out to about 16 decimal digits of precision, since $2^{53}$ has 16 decimal digits. Thus, in your problem, $2^{64}-1$ is indistinguishable from $2^{64}$ so that $$\frac{2^{64}-1}{2^{64}} = 1,$$ as far as machine precision is concerned. Thus, you might expect the result of your computation to be $1$ and that's exactly what the following Mathematica code yields:

N[(2^64 - 1)/2^64]^(2^56)
(* Out: 1.0 *)

Note that any computer code working in machine precision will yield the same thing. We can try it in Python, for example, here; or, if you have Python 3 installed:

((2**64-1)/2**64)**(2**56)
(* Out: 1.0 *)

Now, $2^{64}$ has 20 decimal digits so, if you compute with greater precision that that, we should be fine. In Mathematica:

N[(2^64 - 1)/2^64, 25]^(2^56)
(* Out: 0.99610137 *)

Again, this can be done in many computer languages. In Python, you can use the mpmath multi-precision library:

from mpmath import mp
mp.dps = 25
bf = mp.mpf(2**64)
((bf-1)/bf)**(2**56)
(* Out: mpf('0.996101369470117490062759194') *)

You can check this online here.

$\endgroup$

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.