Re: [Algorithms] Approximating the pow() function

[<rob...@pl...>]

Oops, did I say Horner's form? I ment Estrin's method. I just saw the stack 
of multiplies to get the higher powers and assumed they were in order, but 
Guillaume was sneakier than that.

My argument was still partially valid in that the stack of multiples 
followed by the polynomial reconstruction should be replaced by a series of 
(non IEEE754) multiply-adds on modern hardware rather than just the 
multiples. Estrin's trick of doing N parallel MADDS and glueing them 
together using a running x^(2^i) makes the parallelism more explicit. e.g.

	// evaluate a + bx + cx^2 + dx^3 + ex^4 + fx^5 + gx^6 + hx^7
	// in three parallel steps

	// step 1 -------
	x2 = x*x;
         A = h*x+g;
         B = f*x+e;
         C = d*x+c;
         D = b*x+a;

	// step 2 --------
	x4 = x2*x2;
         AA = A*x2+B;
         BB = C*x2+D;

	// step 3 --------
	result = AA*x4 + BB;

- Robin Green.




Peter-Pike Sloan wrote:

> I was under the impression that horners method was actually less
> efficient on modern architectures because of the dependencies it
> creates...
> 
> -Peter-Pike Sloan