Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
5  
What kind of number are you talking about? Arbitary-sized integer? Fixed-size floating point? Arbitrary-precision floating point? –  Gilles Jun 19 at 12:03
    
@Gilles It's a good point. I didn't realise the difference was important. –  isomorphismes Jun 19 at 13:59
2  
I've seen on some Casio pocket calculators that log and power of a non-e number is much slower than ln/exp –  Lưu Vĩnh Phúc Jun 19 at 15:35
1  
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? –  jmite Jun 19 at 16:53
1  
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 –  vonbrand Jun 21 at 16:46

5 Answers 5

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

share|improve this answer
    
when you say "subnormal" – you clearly don't mean "sub-Gaussian"; do you mean "worse than [some benchmark of typicality]"? –  isomorphismes Jun 19 at 10:22
2  
@isomorphismes Here, 'subnormal' is with respect to how floats are implemented. See denormal numbers on Wikipedia. –  Paul Manta Jun 19 at 13:45

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.

share|improve this answer
4  
not actually. x maybe a floating-point type –  Lưu Vĩnh Phúc Jun 19 at 15:28
1  
Ah sorry I implicitly assumed that $x$ was an integer. –  Stephen Bly Jun 19 at 22:52
    
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´. –  Damon Jun 20 at 9:39

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.

share|improve this answer
    
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). –  isomorphismes Jun 19 at 10:39

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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