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,
->thanks in advance
->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] ====