views:

1051

answers:

9

I have a C++ application in which I need to compare two values and decide which is greater. The only complication is that one number is represented in log-space, the other is not. For example:

double log_num_1 = log(1.23);
double num_2 = 1.24;

If I want to compare num_1 and num_2, I have to use either log() or exp(), and I'm wondering if one is easier to compute than the other (i.e. runs in less time, in general). You can assume I'm using the standard cmath library.

In other words, the following are semantically equivalent, so which is faster:

if(exp(log_num_1) > num_2)) cout << "num_1 is greater";

or

if(log_num_1 > log(num_2)) cout << "num_1 is greater";
+1  A: 

Why don't you write some tests up and post your results? :)

kitchen
I was going to later this afternoon, but the S.O. community is too quick for me ;-)
redmoskito
+3  A: 

some quick tests in python (which uses c for math):

$ time python -c "from math import log, exp;[exp(100) for i in xrange(1000000)]"

real    0m0.590s
user    0m0.520s
sys     0m0.042s

$ time python -c "from math import log, exp;[log(100) for i in xrange(1000000)]"

real    0m0.685s
user    0m0.558s
sys     0m0.044s

would indicate that log is slightly slower

Edit: the C functions are being optimized out by compiler it seems, so the loop is what is taking up the time

Interestingly, in C they seem to be the same speed (possibly for reasons Mark mentioned in comment)

#include <math.h>

void runExp(int n) {
    int i;
    for (i=0; i<n; i++) {
        exp(100);
    }
}

void runLog(int n) {
    int i;
    for (i=0; i<n; i++) {
        log(100);
    }
}

int main(int argc, char **argv) {
    if (argc <= 1) {
        return 0;
    }
    if (argv[1][0] == 'e') {
        runExp(1000000000);
    } else if (argv[1][0] == 'l') {
        runLog(1000000000);
    }
    return 0;
}

giving times:

$ time ./exp l

real     0m2.987s
user     0m2.940s
sys      0m0.015s

$ time ./exp e 

real     0m2.988s
user     0m2.942s
sys      0m0.012s
cobbal
Nice idea, but Python may perform extra range checking on log, and it may well be implemented differently to OP's libs. Also, is the difference always around 7%? Because that could just be experimental error.
Mark
+5  A: 

Do you really need to know? Is this going to occupy a large fraction of you running time? How do you know?

Worse, it may be platform dependent. Then what?

So sure, test it if you care, but spending much time agonizing over micro-optimization is usually a bad idea.

dmckee
Even worse, it may be dependent on which processor you are running on (your app is almost certain to outlive the current generation of CPUs).
Michael Kohne
I haven't profiled yet, but this is likely to be a hot spot in my code. Nevertheless, you're probably right. I was just curious, mostly, and I thought it could be a useful question to be here for posterity.
redmoskito
Curiosity is never bad. Too many processor cycles are wasted today by developers not curious enough. "Just throw more hardware at it" is the root of all evil.
Svante
@Svante: The argument against premature optimization isn't that we can "just thrown more hardware at it", it is that (1) you can only gain much if you optimize the parts that are costing a lot in the first place, (2) optimizations have cost beyond the programmer time needed to write them, and (3) the total cost can and often do outweigh the total value of the optimization. So you test *first*. Now, redmoskito has indicated that this lies in a tight loop, so it is a good candidate, but...
dmckee
@Svante: You're missing the point. Curiosity is fine, and that is why you should PROFILE before assuming it is a problem. Too many programmer hours are wasted by people who think they can *guess* at where the CPU time is being spent, and *that* is the root of all evil, because it takes development time away from the places where it would actually make a difference.Profile first, and don't waste your time optimizing unless you've determined that what you're optimizing actually takes up enough time to need optimizing.
jalf
+1  A: 

It can depend on your libm, platform and processor. You're best off writing some code that calls exp/log a large number of times, and using time to call it a few times to see if there's a noticeable difference.

