OpenSTA icon indicating copy to clipboard operation
OpenSTA copied to clipboard

Speed up approximate exponential function by 2.1x

Open rmlarsen opened this issue 1 year ago • 22 comments

This change replaces the fast exponential approximation based on the limit exp(x) = lim_{n->inf} (1+x/n)^n, which uses 1 double division, 1 double addition and 12 double multiplications. The new implementation uses Shraudolph's approximation, which uses 1 double multiplication, 1 double addition, and 1 integer shift. The Shraudolph approximation is accurate (maximum absolute error 2.98%) over a much larger interval than the old implementation. In fact, the 2.98% max error was measured on the interval [-707.703272; 707.703272], which is almost the entire interval on which exp(x) doesn't overflow the IEEE double range: [-709.78271; 709.78271]

In comparison, the old approximation has zero correct bits when the absolute value of the argument exceeds ~88.

Pivoted flame graph before: image

Pivoted flame graph after: image

rmlarsen avatar Dec 15 '23 21:12 rmlarsen