Serving the Quantitative Finance Community

 
User avatar
DominicConnor
Topic Author
Posts: 41
Joined: July 14th, 2002, 3:00 am

A faster exp() finction

January 2nd, 2015, 9:28 pm

8* speedup. Looks useful...here
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

A faster exp() finction

January 3rd, 2015, 5:15 pm

Interesting! It's a good example of the tension between encapsulation/reuse vs. application-specific code. Not all multiplies are created equal!
 
User avatar
AVt
Posts: 90
Joined: December 29th, 2001, 8:23 pm

A faster exp() finction

January 3rd, 2015, 9:18 pm

I do not quite understand "8* speedup". Is it for the multiple precisionin glibc or for the usual IEEE-754 double precision? And I miss somethingtowards correctness (see "The road ahead" at the end of the link). Hm ?
 
User avatar
Cuchulainn
Posts: 20252
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

A faster exp() finction

January 4th, 2015, 3:38 pm

I used to program in Fortran some time ago. But I can't remember expistential discussion like we are having here on C++. Was Fortran just better and/or C++ not there yet?
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

A faster exp() finction

January 4th, 2015, 4:20 pm

A cursory reading suggests that the algorithm is using multi precision intermediate values within the algorithm to get accurately aggregated and rounded results for a bounded-precision output (IEEE-754 double).The original algorithm does 32-bit multiplies when, in fact, as few as 3 bits are involved at that stage of the algorithm. Getting rid of 29 multiply-by-zero iterations provides the 8X speedup.
 
User avatar
Hansi
Posts: 41
Joined: January 25th, 2010, 11:47 am

A faster exp() finction

January 4th, 2015, 5:17 pm

There were some interesting side discussions related to this on HN if anyone cares, https://news.ycombinator.com/item?id=8828936All of this is a bit beyond what I care about. I'm just glad there are smarter people than me out there to come up with things like this.
 
User avatar
AVt
Posts: 90
Joined: December 29th, 2001, 8:23 pm

A faster exp() finction

January 4th, 2015, 8:09 pm

Thx. So it is to get exp correctly up to the last (binary) digit, rounded correctly (convention whatever), IEEE 754 for C (AFAIK C++ does not officially guarantee IEEE 754)
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

A faster exp() finction

January 4th, 2015, 9:37 pm

QuoteOriginally posted by: AVtThx. So it is to get exp correctly up to the last (binary) digit, rounded correctly (convention whatever), IEEE 754 for C (AFAIK C++ does not officially guarantee IEEE 754)Yes. My guess (and it is only a guess!) is that the polynomial approximation that they use does not converge that quickly so it's easy for the bits in the intermediate terms beyond the LSB to accumulate to change the LSB (or other low-order bits).
 
User avatar
Cuchulainn
Posts: 20252
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

A faster exp() finction

January 5th, 2015, 2:45 pm

QuoteOriginally posted by: Traden4AlphaQuoteOriginally posted by: AVtThx. So it is to get exp correctly up to the last (binary) digit, rounded correctly (convention whatever), IEEE 754 for C (AFAIK C++ does not officially guarantee IEEE 754)Yes. My guess (and it is only a guess!) is that the polynomial approximation that they use does not converge that quickly so it's easy for the bits in the intermediate terms beyond the LSB to accumulate to change the LSB (or other low-order bits).Polynomials are not great at approximation; I would expect rational functions or continued fractions. But the compiler builders have their reasons I assume.
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

A faster exp() finction

January 5th, 2015, 3:10 pm

QuoteOriginally posted by: CuchulainnQuoteOriginally posted by: Traden4AlphaQuoteOriginally posted by: AVtThx. So it is to get exp correctly up to the last (binary) digit, rounded correctly (convention whatever), IEEE 754 for C (AFAIK C++ does not officially guarantee IEEE 754)Yes. My guess (and it is only a guess!) is that the polynomial approximation that they use does not converge that quickly so it's easy for the bits in the intermediate terms beyond the LSB to accumulate to change the LSB (or other low-order bits).Polynomials are not great at approximation; I would expect rational functions or continued fractions. But the compiler builders have their reasons I assume.Indeed. I would assume that various people have created various algorithms for computing exp() or pow() to the Nth bit and found that this method was fastest. But if algorithm builders start using bespoke multiplication or division algorithms, then maybe a continued fraction, rational function, or some other exotic approximation might be faster still.
 
User avatar
ExSan
Posts: 493
Joined: April 12th, 2003, 10:40 am

A faster exp() finction

January 14th, 2015, 10:53 pm

I am fan of Taylor Series
°°° About ExSan bit.ly/3U5bIdq °°°