Polynomial Rootfinder repost

[William C Wickes]

Some people have indicated that they have had trouble finding this material
on comp.sources.hp48, so I'll post it here as well.

HP 48 Polynomial Rootfinder

The HP 48 object listed below in ->ASC form is a high-performance polynomial
root finder. Those of you who remember the HP 71B Math Pac will recognize
this as the same as the PROOT command from that Pac; it is in fact the same
assembly-language code, given an RPL front end to operate in the HP 48.
I will refer to the object as PROOT; you can, of course, give it any
name you please by storing it in a global variable.

PROOT takes a (real) vector of coefficients in descending order, and returns
a complex vector containing the polynomial roots:

[ An An-1 An-2 ... A0 ] PROOT -> [ R1 R2 ... Rn ]

represents the determination of the n (complex) zeros R1 ... Rn of the
nth-order polynomial

An x^n + An-1 x^n-1 + ... + A0

The coefficients Ai must be real numbers, but this limitation is at least
partially compensated for by the speed and accuracy of the algorithm. Also,
no initial guess or stopping criterion is required. PROOT uses
Laguerre's method for n>2, or the quadratic or linear formulas for n<=2.
You are referred to the HP 71 Math Pac Owner's Manual for more information.

The use of vectors rather than lists for the input and output derives from
PROOT's HP71 origins. You can easily add list/vector conversion around
this object to make a more versatile version. To be more fully compliant
with HP 48 style you can write user-language programs to extract the
polynomial coefficients from an arbitrary expression to use as a preliminary
to PROOT, and to convert the result elements back into a factored expression
(x-R1)(x-R2)...(x-Rn). Examples of such programs are listed in
HP 48 Insights Part II (if you'll excuse the plug).

Enjoy.

Bill Wickes
HP Corvallis Division

%%HP: T(3)A(R)F(.);
"D9D20D29512BF8171040D9D2088130F853059F30E2B30399162BC81881302653
08DA364EC307F8162ED73F2926DEE32FA42524430CAF0611920A20002CE30119
2078200CBD30D2473CCD2067610823179E7E78FB97601C914313016913210417
914313016E1641421011641321031C414313016E142CC8A85016416913210211
41311111411741411761131411333466200CA131340000912A134152716F058F
A4CB28E78D011A24902A090EA05A08BA501028F88AC0111CC10150C20AC28EC4
B0AC28E1AB011234084002490C708BE1605E26C002034889991088EA2A014710
91318E22D09795105118CA8E68B08EAEC08F88AC0119CE10952DAC2B468EECA0
AC2B468E02B011C135147CECE4B2CE5558E5B018E4F218E43A08EC4E08E2CB08
C62A08EA9901318E6AC08E29C005BCC8EDE90AF21081098C7F901438E85418FA
4CB28EFCD08EC4018E87118E05C08E859011C1351478E3FE08E3EF0D28E5EE00
58FBCEB28F779B2AC08F896B28F6DEB28F779B28FAA6B28EC0218ECEB0AF2AF3
2EB07B578ED2908E8BB08E97C01348E2C80147CE131AF0AF18E2AB08EFAB0AC0
18F1848ED8B010B8EE9B0058E5E808E33B08E89B08E2B808EA6B08E87B08E51B
08EBB808ED6B0AC21238AC50BCE1238ED7808EF2B08F88AC011BCE559058E04B
08EB880BCC8E13B08FD7EB28E44808E6FA018F1848E02808E7990460642F8EFF
70AF2CEAF3A5F8E82808EB4C08E73A08E7CA0058E5180AF3AF22B335441AFF8E
7F708E6B018E69A08EBAB0AF0AF18E07A08EA6A0D28E43D0AC08EFBB011C1351
79AE214D8EB7C08E60E08EDC908EA5A08FB8EB28EFD804606645794774A78E8D
D070578E0C804A411C13517914F96E918E68C072E673178E898052276078E24B
0057F0777478E93908E109011C135179AC2B46155420324A08E75C01348E1290
17F1743068ED9908EA890A0E50F8E66B077668E18907B868E88800576A68EE28
0719678968E02808EED808E24808ED5B005AF2CEAF32EB07B0774868ECB808E7
390AC28E0C7046064418ED7808ED0908E5BC0AF0AF18E1E808E199013477E514
7CE10AE61318EBD8013710B1378E9B808EEAB06D508E3C800571068E06808EFB
807BD578174F28EC8808E34808E498074D51CF1C48EB8807EA57BE65606E2B8E
55808EC5800577A51231338EE5801331237B7578B64FC8EF1808F88AC011ACE1
0A460646FAF210810974258E71807CB78EB18018F18473B68ECD6079A67A0571
A6AC08ED2908408C7FB07E3771E67AD48E79F08EE6B078D475258EF68013470A
670A4147131DACE10ACE06D670971331031338E96A07127AF2154716F154716F
15471697457154716F14416477171128AC021371088E469011813572E6712760
2007068B2017DC61CF1C46FA018F1847E177D9672067AE6057AB5724472B572B
67D34BCC7114BCC79867AE6760471767F35560628971B616F16475B57D967F65
16F16478F371657A467CE3BCC70C3BCC72F5729675B376267EE4560613970661
6F16473660573B312313371661331237E737A568FD7EB20706D711A8B7F17FE4
7295723617F1747963BCC744375845808C7C8F78E58F88AC011ACE10A4606F9E
07769575D578457AD58E28908E108078D2794777B40577037BA570D27E037AB2
75137113BCC75351361341357CB47C857D9579B27D657C75AF2AF32E303A8F79
B27B75779279C579A21371361377DF4763571627EA2BCC16F1647A827E357162
78D479357D057684781573627D727FF479048EBAC07A468508C419011C135179
157494E606BA005AF0CCAF12E305A852032EC07AE317F17478B47FF170947AB1
17F17473B38E54C08E44807CB173C17DA17623919606FEA760475748ED18078F
3776471C17D6179E5057F7170A17071743175E246062C08D04F01170157494E5
5B461554759605787176F072147C117071701579837F03785377E279737CF305
74017A41723378036A8A7CF575E27692734374C3AF22C32521AF7AD2BCE78907
F017357AF0AF12EB0579527AC67EA47F728F88AC0613A73A57C8211997A91118
05BCE1087BD074857D627FC0CE1087B0613411879361187A337923068F88AC00
7CE5AE8C836FAF9AF7AF601AFDAFFAFDAFE0104114131203427200CA018DF6EB
28D5BEB28D0CEB28DBCEB28D6DEB27EEF136061368FAC7B2071340174DF8DE19
B27BB264FF7E7F6CEF8D779B28D9DBB28DCBBB2058F64E927B318F64E9212011
C13517B147134150716F110150716F8F88AC01361451CB147CE1458AE00208F2
D760142164808C114ACA10413114710870C497D0013713411878C1DB8FC0760A
F011C94AD0B542EB055D0058F141A20476757F3F64BF114ACA104D2796497D00
AF011C94AE02EB0505CCAB07F35780F45D05D6C62034000504908BE0001FA8B2
4001AF0AF10305BCE7C8E2E9190094800017831740070318D99EB275716CEF75
917311792171EF7701AFAAFBAF50171F07ACF79E065CF720175A47AF065BF7BE
0759473E065AF7D105607673057C74700076C07D0E61A0AF0AF12EB05B05011C
F1C41CF1C41CF1C41CF1C41CF1CF1C90117F17417F17417F17417F17417F17F1
790118F18418F18418F18418F18418F18F1890116F16416F16416F16F16901D7
F3C3C6C3C3011CF1C48D660C218F1848DB40C21CF1C48D3EFB28DDFFB28D710C
28D130C220349020066202034E120069102034D52006C0020344F100D711C04C
B05134689F2034902006C0020344F100D711C04CB05134629F20321106DF1203
262062F12032B3067E120320506CD1203256061D12032A7066C12032F806BB12
0324A060B120329B065A12032EC06A9120323E06F8120328F064812032D01697
120322216E61203273163612032C41685120321616D41203267162412032B816
73120320A16C2120325B161212032AC166112032FD16B0120324F16001203211
06DF0203262062F02032B3067E020320506CD0203256061D02032A7066C02032
F806BB020324A060B020329B065A02032EC06A9020323E06F8020328F0648020
32D01697020322216E60203273163602032C41685020321616D4020326716240
2032B81673020320A16C2020325B161202032AC166102032FD16B007310665D7
B00686D20326200423310020D711CCB135017400634D04D711C135147EB7FFC2
03427200C3137CB135017C0069FC74006B0D04D711C135147EF174147CB7FBC2
034282006FBF774D7D0A779B75EC710A6E8B7AFC7E1D7B0A76C979C9706C720A
72D979D9736BBCC7FE973A9714C749C744C7BD97BA965B97FAC783BBCC7C797B
342E91DA1AC1B05AF223305AFA8D16EB277FB763C7B5979EF7E3C7F6F7FDB704
C8FB8EB276897FDA72497A7966DA77AE134D230270CEAF210810930270FB73AA
CE55F01793B7EEA057083718F11C13514704CE10AE67DAEAC0057FF87EBBAC27
ED88F88AC011ACE10A5FD058606079F8203431000EA730C8E588F77CD8ED48F8
F7AEB2720A5808CED7F11C135179157494AF17A4D8E768F8E228F73D95808C93
6F78407C8A7E1B8E628F766A712A75B28E6E7F8F7AEB28EE28F8ED18F7F8991D
808C967F8CE70F798C7BE97C997FD97D4E7CFB77B9754A78CA8FB8EB2057FE98
ED08FBCC8F0B7B27BE971C98EBA7F8F7A7B2203205075A98E397F8ECB7F8EFD7
F739978907929799C7C697B8D8EB57F7EBC058F7A7B28E467F8E967F73BD7E79
79197DC117F174700A8E227F7FBB7129057FA1746B7EF90572C18EC17F8EB37F
8E49DF7C4C8EFF6F78785008E4E6F6EA9726C74E87C497CD879098E2C8F8E578
F743974B877DC74C07B398E848F7BE87A988ED48F77BC8E348F8E478F7F8C72A
016F1648E618F75C88E668F7A708E518F8EB96F8E208F8EF86F8E466FAC67CD8
8E728F94A607640793C8EDD7F8EB68F8E818F768C8E768F8E8E7F70888EEF7F8
E9B7F766C8EB38F8CCC7FBCC118BCE108018E1D5F8E087F7CF87E5097D606D5C
8E0D5FAC28E2D5F8EB06F7D507D3C8E6F5F18F18474988E465F8E9D5F11A94A0
1118AC6108AC0018CE17F2E11991E70AC00191DB08E255F5FE77008DF0AB28E7
85F8E6E6F8EB75F8CC45F3191AF1A7504C405550B75A6E5DE25A3CB3481591D7
FBF5AD4AC001B2130B21307FF2"