Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Implementing the Exponential Function

pseudorandom.com

Post reply on HN
Print view View original

31–40 of 62 posts

Re: Implementing the Exponential Function

#31

Post by raphlinus »

dvt wrote: post #3

This is an awesome article! One of my favorite SO answers I remember researching dealt with the Padé approximation of tanh[1] (which I found was significantly better than the Taylor expansion), but the caveat was that it only worked within a very narrow neighborhood. I will say that the article didn't really touch on techniques that minimize IEEE 754 subnormal[2] performance impact, which is a very interesting proble…

You might enjoy a few of my favorite sigmoids: https://raphlinus.github.io/audio/2018/09/05/sigmoid.html

That's not a deep exploration of the numerical analysis (especially compared with OP), but it does make one point: traditional "numerical analysis" techniques tend to assume the traditional four mathematical operators as canonical, but if your goal is to get something computed on actual computer hardware quickly and reasonably accurately, you have a wider palette to play with. In particular, inverse square root is a primitive about as efficient as reciprocal on modern hardware (or if using Carmack's wtf trick).

Re: Implementing the Exponential Function

#32

Post by nitrogen »

dietrichepp wrote: post #2

I recently implemented the exponential function for a sound synthesizer toolkit I’m working on. The method I used was not mentioned in the article, so I’ll explain it here. I used the Remez algorithm, modified to minimize equivalent input error. This algorithm lets you find a polynomial with the smallest maximum error. You start with a set of X coordinates, and create a polynomial which oscillates up and down around…

I used something similar to implement an approximate square root function in a graphical DSP platform that only has addition and multiplication. A 4th-order polynomial gives satisfactory accuracy from -20dBFS to 0 dBFS, which was the region I cared about. It's hard to do better near the origin (-inf dB) though, because the slope of the square root approaches infinity.

Re: Implementing the Exponential Function

#33

Post by ithinkso »

contravariant wrote: post #21
bollu wrote: post #16

Earlier quoted context omitted.

Blessedly, in the complex analytic setting, these coincide, to they not? [Attempting to sanity-check my own understanding here]

In fact it is enough for functions to be complex differentiable once (in which case they'll automatically be differentiable infinitely often).

It's one of those theorems that still boggles my mind even though I know it for so many years now. Either complex functions are so much well behaved or complex differentiability is so much stronger condition, I can't decide which. Top it off with the uniqueness of analytic continuation and you start to wonder what causes real functions to be such a pain.

If anyone knows some nice articles about this topic I would love to read them

Re: Implementing the Exponential Function

#35

Post by nimish »

ithinkso wrote: post #33
contravariant wrote: post #21

Earlier quoted context omitted.

In fact it is enough for functions to be complex differentiable once (in which case they'll automatically be differentiable infinitely often).

It's one of those theorems that still boggles my mind even though I know it for so many years now. Either complex functions are so much well behaved or complex differentiability is so much stronger condition, I can't decide which. Top it off with the uniqueness of analytic continuation and you start to wonder what causes real functions to be such a pain. If anyone knows some nice articles about this topic I would lov…

It's the latter. Complex differentiability is a very strong condition.

Re: Implementing the Exponential Function

#36

Post by philzook »

Really interesting article!

Some other resources you may find interesting

https://fpbench.org/index.html - I think I saw a talk at FPTalks that felt related to your topic "Creating correctly rounded math libraries for real number approximations"

https://fpbench.org/community.html

https://hal-ens-lyon.archives-ouvertes.fr/ensl-01529804 - Correctly Rounded libm

https://www.mpfr.org/ - GNU Multi precision floating point

http://sollya.gforge.inria.fr/ - A tool for floating point code development

Re: Implementing the Exponential Function

#37

Post by [deleted] »

jbay808 wrote: post #25
dietrichepp wrote: post #2

I recently implemented the exponential function for a sound synthesizer toolkit I’m working on. The method I used was not mentioned in the article, so I’ll explain it here. I used the Remez algorithm, modified to minimize equivalent input error. This algorithm lets you find a polynomial with the smallest maximum error. You start with a set of X coordinates, and create a polynomial which oscillates up and down around…

I wouldn't recommend doing this directly -- there's no good polynomial that can represent the exponential function well over a wide range. Instead, it's better to exploit the definition of IEEE754 as an exponent and a mantissa. You calculate the exponent directly (because e^x = 2^(x/ln2)), and use the Remez algorithm to find a polynomial that fits just the mantissa.

[deleted]

Re: Implementing the Exponential Function

#38

Post by dietrichepp »

jbay808 wrote: post #25
dietrichepp wrote: post #2

I recently implemented the exponential function for a sound synthesizer toolkit I’m working on. The method I used was not mentioned in the article, so I’ll explain it here. I used the Remez algorithm, modified to minimize equivalent input error. This algorithm lets you find a polynomial with the smallest maximum error. You start with a set of X coordinates, and create a polynomial which oscillates up and down around…

I wouldn't recommend doing this directly -- there's no good polynomial that can represent the exponential function well over a wide range. Instead, it's better to exploit the definition of IEEE754 as an exponent and a mantissa. You calculate the exponent directly (because e^x = 2^(x/ln2)), and use the Remez algorithm to find a polynomial that fits just the mantissa.

Honestly, reading this comment made me a bit unhappy. Don't mansplain to me the things that I've done. The Remez algorithm requires that you specify the domain. If you tried to use it to approximate the exponential function over its entire domain the algorithm would diverge.

You have to explicitly choose a range [x1,x2] for the Remez algorithm. It minimizes the maximum error over that range.

I'm ordinarily happy to share the work I'm doing but this comment reminds me of the reasons I don't share much with HN.

Re: Implementing the Exponential Function

#39

Post by joppy »

ithinkso wrote: post #33
contravariant wrote: post #21

Earlier quoted context omitted.

In fact it is enough for functions to be complex differentiable once (in which case they'll automatically be differentiable infinitely often).

It's one of those theorems that still boggles my mind even though I know it for so many years now. Either complex functions are so much well behaved or complex differentiability is so much stronger condition, I can't decide which. Top it off with the uniqueness of analytic continuation and you start to wonder what causes real functions to be such a pain. If anyone knows some nice articles about this topic I would lov…

One way of understanding why complex differentiability is so strong is looking at a complex-to-complex function as a real function of two real inputs and two real outputs. The fact that h rather than |h| appears in the denominator of the complex derivative causes the derivative to be “aware” of the rotational nature of complex functions: this turns into a differential equation which must be satisfied by the real function (the Cauchy-Riemann equations).

Re: Implementing the Exponential Function

#40

Post by dvt »

raphlinus wrote: post #31
dvt wrote: post #3

This is an awesome article! One of my favorite SO answers I remember researching dealt with the Padé approximation of tanh[1] (which I found was significantly better than the Taylor expansion), but the caveat was that it only worked within a very narrow neighborhood. I will say that the article didn't really touch on techniques that minimize IEEE 754 subnormal[2] performance impact, which is a very interesting proble…

You might enjoy a few of my favorite sigmoids: https://raphlinus.github.io/audio/2018/09/05/sigmoid.html That's not a deep exploration of the numerical analysis (especially compared with OP), but it does make one point: traditional "numerical analysis" techniques tend to assume the traditional four mathematical operators as canonical, but if your goal is to get something computed on actual computer hardware quickly a…

This is great! Sometimes I wish I took more analysis back in school.
Post reply on HN