MathGroup Archive 1996

[Date Index] [Thread Index] [Author Index]

Search the Archive

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] ====


  • 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 ?