On 8/8/06, Michael Ulm <michael.ulm / isis-papyrus.com> wrote:
> Jacob Fugal wrote:
> > Except that the implementation of Math.log itself is most likely
> > O(log2(n)) as well (unless the C source contains a gigantic lookup
> > table; unlikely). So using a strict O-based analysis, neither is
> > preferable over the other.
>
> I really doubt, that the implementation of Math.log (or any serious
> implementation of a log for that matter) is O(log(n)). Usually, logs
> are computed by a polynomial approximation on the interval (0.5, 1)
> for the mantissa, and a trivial computation for the exponent, which
> makes it O(1).

I stand corrected.

My guess is that the number of terms N in the polynomial that *need*
to be calculated for a certain precision in the approximation of
log(x) is in fact also O(log2(x)). But you're right that
implementations can just assume an N that will be sufficiently large
for all valid 32/64-bit values and always use that precision, in which
case it can be argued the algorithm is O(1).

Jacob Fugal