Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!elroy.jpl.nasa.gov!decwrl!pa.dec.com!shlump.nac.dec.com!jareth.enet.dec.com!edp
From: edp@jareth.enet.dec.com (Eric Postpischil (Always mount a scratch monkey.))
Newsgroups: comp.sys.handhelds
Subject: Re: Finding roots of Tertiary and above equations?
Message-ID: <21858@shlump.nac.dec.com>
Date: 8 Apr 91 13:45:11 GMT
References: <25744@hydra.gatech.EDU>
Sender: newsdaemon@shlump.nac.dec.com
Reply-To: edp@jareth.enet.dec.com (Eric Postpischil (Always mount a scratch monkey.))
Organization: Digital Equipment Corporation
Lines: 89

In article <25744@hydra.gatech.EDU>, gt5223b@prism.gatech.EDU (Doug
Berkland) writes:

>Is there an easy way to get ALL roots of a polynomial of any degree?

In short, no.  For polynomials up to degree four, there are exact
algebraic solutions.  Beyond that, numerical methods must be used. 
There are good methods (and the 48 has a good
method built in, for real solutions), but they are not guaranteed to
find all roots.

>I need to use this mostly on tertiary and above, and I need complex
>roots to be revealed as well.  I need this for a 28s.

Here are algebraic solutions for tertiary and quartic equations:

    From Chemical Rubber Company's _Standard Mathematical Tables_:
    
    A cubic equation, y^3+py^2+qy+r=0 may be reduced to the form
    
    	x^3+ax+b=0
    
    by substituting for y the value, x-p/3.  Here
    
    	a=1/3*(3q-p^2) and b = 1/27*(2p^3-9pq+27r).
    
    For solution, let
    
    	A = (-b/2+sqrt(b^2/4+a^3/27))^1/3,
    
    	B = -(b/2+sqrt(b^2/4+a^3/27))^1/3,
    
    then the values of x will be given by
    
    	x = A+B, -(A+B)/2 + (A-B)*sqrt(-3)/2, -(A+B)/2 - (A-B)*sqrt(-3)/2.
    
    If p, q, r are real, then
    
    	If b^2/4+a^3/27 > 0, there will be one real root and two conjugate
    	complex roots.
    	If b^2/4+a^3/27 = 0, there will be three real roots of which at
    	least two are equal.
    	If b^2/4+a^3/27 < 0, there will be three real and unequal roots.
    
    
    A quartic equation,
    
    	x^4+ax^3+bx^2+cx+d=0,
    
    has the resolvent cubic equation
    
    	y^3 - by^2 + (ac-4d)y - a^2d + 4bd - c^2 = 0.
    
    Let y be any root of this equation, and
    
    	R = sqrt(a^2/4-b+y).
    
    If R != 0, then let
    
    	D = sqrt(3a^2/4-R^2-2b+(4ab-8c-a^3)/4R)
    
    and
    
    	E = sqrt(3a^2/4-R^2-2b-(4ab-8c-a^3)/4R)
    
    If R = 0, then let
    
    	D = sqrt(3a^2/4-2b+2sqrt(y^2-4d))
    
    and
    
    	E = sqrt(3a^2/4-2b-2sqrt(y^2-4d)).
    
    Then the four roots of the original equation are given by
    
    	x = -a/4 + R/2 1 D/2
    
    and
    
    	x = -a/4 - R/2 1 E/2.
    
    (If viewed without extended character support, the "plus or minus"
    character above may appear oddly -- it is the operator between the
    "R/2" and the "D/2" or "E/2".)
    
  
				-- edp (Eric Postpischil)
				"Always mount a scratch monkey."
				edp@jareth.enet.dec.com