On Convergence Rates of Root-Seeking Methods

[Gerson W. Barbosa]

(03-09-2018 02:00 PM)emece67 Wrote:  I've tested this 4th order Taylor with only 1 division. The results are a little disappointing.

Decimal Basic is not the right tool for this test, but I did it anyway. It's limited to 1 thousand digits and the precision cannot be changed.
Starting with a 16-digit approximation, the number of correct digits is quadrupled at each iteration. Thus, for 268.435.456 digits only 12 iterations would suffice ( log(268435456)/log(4) - 2 ). Ideally the precision should be set to 64 digits in the first iteration, then to 256 in the second iteration, then to 1024 in the third iteration and so on, but I cannot do it in Decimal Basic.

OPTION ARITHMETIC DECIMAL_HIGH ! 1000 digits precision
INPUT x
LET r = EXP(LOG(x)/2)
LET t = TIME
PRINT r
DO
LET a = r
LET b = r*r
LET r = (b*(b*(b*(20*x - 5*b + 40) + (120 - 30*x)*x) + x*x*(20*x - 40)) + (8 - 5*x)*x*x*x)/(128*b*b*r)
PRINT r
LOOP UNTIL ABS(r - a) < 1E-256
PRINT SQR(x) - r
PRINT
PRINT TIME - t;" seconds"
PRINT
END

? 2
1.414213562373095
1.414213562373095048801688724209698078569671875376948073176679737989479122515585022787243548195807986806093853455270729739546313528476579927594917​19132295975097
78511905460519930449443820000402107044034260340386343880911130547966945813563882​29288359585276126491113757787998102600361450207381045186090436903909837008746643​
10347026139854082311463096492085942752871500618232557795510861959579135040684685​69392040023760526772118640227753720558095337126185503740848528003003220083571259​
78760074662894146616142755770477791864670027513055471099322605191320081824714171​58427394358697639180854278403008712404509644239238267271289740289167825812746163​
06614807181347711085881252716913249041129412872705291204646535635668829464403089​72859172411054988437943106627597053434432708976403774980364280296083588274483068​
90320789038870933116715401196155056676252437765219655389881281780333497686451818​23188802504726858350883437664116300306244902929112295963603771463834304635321134​
83159222912044330867518715241960119192026
1.414213562373095048801688724209698078569671875376948073176679737990732478462107​03885038753432764157273501384623091229702492483605585073721264412149709993583141​
32226659275055927557999505011527820605714701095599716059702745345968620147285174​18640889198609552329230483763417799908824040833757274424682543742882438438438070
45310063642726152360461106439741659989781643283198107018711015717646721345555956​34138328395716863930924425632516611811108073845894133895402501220018056132779461​
78199284355998211437151241574470660408495214036434662520605856846458150316934024​75444690707768303296469996147472177954132880251268214102352564481045043373214707​
37038015470189348837678162553849565902247519824742415713391547280188975735650003​39167513251254677743584922032240364649937930685912128733124895129684082793457798​
60719307754973604681004724614221457940961258955293138740256354060891882186677887​35355852898088999919542662057387970464289475610337999433702645392165833753575717​
67992903973693340385046714018520340468998
1.414213562373095048801688724209698078569671875376948073176679737990732478462107​03885038753432764157273501384623091229702492483605585073721264412149709993583141​
32226659275055927557999505011527820605714701095599716059702745345968620147285174​18640889198609552329230484308714321450839762603627995251407989687253396546331808​
82964062061525835239505474575028775996172983557522033753185701135437460340849884​71603868999706990048150305440277903164542478230684929369186215805784631115966687​
13013015618568987237235288509264861249497715421833420428568606014682472077143585​48741556570696776537202264854470158588016207584749226572260020855844665214583988​
93944370926591800311388246468157082630100594858704003186480342194897278290641045​07263688131373985525611732204024509122770022694112757362728049573810896750401836​
98683684507257993647290607629969413804756548237289971803268024744206292691248590​52181004459842150591120249441341728531478105803603371077309182869314710171111683​
91658172688941975871658215212822951848847

2.08969463386289156288276595230574797E-1000

0 seconds