Implementation of pow(3m) function

[Richard A. O'Keefe]

In article <46584 at brunix.UUCP>, gvr at cs.brown.edu (George V. Reilly) writes:
> There are many common special cases where calling pow is unwise ...

> The following routine can be used to calculate x^n, where n is a non-negative
> integer.  Instead of requiring the n-1 multiplications that the naive
> algorithm would use, it requires lg n multiplications.

> Caveat: I would expect any decent implementation of pow to do this, though
> this power function should be slightly faster.

UNIX implementations of pow _do_ do that.  However, consider
	x**(n-eps)	=> exp(log(x)*(n-eps))
	x**n		=> squaring-and-multiplying used
	x**(x+eps)	=> exp(log(x)*(n+eps))
The code implementing the exp-and-log method had better be _very_ good,
or pow(x,y) may fail to be monotone in y.  That can do nasty things to
some iterative algorithms.  [There _are_ some very good algorithms now,
would you believe 0.54 ULP worst case for exp() using IEEE?]
Consider also that for n sufficiently large, and for exp() and log()
sufficently well implemented, the exp() and log() method may be _more_
accurate than the squaring-and-multiplying method.

-- 
Distinguishing between a work written in Hebrew and one written in Aramaic
when we have only a Latin version made from a Greek translation is not easy.
(D.J.Harrington, discussing pseudo-Philo)