Both take basically the same time on my computer (Windows), so I'd use exp, since it's defined for all values (assuming you check for ERANGE). But if it's more natural to use log, you should use that instead of trying to optimise without good reason.

Mark
+6  A: 

Edit: Modified the code to avoid exp() overflow. This caused the margin between the two functions to shrink considerably. Thanks, fredrikj.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char **argv)
{
    if (argc != 3) {
        return 0;
    }

    int type = atoi(argv[1]);
    int count = atoi(argv[2]);

    double (*func)(double) = type == 1 ? exp : log;

    int i;
    for (i = 0; i < count; i++) {
        func(i%100);
    }

    return 0;
}

(Compile using:)

emil@lanfear /home/emil/dev $ gcc -o test_log test_log.c -lm

The results seems rather conclusive:

emil@lanfear /home/emil/dev $ time ./test_log 0 10000000

real    0m2.307s
user    0m2.040s
sys     0m0.000s

emil@lanfear /home/emil/dev $ time ./test_log 1 10000000

real    0m2.639s
user    0m2.632s
sys     0m0.004s

A bit surprisingly log seems to be the faster one.

Pure speculation:

Perhaps the underlying mathematical taylor series converges faster for log or something? It actually seems to me like the natural logarithm is easier to calculate than the exponential function:

ln(1+x) = x - x^2/2 + x^3/3 ...
e^x = 1 + x + x^2/2! + x^3/3! + x^4/4! ...

Not sure that the c library functions even does it like this, however. But it doesn't seem totally unlikely.

Emil H
+1: yours is different than mine because you're evaluating a changing value, while mine was being optimized by the compiler into nothing. So the mistake was mine, not yours I think
cobbal
Ah, interesting. Do you get similiar results when you do the same thing?
Emil H
No, the Taylor series for the exponential function converges faster than that for the natural logarithm. But that's probably irrelevant anyway because the math library most likely uses a minimax polynomial and not a Taylor polynomial.The reason exp is much slower than log in your test is probably that it overflows most of the time, and this needs to be handled. Note that exp(i) overflows already at around i = 700. log doesn't overflow.
fredrikj
I've modified my test to compensate for this. Thanks for the info. :)
Emil H
Your test is a bit unfair... Computing the log of a number between 1 and 100 is fairly straightfoward (it's a double between 0 and ~4.6). Computing exp(N) where N is between 1 and 100 is much more difficult. (exp(100) is 2.688x10^43.)
ParoXoN
+15  A: 

AFAIK the algorithms, the complexity is the same, the difference should be only a (hopefully negligible) constant. Due to this, I'd use the exp(a) > b, simply because it doesn't break on invalid input.

peterchen
Very good point about log() being more fragile. Especially since the performance difference is likely to be a non-issue in reality.
Michael Burr
Now this is a good reason for choosing exp() over log().
dmckee
+1, Agreed. Unless you're doing something really, really performance intensive, you shouldn't worry about micro-optimizations like this...
Emil H
Thanks for the answer--very helpful. I'll be using log(), though, because I'm working with extremely small positive values (they're probabilities), and I think precision-wise, I'll be better off.
redmoskito
interesting point, redmoskito, and it turned out a very interesting question.
peterchen
A: 

if you are sure that this is hotspot -- compiler instrinsics are your friends. Although it`s platform-dependent (if you go for performance in places like this -- you cannot be platform-agnostic) So. The question really is -- which one is asm instruction on your target architecture -- and latency+cycles. Without this it is pure speculation.

+2  A: 

Since you're working with values << 1, note that x-1 > log(x) for x<1, which means that x-1 < log(y) implies log(x) < log(y), which already takes care of 1/e ~ 37% of the cases without having to use log or exp.

Which added test may or may not be faster, but it's certainly a good approach to test and profile.
David Thornley
That's just brilliant.
redmoskito
A: 

It would make sense that log be faster... Exp has to perform several multiplications to arrive at its answer whereas log only has to convert the mantissa and exponent to base-e from base-2.

Just be sure to boundary check (as many others have said) if you're using log.

ParoXoN