Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!uunet!samsung!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.c
Subject: Re: Implementation of pow(3m) function
Keywords: math-library exponentiation C
Message-ID: <3511@goanna.cs.rmit.oz.au>
Date: 4 Aug 90 08:31:15 GMT
References: <1990Aug2.120706.25713@bnrgate.bnr.ca> <13474@smoke.BRL.MIL> <46584@brunix.UUCP>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 26

In article <46584@brunix.UUCP>, gvr@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)