The Mathematical Hacker

Re:The Mathematical Hacker by abrezas on Thursday December 13, 2012 @08:56AM (#4915653)

"Despite the aesthetic virtues ascribed to functional programming, I find the preceding solutions to be more beautiful than their recursive counterparts. They run in constant (rather than linear) time, and they are easily adapted to work with non-integer inputs."

Isn't this wrong? I don't think pow is computed in constant time.

[ Parent | on HN ]

Re:The Mathematical Hacker by Patient0 on Thursday December 13, 2012 @09:11AM (#4915701)

I think many floating point functions (e.g. sin, cosine) are implemented using Pade rational approximations - basically, the ratio of two polynomials. (http://www.dattalo.com/technical/theory/sinewave.html)

This usually gives enough accuracy for the purposes of floating point.

However, I'm not sure if "pow" can be usefully implemented this way. I am guessing no, because pow grows faster than any polynomial eventually...

edit: Hmm, pow at least looks linear here: http://www.netlib.org/fdlibm/e_pow.c

[ Parent | on HN ]

Re:The Mathematical Hacker by Jacobi on Thursday December 13, 2012 @09:10AM (#4915697)

I think that it can be implemented in constant time for floating point numbers. For integers I know that the exponentiation by squaring takes O(log(n))

[ Parent | on HN ]