Special-case `math.exp` approximation

[AlexanderViand]

For exp specifically, simple Taylor should beat the complex general-purpose approximation logic:

(Slide from one of Lawrence's talks, iirc)

[j2kun]

Intriguing, but I'd expect it depends heavily on the desired range. Taylor approximations are well behaved around a point, and their primary benefit over minimax approximations is that their behavior is predictable around that point.

But being able to represent the approximation as this exponentiation is really where I think the Taylor approximation would shine, because this could produce a tighter approximation with less depth than a minimax approach.

[j2kun]

The same reasoning could be used, say, for approximating sin/cos using double angle formulas: you apply a lower-degree approximation to a tight range, then use double-angle formulas to boost the range of approximation.

[AlexanderViand]

Yep, and afaik that is also a fairly common technique in FHE ML papers

[lawrencekhlim]

The e^x approximation via (1 + x / 2^k)^(2^k) is a pretty good approximation in absolute terms around the range [-2^k, 0]. Larger positive numbers it starts to get more and more inaccurate. It's based on the limit definition of exponentiation (where the limit as n goes to infinity (1 + x / n)^n is equal to e^x. The main benefit of using this approximation is how it turns exponentiation into k repeated squaring operations, which is fairly easy to implement and relatively cheap in terms of performance.

Still, I think that Chebyshev approximations still tend to be more accurate for the same multiplicative depth (but have more total operations).