Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

"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.



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


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))




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: