Efficient Approximation of Exponential Function in O(1) time

In this article at OpenGenus, we have explored an efficient approximation of Exponential Function that can be computed in O(1) time. This is also known as Schraudolph's method.

Table of contents:

1. Approximation of Exponential Function
2. Java implementation
3. C and C++ implementation

Approximation of Exponential Function

This method was developed by Nicol N. Schraudolph from IDSIA, Lugano, Switzerland in 2007.

We need to compute e^val.

This is an expensive operation and can be approximated efficiently using the following algorithm:

1. Get value of exponent val.
2. Compute tmp = (1512775 * val) + (1072693248 - 60801);\
3. Answer is tmp << 32 (left shifted by 32).

This approach involves:

• 1 multiplication, 1 addition and subtraction
• 1 left shift

This is an efficient in terms of computation.

The Time Complexity of this approach is O(1).

The space complexity is O(1) as well.

Java implementation

This is the Java implementation of the approach to approximate Exponent function:

public static double exp(double val) {
    final long tmp = (long) (1512775 * val) + (1072693248 - 60801);
    return Double.longBitsToDouble(tmp << 32);
}

C and C++ implementation

In Programming Languages like C and C++, this can be implemented using MACRO and is significantly, faster than other approaches of computing exponent.

In C, this approach is implemented as follows:

#include <math.h>
static union
[
    double d;
    struct
    [
        #ifdef LITTLE_ENDIAN
        int j, i;
        #else
        int i, j;
        #endif
    ] n;
] eco;

#define EXP_A (1512775)
#define EXP_C 60801
#define EXP(y) (eco.n.i = EXP_A * (y) + (1072693248 - EXP_C), eco.d)

With this article at OpenGenus, you must have the complete idea of how to approximate exponential function.