The Museum of HP Calculators

HP Forum Archive 21

[ Return to Index | Top of Index ]

Math Help!!
Message #1 Posted by Namir on 16 Apr 2012, 6:55 p.m.

Hi All,

How can one convert a polynomial of the general (and common) form: 

p(x) = Sum a(i) x^i, for i = 0,1,2,..,n
to a nested form: 
p(x) = A(0) + x^B(0)(1 + A(1)x^B(1)(1 + A(2)x^B(2)(1 + A(3)x^B(3)( .....(1 + A(n)x^B(n)))...)

Notice that each open parenthesis is in the form of: 

1 + A(i)x^B(i)

I saw these nested polynomials, as approximations for various common log and trig functions, on page 37 in Jon Smith's book Scientific Analysis on the Pocket Calculator, 2nd edition.

Namir

Edited: 16 Apr 2012, 6:56 p.m.

      
Re: Math Help!!
Message #2 Posted by Paul Dale on 16 Apr 2012, 7:29 p.m.,
in response to message #1 by Namir

Are you describing Horner's method here ?

If so, start factoring powers of x from whichever end has the highest power.

- Pauli

            
Re: Math Help!!
Message #3 Posted by Namir on 16 Apr 2012, 8:40 p.m.,
in response to message #2 by Paul Dale

Its' a variant of the regular Horner's method.

      
Re: Math Help!!
Message #4 Posted by Katie Wasserman on 16 Apr 2012, 8:13 p.m.,
in response to message #1 by Namir

Namir,

I'm not sure why you're looking into this, but this technique was very useful for writing a compact program to calculate pi like I did in this set of programs.

-Katie

            
Re: Math Help!!
Message #5 Posted by Namir on 16 Apr 2012, 8:41 p.m.,
in response to message #4 by Katie Wasserman

Yes Katie, the form of the polynomial in your link is what I am looking for.

Namir

      
Re: Math Help!!
Message #6 Posted by Les Wright on 16 Apr 2012, 8:17 p.m.,
in response to message #1 by Namir

I have that very book. On the page in question Smith has simply applied Horner's method, only in all of the examples on that page the central polynomial of the approximations in question are in x^2 rather than x. If you take a close look, you will see that all of your B(i)'s equal 2.

Hope this helps.

Les

            
Re: Math Help!!
Message #7 Posted by Namir on 16 Apr 2012, 8:44 p.m.,
in response to message #6 by Les Wright

Yes, all B(i) would typically be the same value.

      
Re: Math Help!!
Message #8 Posted by Peter Murphy (Livermore) on 16 Apr 2012, 8:18 p.m.,
in response to message #1 by Namir

Polynomial Expressions and Horner's Method are discussed on p. 79 of the HP 15C Owner's Handbook, but not How to Do It. Factorization is clearly what's required.

      
Re: Math Help!!
Message #9 Posted by Les Wright on 16 Apr 2012, 8:40 p.m.,
in response to message #1 by Namir

Namir, here is a simple 10th-degree example without odd-powered terms to demonstrate the method Smith uses:

1 + 3x^2 +4x^4 + 5x^6 + 2x^8 + 7x^10 = 1 + x^2(3 + x^2(4 + x^2(5 + x^2(2 + 7x^2))))

If C is a 0-based 5 element vector containing the coefficients in the order written, a C-code snippet might look like this:

C=[1,3,4,5,2,7];
y=x*x;
p=C[n-1];
for(j=n-2;j>=0;j--) p=p*y+c[j];

FWIW, it seems that Smith never uses the term "Horner's Method", but he does discuss the process of rewriting polynomials in this nested form on pages 31-32ff.

HTH,

Les

Edited: 16 Apr 2012, 9:01 p.m.

            
Re: Math Help!!
Message #10 Posted by Crawl on 16 Apr 2012, 10:37 p.m.,
in response to message #9 by Les Wright

Yes, just to be clear, the coefficients in both forms are the same. This is not "factoring".

      
Re: Math Help!!
Message #11 Posted by Allen on 16 Apr 2012, 11:32 p.m.,
in response to message #1 by Namir

I use wolfram alpha to calculate Horner forms. example:

http://www.wolframalpha.com/input/?i=4*Sum[4*n^2%2Bn%2B1%2C+{n%2C+0%2C%28s-1%29%2F2}]-3

Look under alternate forms.

[ Return to Index | Top of Index ]

Go back to the main exhibit hall