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