This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: GCC and fast eveluaton of polynomials
- From: Stephen L Moshier <moshier at mediaone dot net>
- To: "Timothy J. Wood" <tjw at omnigroup dot com>
- Cc: Andreas Svrcek-Seiler <svrci at tbi dot univie dot ac dot at>, gcc at gcc dot gnu dot org
- Date: Tue, 20 Nov 2001 07:56:50 -0500 (EST)
- Subject: Re: GCC and fast eveluaton of polynomials
- Reply-to: moshier at moshier dot ne dot mediaone dot net
> An example might help here, say we have:
>
> y = a7*x^7 ... + a1*x + a0
>
> Rewrite this as:
>
> y = yEven + yOdd
> yEven = a6*x^6 + a4*x^4 ... + a0
> yOdd = a7*x^7 + a5*x^5 ... + a1*x
>
>
> Factor yOdd, leaving:
>
> y = yEven + x * yOdd;
> yEven = a6*x^6 + a4*x^4 ... + a0
> yOdd = a7*x^6 + a5*x^4 ... + a1
Some of the glibc functions were modified to work this way.
Unfortunately the details of how you would best keep the pipeline(s)
full are hardware dependent. I recall that the best code for a Motorola 88000
didn't work well at all on an Intel i860, for example.
> On Monday, November 19, 2001, at 04:48 AM, Andreas Svrcek-Seiler wrote:
> If I do it naively according to horner's scheme:
> (replaciing a log() call, that's even more time-consuming)
> u2 = u*u;
> v = (((((B5*u2+B4)*u2+B3)*u2+B2)*u2+B1)*u2+B0)*u;
>
> the coompiled executable is significantly slower than
> when the source reads
> v = B5*u2 + B4;
> v = v*u2 + B3;
> v = v*u2 + B2;
> v = v*u2 + B1;
> v = v*u2 + B0;
> v *= u;
That's really too bad! It looks like the second version will defeat
some optimizations, which would mean that writing it that way
actually prevents the compiler from making a mess of it. Please
mention what brand of computer you are using. If you give a complete
test case in the form of a bug report, maybe someone will investigate.