Re: Horner scheme function ?

• To: mathgroup at smc.vnet.net
• Subject: [mg4461] Re: Horner scheme function ?
• From: rubin at msu.edu (Paul A. Rubin)
• Date: Mon, 29 Jul 1996 02:37:17 -0400
• Organization: Michigan State University
• Sender: owner-wri-mathgroup at wolfram.com

```In article <4shu29\$g7n at ralph.vnet.net>,
kraft at emma.bauwesen.uni-dortmund.de (Manfred Krafczyk) wrote:
->Hi all,
->does anybody know where I can find a Mathematica
->function that returns the Horner representation
->of a polynomial or how such a function could be
->constructed from the standard M. function set ?
->
->Any hints welcome,
->Manfred Krafczyk
->kraft at busch.bauwesen.uni-dortmund.de

This does it (more or less):

In[]:=
horner[ poly_, var_Symbol ] := poly /; FreeQ[ poly, var ]
horner[ poly_, var_Symbol ] :=
var horner[ PolynomialQuotient[ poly, var, var ], var ] +
PolynomialRemainder[ poly, var, var ] /;  PolynomialQ[ poly, var ]

In[]:=
p = -2 x^4 - x^3 + 3 x^2 - 2 x + 6;
horner[ p, x ]

Out[]=
6 + x (-2 + x (3 + (-1 - 2 x) x))

The only (cosmetic) problem is that Mathematica's idea of standard form for
the result apparently puts that innermost x factor on the right rather than
the left, i.e. (-1-2x)x rather than x(-1-2x).  I'm not sure why.  If that's
a problem, you might prefer to make a nested list of the factors and terms
rather than an expression.

This method uses recursion, which is ok for low degree polynomials.  I
don't know how much memory it will consume with high degree polynomials.
The following method may be more efficient:

In[]:=
horner2[ poly_, var_Symbol ] :=
ReleaseHold //@
((CoefficientList[ poly, var ] //.
{a_, b___} -> a + var Hold[ {b} ]) /.
{} -> 0) /;
PolynomialQ[ poly, var ]

In[]:=
horner2[ p, x ]
Out[]=
6 + x (-2 + x (3 + (-1 - 2 x) x))

Paul

**************************************************************************
* Paul A. Rubin                                  Phone: (517) 432-3509   *
* Department of Management                       Fax:   (517) 432-1111   *
* Eli Broad Graduate School of Management        Net:   RUBIN at MSU.EDU    *
* Michigan State University                                              *
* East Lansing, MI  48824-1122  (USA)                                    *
**************************************************************************
Mathematicians are like Frenchmen:  whenever you say something to them,
they translate it into their own language, and at once it is something
entirely different.                                    J. W. v. GOETHE

==== [MESSAGE SEPARATOR] ====

```

• Prev by Date: Need help in evaluating software
• Next by Date: Revealing HiddenSurfaces
• Previous by thread: Horner scheme function ?
• Next by thread: Re: Horner scheme function ?