14
$\begingroup$

Forgive the naïveté that will be obvious in the way I ask this question as well as the fact that I'm asking it.

Mathematicians typically use $\exp$ as it's the simplest/nicest base in theory (due to calculus). But computers seem to do everything in binary, so is it faster on a machine to compute 2**x than Math::exp(x)?

$\endgroup$
7
  • 8
    $\begingroup$ What kind of number are you talking about? Arbitary-sized integer? Fixed-size floating point? Arbitrary-precision floating point? $\endgroup$ Jun 19 '14 at 12:03
  • 1
    $\begingroup$ @Gilles It's a good point. I didn't realise the difference was important. $\endgroup$ Jun 19 '14 at 13:59
  • 3
    $\begingroup$ I've seen on some Casio pocket calculators that log and power of a non-e number is much slower than ln/exp $\endgroup$
    – phuclv
    Jun 19 '14 at 15:35
  • 2
    $\begingroup$ To risk being blunt, have you tried timing them both and seeing which is faster? Or are you speaking of speed in an $O(f(n))$ complexity sense? $\endgroup$
    – jmite
    Jun 19 '14 at 16:53
  • 1
    $\begingroup$ The language is in charge to select the fastest way and will make a good job at it. Only in case the utmost speed is required, and measurements have shown that this is relevant to performance should you worry about this kind of stuff $\endgroup$
    – vonbrand
    Jun 21 '14 at 16:46
20
$\begingroup$

Since this is CS and not Stackoverflow, I'm going to assume that you're asking a question about numeric analysis, and (to keep things simple) IEEE-754 floating point in particular. In that case, the answer to your question partly depends on what you mean by "easier", and partly on the details of the system.

No modern CPUs that I'm aware of have an instruction built in which does exactly what you'd expect either for either the $e^x$ operation (which henceforth we will call exp, its usual name in C) or $2^x$ (exp2). They are both implemented using library functions.

As is the case with all numeric methods for transcendental operations, there are a few special cases to consider:

exp(NaN) = NaN
exp(+Inf) = +Inf
exp(-Inf) = 0

However, there is another thing that makes the problem slightly less complicated: the useful domain is quite small. For binary32, exp(x) underflows if $x < -104$ or so, and overflows if $x > 88.7$ or so. Unusually for transcendental operations, we can also ignore the subnormal case, since exp(x) is indistinguishable from 1.0 if x is subnormal. All of the above is also true for exp2, except that the domain is slightly different.

Your intuition is right in that most implementations compute $e^x = 2^{x/\ln 2}$. However, the cost of that multiplication by $\frac{1}{\ln 2}$ is trivial compared to the rest of computing exp2. A typical method uses a precomputed table with $K$ elements:

$$\hbox{exp2}(x) = 2^n \times T[j] \times P(y)$$

where $n$ is the integer part of $x$, the table $T$ contains values of $2^{j/K}$ for all $j$ in the range $[0,K)$, and $P$ is some polynomial approximation to $2^x$ (quartic is sufficient for binary32) in the range $[0,\frac{1}{K})$. The $2^n$ part is cheap, since it's just manipulating the exponent. $T$ is a lookup table. So $P$ is likely to be the expensive part of the operation.

I should point out for completeness that Intel x86 FPUs include an instruction called f2xm1, which computes $2^x-1$ for $x$ in the range $[-1,1]$. However, on a modern CPU, this is a fairly expensive and non-pipelined instruction, and you are highly discouraged from using it. As the Intel Optimization Reference Manual Section 3.8.5 rightly notes:

Although x87 supports transcendental instructions, software library implementation of transcendental function can be faster in many cases.

Edit: It's been pointed out in the comments that I should explain some of the new terminology used in IEEE 754-2008. Some of the language has changed since 1985 and 1987, and most people are far more familiar with the old jargon.

The terms "binary32" and "binary64" are the new names for 32-bit and 64-bit binary floating-point numbers, which the old standard called "single" and "double" respectively.

The term "subnormal number" replaces the previous term "denormal number" or "denormalized number".

