gt5223b@prism.gatech.EDU (Doug Berkland) (04/07/91)
Is there an easy way to get ALL roots of a polynomial of any degree?
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.
Thanks in advance.
--
Doug Berkland Internet: gt5223b@hydra.gatech.edu Phone: (404)676-9068
uucp: ...!{decvax,hplabs,ncar,purdue,rutgers}!gatech!prism!gt5223b
Georgia Institute of Technology, Atlanta GA 30332 <<Electrical Engineer>>
"If I don't have it, how do I know I don't want it?" --meedp@jareth.enet.dec.com (Eric Postpischil (Always mount a scratch monkey.)) (04/08/91)
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
hoford@sequoia.circ.upenn.edu (John Hoford) (04/08/91)
In article <21858@shlump.nac.dec.com> edp@jareth.enet.dec.com (Eric Postpischil (Always mount a scratch monkey.)) writes: >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. Is this true in the sense that, a solution involving a square root
hoford@sequoia.circ.upenn.edu (John Hoford) (04/09/91)
In article <21858@shlump.nac.dec.com> edp@jareth.enet.dec.com (Eric Postpischil (Always mount a scratch monkey.)) writes: >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. Is this true in the sense that, a solution involving a square root is a numerical solution. That is to find SQRT(x) programs implement some form of ('x = y^2' 'y' solve) Ps. My last atempt to post this got truncated (thanks Eric). John...
edp@jareth.enet.dec.com (Eric Postpischil (Always mount a scratch monkey.)) (04/09/91)
In article <40731@netnews.upenn.edu>, hoford@sequoia.circ.upenn.edu (John Hoford) writes: >>In short, no. For polynomials up to degree four, there are exact >>algebraic solutions. Beyond that, numerical methods must be used. >Is this true in the sense that, a solution involving a square root >is a numerical solution. >That is to find SQRT(x) programs implement some form of ('x = y^2' 'y' solve) I'm not quite sure what you are asking. However, my statement did not mean to exclude square roots. For example, sqrt(2) is considered an exact algebraic solution to x^2=2. For quadratic, cubic, and quartic polynomials, one can always find an exact algebraic solution, even if the answer is complex and involves square roots, cube roots, or quartic roots. The solution may be irrational, so it will not have an exact numerical representation, but the algebraic solution can be found. Many polynomials above degree four do have algebraic solutions, but in the general case, there is no exact algebraic solution for all polynomials of degree five, or of any higher degree. -- edp (Eric Postpischil) "Always mount a scratch monkey." edp@jareth.enet.dec.com
hoford@sequoia.circ.upenn.edu (John Hoford) (04/09/91)
In article <21917@shlump.nac.dec.com> edp@jareth.enet.dec.com (Eric Postpischil (Always mount a scratch monkey.)) writes: >I'm not quite sure what you are asking. However, my statement did not >mean to exclude square roots. I a not quite sure ether. > For example, sqrt(2) is considered an > exact algebraic solution to x^2=2. But what is sqrt(2)? The only way I know it is as the solution to x^2=2. I gusss what I am asking is, what does it meen to say something has an algebraic soloution and is ther any thing realy special about 5'th and above degree polynomials. if i defined a function f(k,a0,a1,...an) which gave me the k'th soloution to a polynomials of order n whose terms were a0..an and defined it as part of my "algebra" then any polynomial would have an "algebraic" soloution. What makes the functions sqrt() and "x^(1/y)" ok to use? Is this just convention? John Hoford
edp@jareth.enet.dec.com (Eric Postpischil (Always mount a scratch monkey.)) (04/10/91)
In article <40762@netnews.upenn.edu>, hoford@sequoia.circ.upenn.edu (John Hoford) writes: >But what is sqrt(2)? The only way I know it is as the solution to x^2=2. Besides knowing that sqrt(2) is a solution to x^2=2, we also know it is between 1.4 and 1.5 and that it is irrational. What does it mean to "know" something? Do we know 2.5 better than sqrt(2)? Part of the answer is that knowing something means knowing what its properties are, how it acts, how it relates to other things. 2.5 is 2 plus one-half; it is half of five. So we "know" sqrt(2) to the extent that we can square it, divide it into other numbers, et cetera. We can work with it, and that is our knowledge about it. >I gusss what I am asking is, what does it meen to say something >has an algebraic soloution and >is ther any thing realy special about 5'th and above degree >polynomials. One meaning of the word "algebraic" is "involving only a finite number of repetitions of addition, subtraction, multiplication, division, extraction of roots, and raising to powers" (Webster's New Collegiate Dictionary). In that meaning, polynomials of ONLY degree four and less have algebraic solutions. Polynomials of greater degree may have algebraic solutions, as x^8=n obviously does, but this is not guaranteed. Some polynomials of degree five and greater do not have solutions that can be found with only a finite number of repetitions of those operations. >What makes the functions sqrt() and "x^(1/y)" ok to use? >Is this just convention? Well, in one sense they are okay to use because that's what the word "algebraic" means. To answer a bit more deeply, the word "algebraic" means that because that definition is useful -- those functions are well understood. We can implement them with computers or by hand, we can analyze expressions involving them, et cetera. In other words, those are basic simple operations. So, in a sense, equations that can be solved with those operations are simpler than equations that cannot, and we call such solutions algebraic solutions. It's just a way of giving a name to a class of things. There is a proof that polynomials of degree five and greater do not have algebraic solutions, but it involves group theory beyond what I studied. You might be able to get an answer by asking in sci.math. -- edp (Eric Postpischil) "Always mount a scratch monkey." edp@jareth.enet.dec.com
KAZLOWF%PACEVM.BITNET@CUNYVM.CUNY.EDU (Michael Kazlow) (04/10/91)
It is impossible to find a general solution to a polynomial equation that has real or complex coefficients that can be expressed in terms of elementary functions that use radicals square roots, cube roots, etc.: The proof of this result uses Galois Theory. It can be found in most abstract algebra written for first year graduate mathematics students. It is also in many undergraduate texts. Note: The lack of a general formula is true for polynomials of degree of at least five:. This does not mean there is no general formula that use non-elementary functions. However, noone knows of such a formula! Galois Theory can be used to show two other classical problems have no solution: Squaring the circle and trisecting an angle with compass and straight edge. For the mathematically inclined Galois Theory is beautiful mathematics. From the computer of: Michael Kazlow (Bitnet: KAZLOWF@PACEVM) Acknowledge-To: <KAZLOWF@PACEVM>
tonl@hpuamsa.neth.hp.com (Ton 't Lam CRC) (04/10/91)
I use the program of Wayne Scott. It is a neat program indeed.
Regards,
Ton 't Lam.
This file is set up to be downloaded into a HP48sx but it should work just
fine with a HP28.
%%HP: T(3)A(R)F(.);
@ The following is a set of programs that I developed to find the roots of
@ polynomials. However as a bonus I also created a program to reduce any
@ polynomial into its quadric factors.
@
@ The first program is FCTP. (factor polynomial)
@ When it is passed the cooeficients of a polynomial in a list it returns the
@ factor of that polynomal. ex:
@
@ 1: { 1 -17.8 99.41 -261.218 352.611 -134.106 }
@ FCTP
@ 3: { 1 -4.2 2.1 }
@ 2: { 1 -3.3 6.2 }
@ 1: { 1 -10.3 }
@
@ This tells us that X^5-17.8*X^4+99.41*X^3-261.218*X^2+352.611*X-134.106
@ factors to (X^2-4.2*X+2.1)*(X^2-3.3*X+6.2)*(X-10.3)
@
@ Neat!
@
@ The next program is RT. (Roots)
@ If given a polynmoial it return its roots. ex:
@
@ 1: { 1 -17.8 99.41 -261.218 352.611 -134.106 }
@ RT
@ 5: 3.61986841536
@ 4: .58013158464
@ 3: (1.65, 1.8648056199)
@ 2: (1.65, -1.8648056199)
@ 1: 10.3
@
@ Very Useful!
@
@ These programs use the BAIRS program which performs Bairstow's method of
@ quadratic factors and QUD with does the quadratic equation.
@
@ Have Fun!
@ _____________________________________________________________________________
@ Wayne Scott | INTERNET: wscott@en.ecn.purdue.edu
@ Electrical Engineering | BITNET: wscott%ea.ecn.purdue.edu@purccvm
@ Purdue University | UUCP: {purdue, pur-ee}!en.ecn.purdue.edu!wscott
@ _____________________________________________________________________________
@ "To iterate is human. To recurse, divine."
DIR
FCTP
\<<
IF DUP SIZE 3 > THEN
BAIRS
FCTP
END
\>>
RT
\<< DUP SIZE \-> n
\<<
IF n 3 > THEN
BAIRS
\-> A B \<< A RT B RT \>>
ELSE
IF n 2 > THEN
QUD
ELSE
LIST\-> DROP NEG SWAP DROP
END
END
\>>
\>>
BAIRS
\<< LIST\-> 1 - 1 1 \-> n R S
\<< n 3 + 1 2 \->LIST 0 CON DUP \-> B C
\<<
DO
3 n 3 +
FOR J
'B' J n 6 + J - PICK R 'B' J 1 - GET * + S 'B' J 2 - GET * + PUT
'C' J 'B' J GET R 'C' J 1 - GET * + S 'C' J 2 - GET * + PUT
NEXT
'C' n 1 + GET SQ 'C' n 2 + GET 'C' n GET * - \-> DEN
\<< 'B' n 3 + GET 'C' n GET * 'B' n 2 + GET 'C' n
1 + GET * - DEN / DUP R + 'R' STO
'C' n 2 + GET 'B' n 2 + GET * 'C' n 1 + GET
'B' n 3 + GET * - DEN / DUP S + 'S' STO
\>>
UNTIL ABS .000000001 < SWAP ABS .000000001 < AND
END
n 1 + DROPN
1 R NEG S NEG 3 \->LIST
3 n 1 +
FOR J
'B' J GET
NEXT n 1
- \->LIST
\>>
\>>
\>>
QUD
\<< LIST\-> \->ARRY DUP 1 GET / ARRY\->
DROP ROT DROP SWAP
2 / NEG DUP SQ ROT
- \v/ DUP2 + 3 ROLLD -
\>>
ENDseroussi@hplred.HP.COM (Gadiel Seroussi) (04/10/91)
In / hplred:comp.sys.handhelds / hoford@sequoia.circ.upenn.edu (John Hoford) / 7:25 am Apr 9, 1991 / John Hoford says: > I gusss what I am asking is, what does it meen to say something > has an algebraic soloution and > is ther any thing realy special about 5'th and above degree > polynomials. A number is "algebraic" if it is the root of a polynomial with rational coefficients. A number is "trascendental" if it is not. Thus, all polynomials with rational coefficients have "algebraic" roots, regardless of their degree. However, for polynomials f(x) of degree n >= 5, there is no "solution by radicals". This means you cannot write finite formulas, involving arithmetic operations and m-th roots of any order, that will give you the solutions of f(x)=0 as symbolic functions of the coefficients of f. Of course, such formulas are known for n=1,2,3,4. Gadiel Seroussi HP Labs
akcs.ed@hpcvbbs.UUCP (Edwin S. Linderman) (04/12/91)
Actually, you folks are a bit mistaken. You CAN (Using a formula) get 5th degree roots. It is more than 3 pages long, typed, and there is also a proof that there is no 6th degree formula. CRC Doesn't have it, being that the 28th edition (light blue) is right beside me. otherwise, You need a good IBM/MAC program called Mathematica. Wonderful. It doesn't give roots like 1.74382394+342981571.329823i, it gives 1-Sqrt(5)^3 (over 2, etc.)... VERY good. Wolfram research
wscott@en.ecn.purdue.edu (Wayne H Scott) (04/12/91)
In article <26780001@hpuamsa.neth.hp.com> tonl@hpuamsa.neth.hp.com (Ton 't Lam CRC) writes: >I use the program of Wayne Scott. It is a neat program indeed. > >Regards, >Ton 't Lam. > > You have posted an old version of these routines. Here is a newer one, Article 1164 of comp.sys.handhelds: Newsgroups: comp.sys.handhelds Path: en.ecn.purdue.edu!wscott From: wscott@ecn.purdue.edu (Wayne H Scott) Subject: polynomial routines ver 3.2 Message-ID: <1990Sep3.153439.4558@ecn.purdue.edu> Organization: Purdue University Engineering Computer Network Date: Mon, 3 Sep 90 15:34:39 GMT Here it is, my polynomial routines version 3.2 Changes from version 3.1: - Faster PMUL - RT now works with complex cooeffients - various bug fixes These routines are in the public domain, but I ask that if you use any of them in one of your programs you give me credit. I am also not responsible for any damage caused by these programs. This package include the following programs. TRIM Strip leading zeros from polynomial object. IRT Invert root program. Given n roots it return a nth degree polynomial. PDER Derivative of a polynomial. RDER Derivative of a rational function. PF Partial Fractions. (Handles multiple roots!) FCTP Factor polynomial RT Find roots of any polynomial L2A Convert a list to an array and back. PADD Add two polynomials PMUL Multiply two polynomials. PDIV Divide two polynomials. EVPLY Evalulate a polynomial at a point. COEF Given an equation return a polynomial list. These programs are for the HP-48sx. I have a version of them that works correctly on the HP-28. Send me mail if you want it. I think people will find these very useful and work as I say, but if you find any bugs please send me E-Mail. Comments are also welcome. Some of these routines could be faster (PF, PMUL, ...) tell me if you know how to speed them up. _______________________________________________________________________________ Wayne Scott | INTERNET: wscott@en.ecn.purdue.edu Electrical Engineering | BITNET: wscott%ea.ecn.purdue.edu@purccvm Purdue University | UUCP: {purdue, pur-ee}!en.ecn.purdue.edu!wscott _______________________________________________________________________________ These programs all work on polynomials in the follows form: 3*X^3-7*X^2+5 is entered as { 3 -7 0 5 } Reasons why I use lists instead of arrays include: * lists look better on the stack. (multi-line) * The interactive stack can quickly put serveral items in a list. * Hitting EVAL will quickly return the elements on a list. * the '+' key will add a element to the end or beginning of a list or concat two lists * Internally the main program that needs to be fast (BAIRS) does 100% stack maniplations so speed of arrays vs. lists was not a major issue. * It would be easier for later releases to include symbolic polynomials. so going down the list... The first program is FCTP. (factor polynomial) When it is passed the cooeficients of a polynomial in a list it returns the factor of that polynomal. ex: 1: { 1 -17.8 99.41 -261.218 352.611 -134.106 } FCTP 3: { 1 -4.2 2.1 } 2: { 1 -3.3 6.2 } 1: { 1 -10.3 } This tells us that X^5-17.8*X^4+99.41*X^3-261.218*X^2+352.611*X-134.106 factors to (X^2-4.2*X+2.1)*(X^2-3.3*X+6.2)*(X-10.3) Neat! The next program is RT. (Roots) If given a polynmoial it return its roots. ex: 1: { 1 -17.8 99.41 -261.218 352.611 -134.106 } RT 5: 3.61986841536 4: .58013158464 3: (1.65, 1.8648056199) 2: (1.65, -1.8648056199) 1: 10.3 Very Useful! RT with work with complex cooeffients in the polynomial. These programs use the BAIRS program which performs Bairstow's method of quadratic factors and QUD with does the quadratic equation. TRIM is used to strip the leading zeros from a polynomial list. {0 0 3 0 7 } TRIM => { 3 0 7 } RDER will give the derivative of a rational function. ie. d x + 4 -X^2 - 8*x + 31 -- ------------- = -------------------------------- dx x^2 - 7*x + 3 x^4 - 14*x^3 + 55*x^2 - 42*x + 9 2: { 1 4 } 1: { 1 -7 3 } RDER 2: { -1 -8 31 } 1: { 1 -14 55 -42 9 } I don't know about you but I think it's useful. IRT will return a polynomial whose roots you specify. ie. If a transfer function has zeros at -1, 1 and 5 the function is x^3 - 5*x^2 - x + 5 1: { -1 1 5 } IRT 1: { 1 -5 -1 5 } PDER will return the derivtive of a polynomial. .ie The d/dx (x^3 - 5*x^2 - x + 5) = 3*x^2 - 10*x - 1 1: { 1 -5 -1 5 } PDER 1: { 3 -10 -1 } PF will do a partial fraction expansion on a transfer function. .ie s + 5 1/18 5/270 2/3 1/9 2/27 ----------------- = ----- + ----- - ------- - ------- - ----- (s-4)(s+2)(s-1)^3 (s-4) (s+2) (s-1)^3 (s-1)^2 (s-1) 2: { 1 5 } 1: { 4 -2 1 1 1 } PF 1: { 5.5555e-2 1.85185e-2 -.6666 -.11111 -.074074 } This program expects the polynomial of the numerator to be on level 2 and a list with the poles to be on level 1. Repeated poles are suported but they must be listed in order. The output is a list of the values of the fraction in the same order as the poles were entered. PADD, PMUL, and PDIV are all obvious, they take two polynomial lists off the stack and perform the operation on them. PDIV returns the polynomial and the remainder polynomial. L2A converts a list to and array. (and back) 1: { 1 2 3 } L2A 1: [ 1 2 3 ] L2A 1: { 1 2 3 } EVPLY evalutates and polynomial at a point. x^3 - 3*x^2 +10*x - 5 | x=2.5 = 16.875 2: { 1 -3 10 -5 } 1: 2.5 EVPLY 1: 16.875 P.S. Many thanks to Mattias Dahl & Henrik Johansson for fixs they have made. %%HP: T(3)A(R)F(.); DIR PDIV \<< DUP SIZE 3 ROLLD OBJ\-> \->ARRY SWAP OBJ\-> \->ARRY \-> c b a \<< a b IF c 1 SAME THEN OBJ\-> DROP / OBJ\-> 1 GET \->LIST { 0 } ELSE WHILE OVER SIZE 1 GET c \>= REPEAT DIVV END DROP \-> d \<< a SIZE 1 GET c 1 - - IF DUP NOT THEN 1 END \->LIST d OBJ\-> OBJ\-> DROP \->LIST \>> END \>> \>> TRIM \<< OBJ\-> \-> n \<< n WHILE ROLL DUP ABS NOT n 1 - AND REPEAT DROP 'n' DECR END n ROLLD n \->LIST \>> \>> RDER \<< \-> F G \<< G F PDER PMUL G PDER { -1 } PMUL F PMUL PADD G G PMUL \>> \>> IRT \<< OBJ\-> \-> n \<< IF n 0 > THEN 1 n START n ROLL { 1 } SWAP NEG + NEXT ELSE { 1 } END IF n 1 > THEN 2 n START PMUL NEXT END \>> \>> PDER \<< OBJ\-> \-> n \<< 1 n FOR i n ROLL n i - * NEXT DROP IF n 1 == THEN { 0 } ELSE n 1 - \->LIST END \>> \>> PF \<< MAXR { } \-> Z P OLD LAST \<< 1 P SIZE FOR I P I GET \-> p1 \<< IF p1 OLD \=/ THEN Z p1 EVPLY 1 P SIZE FOR J IF P J GET P I GET \=/ THEN p1 P J GET - / END NEXT p1 'OLD' STO { } 'LAST' STO ELSE IF { } LAST SAME THEN 1 { } 1 P SIZE FOR K P K GET IF DUP p1 == THEN DROP ELSE + END NEXT IRT Z SWAP ELSE LAST OBJ\-> DROP END RDER DUP2 5 PICK 1 + 3 ROLLD 3 \->LIST 'LAST' STO p1 EVPLY SWAP p1 EVPLY SWAP / SWAP ! / END \>> NEXT P SIZE \->LIST \>> \>> FCTP \<< IF DUP SIZE 3 > THEN DUP BAIRS SWAP OVER PDIV DROP FCTP END \>> RT \<< TRIM DUP SIZE \-> n \<< IF n 3 > THEN DUP BAIRS SWAP OVER PDIV DROP \-> A B \<< A RT B RT \>> ELSE IF n 2 > THEN QUD ELSE LIST\-> DROP NEG SWAP / END END \>> \>> L\178A \<< IF DUP TYPE 5 == THEN OBJ\-> \->ARRY ELSE OBJ\-> 1 GET \->LIST END \>> PADD \<< DUP2 SIZE SWAP SIZE \-> A B nB nA \<< A L\178A B L\178A IF nA nB < THEN SWAP END IF nA nB \=/ THEN 1 nA nB - ABS START 0 NEXT END nA nB - ABS 1 + ROLL OBJ\-> 1 GET nA nB - ABS + \->ARRY + L\178A \>> \>> PMUL \<< DUP2 SIZE SWAP SIZE \-> X Y ny nx \<< 1 nx ny + 1 - FOR I 0 NEXT 1 nx FOR I 1 ny FOR J I J + 1 - ROLL X I GET Y J GET * + I J + 1 - ROLLD NEXT NEXT { } 1 nx ny + 1 - START SWAP + NEXT \>> \>> EVPLY \<< OVER IF DUP TYPE 5 == THEN SIZE ELSE SIZE 1 GET END \-> a r n \<< a 1 GET IF n 1 > THEN 2 n FOR i r * a i GET + NEXT END \>> \>> COEF \<< \-> E n \<< 0 n FOR I 0 'X' STO E EVAL 'X' PURGE E 'X' \.d 'E' STO I ! / NEXT 2 n 1 + FOR I I ROLL NEXT n 1 + \->LIST \>> \>> EQ 1 DIVV \<< DUP 1 GET \-> a b c \<< a 1 GET c / DUP b * a SIZE RDM a SWAP - OBJ\-> 1 GETI 1 - PUT \->ARRY SWAP DROP b \>> \>> QUD \<< LIST\-> \->ARRY DUP 1 GET / ARRY\-> DROP ROT DROP SWAP 2 / NEG DUP SQ ROT - \v/ DUP2 + 3 ROLLD - \>> BAIRS \<< OBJ\-> 1 1 \-> n R S \<< DO 0 n 1 + PICK 0 0 0 4 PICK 5 n + 7 FOR J J PICK R 7 PICK * + S 8 PICK * + 7 ROLL DROP DUP 6 ROLLD R 3 PICK * + S 4 PICK * + 5 ROLL DROP -1 STEP 3 PICK SQ 3 PICK 6 PICK * - IF DUP 0 == THEN DROP 1 1 ELSE 6 PICK 6 PICK * 5 PICK 9 PICK * - OVER / 4 PICK 9 PICK * 8 PICK 7 PICK * - ROT / END DUP 'S' STO+ SWAP DUP 'R' STO+ UNTIL (0,1) * + ABS .000000001 < 7 ROLLD 6 DROPN END n DROPN 1 R NEG S NEG 3 \->LIST \>> \>> END -- _______________________________________________________________________________ Wayne Scott | INTERNET: wscott@en.ecn.purdue.edu Electrical Engineering | BITNET: wscott%ea.ecn.purdue.edu@purccvm Purdue University | UUCP: {purdue, pur-ee}!en.ecn.purdue.edu!wscott -- _________________________________________________________________________ Wayne Scott | INTERNET: wscott@ecn.purdue.edu Electrical Engineering | BITNET: wscott%ecn.purdue.edu@purccvm Purdue University | UUCP: {purdue, pur-ee}!ecn.purdue.edu!wscott
edp@jareth.enet.dec.com (Always mount a scratch monkey.) (04/17/91)
In article <2804f002:2682.5comp.sys.handhelds;1@hpcvbbs.UUCP>, akcs.ed@hpcvbbs.UUCP (Edwin S. Linderman) writes... >Actually, you folks are a bit mistaken. You CAN (Using a formula) get >5th degree roots. It is more than 3 pages long, typed, and there is also >a proof that there is no 6th degree formula. The general solution for quintic polynomials uses elliptic modular functions; the issue of discussion was algebraic solutions -- that is, solutions using only finite numbers of additions, subtractions, multiplication, divisions, raising to powers, and extractions of roots. -- edp (Eric Postpischil) "Always mount a scratch monkey." edp@jareth.enet.dec.com
edp@jareth.enet.dec.com (Always mount a scratch monkey.) (04/17/91)
In article <6230005@hplred.HP.COM>, seroussi@hplred.HP.COM (Gadiel Seroussi) writes... >> I gusss what I am asking is, what does it meen to say something >> has an algebraic soloution and >> is ther any thing realy special about 5'th and above degree >> polynomials. > >A number is "algebraic" if it is the root of a polynomial with rational >coefficients. In regard to previous messages, "algebraic solution" did not refer to the numbers that were zeroes of the polynomial being algebraic numbers; it referred to the solution itself being algebraic. In that context, "algebraic" means composed of only finite numbers of additions, subtractions, multiplications, divisions, raisings to powers, and extractions of roots. And to answer the previous questions, yes, there is something special about polynomials that are quintic and above: Their solutions cannot be written as algebraic (in the sense I have given above) formulae of their coefficients. Quartic polynomials and below can be solved with finite numbers of the listed operations; quintic polynomials and above cannot, in the general case. -- edp (Eric Postpischil) "Always mount a scratch monkey." edp@jareth.enet.dec.com
seroussi@hplred.HP.COM (Gadiel Seroussi) (04/19/91)
In article / hplred:comp.sys.handhelds / edp@jareth.enet.dec.com (Always mount a scratch monkey.) / 8:18 am Apr 17, 1991 / Eric Postpischil writes >In regard to previous messages, "algebraic solution" did not refer to the >numbers that were zeroes of the polynomial being algebraic numbers; it referred >to the solution itself being algebraic. In that context, "algebraic" means ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ >composed of only finite numbers of additions, subtractions, multiplications, >divisions, raisings to powers, and extractions of roots. > >And to answer the previous questions, yes, there is something special about >polynomials that are quintic and above: Their solutions cannot be written >as algebraic (in the sense I have given above) formulae of their coefficients. >Quartic polynomials and below can be solved with finite numbers of the listed >operations; quintic polynomials and above cannot, in the general case. However, the word "algebraic" has a well defined meaning in mathematics (especially when talking about roots of polynomials), and the concept we are referring to here is precisely captured by the term "solvable by radicals". There is no need to start redefining standard mathematical terms. Gadiel Seroussi
edp@jareth.enet.dec.com (Eric Postpischil (Always mount a scratch monkey.)) (04/23/91)
In article <6230006@hplred.HP.COM>, seroussi@hplred.HP.COM (Gadiel Seroussi) writes: >>In regard to previous messages, "algebraic solution" did not refer to the >>numbers that were zeroes of the polynomial being algebraic numbers; it >referred >>to the solution itself being algebraic. In that context, "algebraic" >means > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ >>composed of only finite numbers of additions, subtractions, >multiplications, >>divisions, raisings to powers, and extractions of roots. . . . > >However, the word "algebraic" has a well defined meaning in mathematics >>(especially when talking about roots of polynomials), and the concept >we are referring to here is precisely captured by the term >"solvable by radicals". There is no need to start redefining standard >mathematical terms. "Algebraic" has not just one meaning in mathematics, but several. The following is from James and James, _Mathematics Dictionary_ fourth edition (Van Nostrand Reinhold Company, New York: 1976), under "Algebraic": algebraic proofs and solutions. Proofs and solutions which use algebraic symbols and no operations other than those which are algebraic. See above, algebraic operations. Above that, we find: algebraic operations. Addition, subtraction, multiplication, division, evolution and involution (extracting roots and raising to powers). The meaning I used is correct in the context "algebraic solution". The meaning you gave is for "algebraic number". Is it dead yet? -- edp (Eric Postpischil) "Always mount a scratch monkey." edp@jareth.enet.dec.com
akcs.edlin@hpcvbbs.UUCP (Ed Linderman) (05/17/91)
and of course you can always use the CIS function
akcs.edlin@hpcvbbs.UUCP (Ed Linderman) (05/17/91)
Umm, I'm quite sure quintics can ALL be solved with algebraic solutions, I'll check with my prof, she introduced it to me, and I can type up the formula, but it is quite long
henry@zoo.toronto.edu (Henry Spencer) (05/18/91)
In article <283322a6:2812.1comp.sys.handhelds;1@hpcvbbs.UUCP> akcs.edlin@hpcvbbs.UUCP (Ed Linderman) writes: >Umm, I'm quite sure quintics can ALL be solved with algebraic solutions, There are formulas for cubics (3rd power) (slightly long) and quadrics (4th power) (seriously long), but provably none for quintics and up. Something like HP's numerical solver is often rather more useful in any case. Even with quadratics it's easy to find cases where the subtraction operation in the formula nearly destroys the precision of the result, while numerical techniques don't have that problem. -- And the bean-counter replied, | Henry Spencer @ U of Toronto Zoology "beans are more important". | henry@zoo.toronto.edu utzoo!henry
bob@dolores.Stanford.EDU (Bob Lodenkamper) (05/18/91)
In article <1991May17.230122.21758@zoo.toronto.edu> henry@zoo.toronto.edu (Henry Spencer) writes:
There are formulas for cubics (3rd power) (slightly long) and quadrics
(4th power) (seriously long), but provably none for quintics and up.
Something like HP's numerical solver is often rather more useful in any
case. Even with quadratics it's easy to find cases where the subtraction
operation in the formula nearly destroys the precision of the result,
while numerical techniques don't have that problem.
I agree that numerical solutions are often more useful for 3rd and 4th
degree equations, but I don't agree with the statement that numerical
methods of solution don't have numerical problems. Certainly one
can avoid a catastrophic cancellation, but closely spaced or multiple
roots are always difficult to compute accurately.
- Bobmatt@physics16.berkeley.edu (Matt Austern) (05/18/91)
In article <1991May17.230122.21758@zoo.toronto.edu> henry@zoo.toronto.edu (Henry Spencer) writes: > Something like HP's numerical solver is often rather more useful in any > case. Even with quadratics it's easy to find cases where the subtraction > operation in the formula nearly destroys the precision of the result, > while numerical techniques don't have that problem. Actually, there are cases where numerical stability is a problem in finding roots of a polynomial---this is especially true if you're trying to find all of the roots. A bigger problem (with HP's solver specifically) is that it doesn't find complex roots. I agree, though, that it's very useful: a page-long analytic solution is rarely enlightening. -- Matthew Austern Just keep yelling until you attract a (415) 644-2618 crowd, then a constituency, a movement, a austern@lbl.bitnet faction, an army! If you don't have any matt@physics.berkeley.edu solutions, become a part of the problem!