4 ms·
"Despite the aesthetic virtues ascribed to functional programming, I find the preceding solutions to be more beautiful than their recursive counterparts. They r
by abrezas 14y ago
"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.
- Jacobi 14y agoI 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))
- Patient0 14y agoI 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 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 http://www.netlib.org/fdlibm/e_pow.c