$\endgroup$
3
  • $\begingroup$ when you say "subnormal" – you clearly don't mean "sub-Gaussian"; do you mean "worse than [some benchmark of typicality]"? $\endgroup$ Jun 19 '14 at 10:22
  • 2
    $\begingroup$ @isomorphismes Here, 'subnormal' is with respect to how floats are implemented. See denormal numbers on Wikipedia. $\endgroup$
    – Paul Manta
    Jun 19 '14 at 13:45
  • $\begingroup$ Incidentally, I did oversimplify the "typical method" just a little bit. It's possible to implement exp2() and exp() with ulp accuracy using just one small (and quite easy to understand) extension to the method presented here, but an explanation of the small easy-to-understand extension would probably double the length of the answer! $\endgroup$
    – Pseudonym
    Feb 6 '17 at 22:18
7
$\begingroup$

If by 2**x you mean $2^x$, then yes. We can use the left-shift operator <<, i.e. we compute 1 << x. This is lightning-fast as it is a primitive machine instruction in every processor I know of. This can not be done with any base other than 2. Moreover, integer exponentiation will always be faster than real exponentiation, as floating point numbers take longer to multiply.

$\endgroup$
3
  • 4
    $\begingroup$ not actually. x maybe a floating-point type $\endgroup$
    – phuclv
    Jun 19 '14 at 15:28
  • 1
    $\begingroup$ Ah sorry I implicitly assumed that $x$ was an integer. $\endgroup$
    – gardenhead
    Jun 19 '14 at 22:52
  • $\begingroup$ If x is not an integer (say, 20.75), you would set the mantissa to 2 and the exponent to the rounded value of x as the most accurate estimate (precise representation not being possible). Which, too, is much faster than `pow´. $\endgroup$
    – Damon
    Jun 20 '14 at 9:39
2
$\begingroup$

If 2**x is a function on integers, then I agree with Stephen's answer, shift is cheaper. But I typically see that as 2^x and ** to indicate floating point exponentiation. For this case, I would expect similar performance between ** and ^ since both exp and pow (the underlying operation for **) are both transcendental approximation operations.

$\endgroup$
1
  • $\begingroup$ Interesting, I didn't know ** was considered a synonym for the floating-point version (and, silly me, I'd forgotten the two would be different). $\endgroup$ Jun 19 '14 at 10:39
1
$\begingroup$

Since 2^x = e^(x * ln 2) and e^x = 2^(x * log2 (e)), you wouldn't expect much difference.

For x close to zero, one would usually use a polynomial e^x = 1 + x + x^2/2 + x^3/6 ..., nicely optimised to cut off as soon as possible while keeping the rounding error small. Clearly 2^x is a tiny, tiny bit slower to calculate. "x close to 0" would usually be values of x where sqrt (1/2) <= e^x <= sqrt (2). Restricting the range of x makes sure that the polynomial degree need not be chosen too high.

For larger x, one would usually calculate 2^x by letting x = x' + x'', where x' is an integer and -0.5 <= x'' <= 0.5. 2^x' would then be calculated by constructing a floating point number with the right bit pattern, and 2^x'' by using the e^x method for small x. Here, 2^x is a tiny bit faster. Moreover, if x is largish (say x = 100.3), just multiplying x by log2 (e) would introduce an unacceptable rounding error (because there are many fewer fractional bits), so more care needs to be taken.

And hopefully a good library function would take care that whenever x <= y, e^x <= e^y and 2^x <= 2^y, no matter what the rounding errors are. Achieving that kind of thing can be tricky.

Important to notice: If you want to calculate one function, and the other has a faster implementation, you can bet that multiplying your argument with a suitable constant and calling the faster function will not gain you any speed, and may lose substantial precision.

$\endgroup$
0
$\begingroup$

You've got to understand that math on a computer is done in different ways by different software, hopefully coming up with consistent answers. Looking at most software I think computers behave like well - computers and will calculate the answer the long way around even for like 0^0. The problem is that special cases involve "recognition" which doesn't occur for free in digital computers. This means that only in those cases where having the answer will speed things up "the most" will optimization occur. But in those cases it will occur extremely well. Also note that several different recognitions may have to be done to get the right answer. This is called speed optimization levels and this has occurred to the maximum professional extent in the basis of most software called GNU "C". This is because here minute differences in run time from software to software and machine to machine is used there as quality acceptance figures. In other interpreters usually only if a "zero flag" occurs as a side effect of previous calculations will speed up recognition be performed. such as 0 * x => C0.

$\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.