2015F MATH 3600-001 08.26 Newton's method

2286 days ago by calkin

We wish to find numerical approximations to $\sqrt{2}$

A=plot(x^2-2, (x,0,3)) 
       
show(A) 
       
B=plot(4*x-6,(x,0,3),color='red') show(A+B) 
       

Let us zoom in a bit to see that this really does look like a tangent.

C=plot(x^2-2, (x,1.9,2.1)) D=plot(4*x-6,(x,1.9,2.1),color='red') show(C+D) 
       

Where does the line $y=4x-6$ meet the $x$ axis?  That is, for which value of $x$ is $y$ equal to 0?  $x=3/2$.

In general, if we start with a value $x_n$, the tangent line to the point $(x_n, f(x_n))$ will have slope $f'(x_n)$, and will pass through the point $(x_n,f(x_n))$.

Hence its equation will be $y= f'(x_n) x +a$, and $a$ will satisfy $f(x_n)= f'(x_n)x_n + a$, so 

\[ a= f(x_n) - f'(x_n) x_n.\]

This line will hit the $x$ axis when $f'(x_n) x=-a$, that is, when 

\[   x = x_n -\frac{f(x_n)}{f'(x_n)} . \]

We'll call this point $x_{n+1}$.

For the particular function $f(x)=x^2-2$ we have in mind, $f'(x)= 2x$, so

\[  x_{n+1} = x_n -\frac{x_n^2-2}{2x_n}\]

\[ = \frac{x_n}{2} + \frac{1}{x_n}\]

def newton_iterate(x): a=x/2+1/x return(a) 
       
newton_iterate(2) 
       
3/2
3/2
3^2-2*2^2 
       
1
1
newton_iterate(3/2) 
       
17/12
17/12
17^2-2*12^2 
       
1
1
newton_iterate(17/12) 
       
577/408
577/408
577^2-2*408^2 
       
1
1
newton_iterate(577/408) 
       
665857/470832
665857/470832
665857^2-2*470832^2 
       
1
1

It appears to be the case that if the $n$th iterate $x_n=a_n/b_n$, then $a_n^2-2b_n^2=1$.

 \[ \frac{1}{2} \, x + \frac{1}{x} \]

var('x') 
       
x
x
latex(x/2+1/x) 
       
\frac{1}{2} \, x + \frac{1}{x}
\frac{1}{2} \, x + \frac{1}{x}
show(x/2+1/x) 
       
print newton_iterate(2).n() print newton_iterate(3/2).n() print newton_iterate(17/12).n() print newton_iterate(577/408).n() print newton_iterate(665857/470832).n() 
       
1.50000000000000
1.41666666666667
1.41421568627451
1.41421356237469
1.41421356237310
1.50000000000000
1.41666666666667
1.41421568627451
1.41421356237469
1.41421356237310
x=2 for i in range(10): x=newton_iterate(x) print i,x.n() 
       
0 1.50000000000000
1 1.41666666666667
2 1.41421568627451
3 1.41421356237469
4 1.41421356237310
5 1.41421356237310
6 1.41421356237310
7 1.41421356237310
8 1.41421356237310
9 1.41421356237310
0 1.50000000000000
1 1.41666666666667
2 1.41421568627451
3 1.41421356237469
4 1.41421356237310
5 1.41421356237310
6 1.41421356237310
7 1.41421356237310
8 1.41421356237310
9 1.41421356237310
x=2 for i in range(10): x=newton_iterate(x) print i,x.n(digits=20) 
       
0 1.5000000000000000000
1 1.4166666666666666667
2 1.4142156862745098039
3 1.4142135623746899106
4 1.4142135623730950488
5 1.4142135623730950488
6 1.4142135623730950488
7 1.4142135623730950488
8 1.4142135623730950488
9 1.4142135623730950488
0 1.5000000000000000000
1 1.4166666666666666667
2 1.4142156862745098039
3 1.4142135623746899106
4 1.4142135623730950488
5 1.4142135623730950488
6 1.4142135623730950488
7 1.4142135623730950488
8 1.4142135623730950488
9 1.4142135623730950488
x=2 for i in range(10): x=newton_iterate(x) print i,x.n(digits=40) 
       
0 1.500000000000000000000000000000000000000
1 1.416666666666666666666666666666666666667
2 1.414215686274509803921568627450980392157
3 1.414213562374689910626295578890134910117
4 1.414213562373095048801689623502530243615
5 1.414213562373095048801688724209698078570
6 1.414213562373095048801688724209698078570
7 1.414213562373095048801688724209698078570
8 1.414213562373095048801688724209698078570
9 1.414213562373095048801688724209698078570
0 1.500000000000000000000000000000000000000
1 1.416666666666666666666666666666666666667
2 1.414215686274509803921568627450980392157
3 1.414213562374689910626295578890134910117
4 1.414213562373095048801689623502530243615
5 1.414213562373095048801688724209698078570
6 1.414213562373095048801688724209698078570
7 1.414213562373095048801688724209698078570
8 1.414213562373095048801688724209698078570
9 1.414213562373095048801688724209698078570
x=2 for i in range(10): x=newton_iterate(x) print i,x.n(digits=68) 
       
0 1.5000000000000000000000000000000000000000000000000000000000000000000
1 1.4166666666666666666666666666666666666666666666666666666666666666667
2 1.4142156862745098039215686274509803921568627450980392156862745098039
3 1.4142135623746899106262955788901349101165596221157440445849050192001
4 1.4142135623730950488016896235025302436149819257761974284982894986232
5 1.4142135623730950488016887242096980785696718753772340015610131331133
6 1.4142135623730950488016887242096980785696718753769480731766797379907
7 1.4142135623730950488016887242096980785696718753769480731766797379907
8 1.4142135623730950488016887242096980785696718753769480731766797379907
9 1.4142135623730950488016887242096980785696718753769480731766797379907
0 1.5000000000000000000000000000000000000000000000000000000000000000000
1 1.4166666666666666666666666666666666666666666666666666666666666666667
2 1.4142156862745098039215686274509803921568627450980392156862745098039
3 1.4142135623746899106262955788901349101165596221157440445849050192001
4 1.4142135623730950488016896235025302436149819257761974284982894986232
5 1.4142135623730950488016887242096980785696718753772340015610131331133
6 1.4142135623730950488016887242096980785696718753769480731766797379907
7 1.4142135623730950488016887242096980785696718753769480731766797379907
8 1.4142135623730950488016887242096980785696718753769480731766797379907
9 1.4142135623730950488016887242096980785696718753769480731766797379907
x=2 for i in range(20): x=newton_iterate(x) print i,x.n(digits=2000) 
       
WARNING: Output truncated!  
full_output.txt



0
1.5000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000
1
1.4166666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666667
2
1.4142156862745098039215686274509803921568627450980392156862745098039215\
686274509803921568627450980392156862745098039215686274509803921568627450\
980392156862745098039215686274509803921568627450980392156862745098039215\
686274509803921568627450980392156862745098039215686274509803921568627450\
980392156862745098039215686274509803921568627450980392156862745098039215\
686274509803921568627450980392156862745098039215686274509803921568627450\
980392156862745098039215686274509803921568627450980392156862745098039215\
686274509803921568627450980392156862745098039215686274509803921568627450\
980392156862745098039215686274509803921568627450980392156862745098039215\
686274509803921568627450980392156862745098039215686274509803921568627450\
980392156862745098039215686274509803921568627450980392156862745098039215\
686274509803921568627450980392156862745098039215686274509803921568627450\
980392156862745098039215686274509803921568627450980392156862745098039215\
686274509803921568627450980392156862745098039215686274509803921568627450\
980392156862745098039215686274509803921568627450980392156862745098039215\
686274509803921568627450980392156862745098039215686274509803921568627450\
980392156862745098039215686274509803921568627450980392156862745098039215\
686274509803921568627450980392156862745098039215686274509803921568627450\
980392156862745098039215686274509803921568627450980392156862745098039215\
686274509803921568627450980392156862745098039215686274509803921568627450\
980392156862745098039215686274509803921568627450980392156862745098039215\
686274509803921568627450980392156862745098039215686274509803921568627450\
980392156862745098039215686274509803921568627450980392156862745098039215\
686274509803921568627450980392156862745098039215686274509803921568627450\
980392156862745098039215686274509803921568627450980392156862745098039215\
686274509803921568627450980392156862745098039215686274509803921568627450\
980392156862745098039215686274509803921568627450980392156862745098039215\
686274509803921568627450980392156862745098039215686274510
3
1.4142135623746899106262955788901349101165596221157440445849050192000543\
718353892683589900431576443402317599483467563801950589594590002378767798\
280490705814388146939885139497740170591633533829476331260407109117477146\
837937948142861997485302613246338396710503958949264281102388962517415978\
523125021238998198932952730485608454820403031229822951711013694906038671\
967920617120331668195874536989839263261630475413735684915213919189859652\
699901451048356951099330546776769633329935093621504060896455635980562068\
848336561661059571142148367145818466034594080266421993407414959051211472\
457267135623746899106262955788901349101165596221157440445849050192000543\
718353892683589900431576443402317599483467563801950589594590002378767798\
280490705814388146939885139497740170591633533829476331260407109117477146\
837937948142861997485302613246338396710503958949264281102388962517415978\
523125021238998198932952730485608454820403031229822951711013694906038671\
967920617120331668195874536989839263261630475413735684915213919189859652\
699901451048356951099330546776769633329935093621504060896455635980562068\
848336561661059571142148367145818466034594080266421993407414959051211472\
457267135623746899106262955788901349101165596221157440445849050192000543\
718353892683589900431576443402317599483467563801950589594590002378767798\
280490705814388146939885139497740170591633533829476331260407109117477146\
837937948142861997485302613246338396710503958949264281102388962517415978\
523125021238998198932952730485608454820403031229822951711013694906038671\
967920617120331668195874536989839263261630475413735684915213919189859652\
699901451048356951099330546776769633329935093621504060896455635980562068\
848336561661059571142148367145818466034594080266421993407414959051211472\
457267135623746899106262955788901349101165596221157440445849050192000543\
718353892683589900431576443402317599483467563801950589594590002378767798\
280490705814388146939885139497740170591633533829476331260407109117477146\
837937948142861997485302613246338396710503958949264281102
4
1.4142135623730950488016896235025302436149819257761974284982894986231958\
242289236217849418367358303565583143106750594820265773083173200262157783\
022220011129605191773121780900814121327577340130909205357952906146241595\
839698950627958901881012846713609037539941785243738720492533237177771692\
128694642593781865886293232828487039185102132414013985853899895810249191\
643659012636266258062842646075991843832534225417442335179017112225299410\
209548206665024032478555410459858120993074032137180978405521951715690544\
273880756632391146193550180671385332239802773346198169625220657279988434\
015095225495129764347449176739698227703887486654815696030042269596696367\
267049807932196492889365281039725488985820725493968985634817171865670248\
912043201394181519723417414948364871713921555180086431098614940186583591\
193055602281391996374274913493713474378482192568434563593979944203454383\
757678042933494446815832157852929224218825589552708930864615409801992163\
482957841063391001063216600243328073683688452225901208480641935573255502\
884101451580974454265816038492603890730420038862348694596836302995319653\
827433546495680110640871452355846109854215477575484638041111757020623435\
224063517485752375508704521355734403639561362577123338662018805099063992\
748196660784986205995933207786759762110530685740688626638816529085013140\
854307080875811959893003377099397300598802242775170660895703504247635739\
026599441273848334597046469548542063700213435162565135173162861856944547\
561617927923815191360081148251768614658514591845994125733784015073093916\
562072425726464303589134327322866172704949774101318903270964782671055781\
322264600725610614882885469316339317406117673639785892073171311863590168\
367342265635074905619372842293925907768782719490790777347299121574874573\
231173152137036359907757170798482621349970654662360859631235919284241891\
305995106997911804134872950103803812109254135370263745620820172509952729\
985306679888813249959789488832096663975623392060978274242112718238027069\
297213101564271052988532929854583751329839616159385773839
5
1.4142135623730950488016887242096980785696718753772340015610131331132652\
556303399785317871612507104752160483751112618376407188512661681161671621\
012388437834398681429658835007687704614910932258931832849630991506223392\
632878159092813277786538979868580721217647731492814500192417022947217181\
900603455529638446125210083975548948412149449735001953644272311860138925\
411176379829751630513437936591789693543057067828428677221360285957751288\
290660871162016116423633508637413567618595194220018754226180168615405368\
074919485172131970750428856565971232479853036383527834559732549166936392\
048706053544309428706776942298204943106759292501466412645913457281226540\
474057953952095640688020974185824746607391415094289244181294046128400910\
466421960032040430281463005784608194173836315836383172667212259809246136\
451654058147433250941443375791602792846717704429530759848470907873115868\
637473604206790706897671651034802886383180636303108567630314289653089597\
467378581775858402671773117237303676000713147684463812932912392756207132\
877121484077402650827443994448291514319868521995901527811389767397365894\
891299236246034306846011827758742150876076284405909722868816850666630103\
029666296757835035572014331309541189822994156940514352803632213000784991\
154885878106883792884539692184318362060713279232888084969374637245095479\
417539302841246879982932138665283056477704399346034397107022708366104992\
586025970428410618416425907593656047570917490484321619157505908024149271\
230545082030192466834516744441946210446487886245825758459464555363428183\
628677955703723785343879471866270559627417500173947710621627728431713732\
997046093682618774263446521516111198684824355608556786867853020693853786\
030417871038886669580859050380706647301997021727562998434948077530221464\
812486098956770777193637726759057997512792949010602774996277912293908454\
056386930281649381994153500795488814003435267776024642455212689170610315\
546867298385063077163210056793554786117427946324551482532167146932323654\
358158024881950021475033844994890971817691222755710246802
6
1.4142135623730950488016887242096980785696718753769480731766797379907324\
784621070388503875343276416016397857783845578298249912463705876773932799\
692964435297099058203300391173630374124244480380770113378534551996722969\
338209180841198550709847544384006608139779059077241486084310572953336254\
789987301279188900511872748880916039303799225615983460364172902341523850\
600472694397293132700148249065547710266347654439593390710153528011862283\
915322385334215772711972022431678155494845274456738672953414232508972153\
531336374828502785923070827196612467991095067062344435545173194507060557\
143456761117083814042922724788045009115284582749443366407517931891188386\
187567638544954553217597756640187353556383164661233132567286790972259407\
515042952857123968833549003904019562090860694827516620178853047908228988\
964596740530241382544602895735022366006905628283187604964431705680743550\
195488048644558437788910784731238657483237175396259708183232334005059828\
444844340170157993012588307753042264781613973534532761475891876652308372\
692630203346547673093356894007462316575040017126464356580070371414933493\
535385772875460325424897403239258146396643189932929984963732097237539979\
846749744938337608546483201497466941703294351793018506246063052432162177\
996290581645544236180398301663434708256682578340347364556580908830829933\
587804297870669587479702066829307561635921274988511085285107750201706632\
193077119105160755412616918643916675580986072314274243961867946307063224\
498213260422619824231147946527648342224225333374873368267257025236730923\
290205109020122817513478730174568139371510445003505269448518951423823634\
748794761088939129912469807721700731077017912840536384213662530914714407\
144185101519261308619711519552000667610348760871111722568601807429121137\
874774957217795728648772675722558202265395811504195574711878175017969519\
160422347821789010112410794685993005602985178380183244683334502737522822\
863064048208728145568412185803128078878151998001386054561714817673282302\
203298159239026208423551324605024116516052545942389245267
7
1.4142135623730950488016887242096980785696718753769480731766797379907324\
784621070388503875343276415727350138462309122970249248360558507372126441\
214970999358314132226659275055927557999505011527820608668589612436754264\
838852498044502270680618389459459136712765655521341961840596466327404140\
068028165015185988728044719976834090115449759677904499020968618613298346\
908146016510959704367292479776085666780546225582556218766825297963133974\
316439172674074946239391049431865242564232090427704104480965485744071844\
792997489868119590688131608314228368444303620331480130523463406799922629\
335267693463830509455577828822023692499590853560451411089552036807982021\
813599460561062871128897381591612388265897695912536867384711378543585245\
962517718443612818226760054008936841285716595313008721506435271544801268\
081181602717188193056593931077536650278377960182345857690406165598841259\
505680088526949080750130172929071362075659476596518374591003478620014588\
915885511271995690579029075902870391648863121194544995128303767781420414\
479329583486469798756477308099846012826222890891089874038282133151341185\
788156848345159010036720369440514237403925611381953418143044646587587832\
500588279732630212447412082294304857748048529973853941686963741835610133\
405489588440599637123786708062246588084481989901161275560288551238144496\
699860038966594559971215611450760674679469782663003176736860875012049509\
860231915436009689783497104689753767398930185716465186628112529077606047\
051767843928254830279348434828896105715817468603865072043249044114825296\
053351128417427573852487687132469716934447459310846468194626454387538165\
224475804709191173791813883106588691218027634336732751331208064303636481\
776665055356297777437200288027482907962461558550956671431651326612129959\
187820893722339364855111205222428098493926275979674027315421037189805511\
676724719370356455985318012357180541738092579896234937494702573863573466\
770591640444125192770858482485864765217207598468673636136916346927288695\
0050782770348548016210690

...

785696718753769480731766797379907324784621070388503875343276415727350138\
462309122970249248360558507372126441214970999358314132226659275055927557\
999505011527820605714701095599716059702745345968620147285174186408891986\
095523292304843087143214508397626036279952514079896872533965463318088296\
406206152583523950547457502877599617298355752203375318570113543746034084\
988471603868999706990048150305440277903164542478230684929369186215805784\
631115966687130130156185689872372352885092648612494977154218334204285686\
060146824720771435854874155657069677653720226485447015858801620758474922\
657226002085584466521458398893944370926591800311388246468157082630100594\
858704003186480342194897278290641045072636881313739855256117322040245091\
227700226941127573627280495738108967504018369868368450725799364729060762\
996941380475654823728997180326802474420629269124859052181004459842150591\
120249441341728531478105803603371077309182869314710171111683916581726889\
419758716582152128229518488472089694633862891562882765952635140542267653\
239694617511291602408715510135150455381287560052631468017127402653969470\
240300517495318862925631385188163478001569369176881852378684052287837629\
389214300655869568685964595155501644724509836896036887323114389415576651\
040883914292338113206052433629485317049915771756228549741438999188021762\
430965206564211827316726257539594717255934637238632261482742622208671155\
839599926521176252698917540988159348640083457085181472231814204070426509\
056532333398436457865796796519267292399875366617215982578860263363617827\
495994219403777753681426217738799194551397231274066898329989895386728822\
856378697749662519966583525776198939322845344735694794962952168891485492\
538904755828834526096524096542889394538646625744927556381964410316979833\
061852019379384940057156333720548068540575867999670121372239475821426306\
585132217408832382947287617393647467837431960001592188807347857617252211\
867490424977366929207311096369721608933708661156734585334833295254675851\
644710757848602463601
13
1.4142135623730950488016887242096980785696718753769480731766797379907324\
784621070388503875343276415727350138462309122970249248360558507372126441\
214970999358314132226659275055927557999505011527820605714701095599716059\
702745345968620147285174186408891986095523292304843087143214508397626036\
279952514079896872533965463318088296406206152583523950547457502877599617\
298355752203375318570113543746034084988471603868999706990048150305440277\
903164542478230684929369186215805784631115966687130130156185689872372352\
885092648612494977154218334204285686060146824720771435854874155657069677\
653720226485447015858801620758474922657226002085584466521458398893944370\
926591800311388246468157082630100594858704003186480342194897278290641045\
072636881313739855256117322040245091227700226941127573627280495738108967\
504018369868368450725799364729060762996941380475654823728997180326802474\
420629269124859052181004459842150591120249441341728531478105803603371077\
309182869314710171111683916581726889419758716582152128229518488472089694\
633862891562882765952635140542267653239694617511291602408715510135150455\
381287560052631468017127402653969470240300517495318862925631385188163478\
001569369176881852378684052287837629389214300655869568685964595155501644\
724509836896036887323114389415576651040883914292338113206052433629485317\
049915771756228549741438999188021762430965206564211827316726257539594717\
255934637238632261482742622208671155839599926521176252698917540988159348\
640083457085181472231814204070426509056532333398436457865796796519267292\
399875366617215982578860263363617827495994219403777753681426217738799194\
551397231274066898329989895386728822856378697749662519966583525776198939\
322845344735694794962952168891485492538904755828834526096524096542889394\
538646625744927556381964410316979833061852019379384940057156333720548068\
540575867999670121372239475821426306585132217408832382947287617393647467\
837431960001592188807347857617252211867490424977366929207311096369721608\
933708661156734585334833295254675851644710757848602463601
14
1.4142135623730950488016887242096980785696718753769480731766797379907324\
784621070388503875343276415727350138462309122970249248360558507372126441\
214970999358314132226659275055927557999505011527820605714701095599716059\
702745345968620147285174186408891986095523292304843087143214508397626036\
279952514079896872533965463318088296406206152583523950547457502877599617\
298355752203375318570113543746034084988471603868999706990048150305440277\
903164542478230684929369186215805784631115966687130130156185689872372352\
885092648612494977154218334204285686060146824720771435854874155657069677\
653720226485447015858801620758474922657226002085584466521458398893944370\
926591800311388246468157082630100594858704003186480342194897278290641045\
072636881313739855256117322040245091227700226941127573627280495738108967\
504018369868368450725799364729060762996941380475654823728997180326802474\
420629269124859052181004459842150591120249441341728531478105803603371077\
309182869314710171111683916581726889419758716582152128229518488472089694\
633862891562882765952635140542267653239694617511291602408715510135150455\
381287560052631468017127402653969470240300517495318862925631385188163478\
001569369176881852378684052287837629389214300655869568685964595155501644\
724509836896036887323114389415576651040883914292338113206052433629485317\
049915771756228549741438999188021762430965206564211827316726257539594717\
255934637238632261482742622208671155839599926521176252698917540988159348\
640083457085181472231814204070426509056532333398436457865796796519267292\
399875366617215982578860263363617827495994219403777753681426217738799194\
551397231274066898329989895386728822856378697749662519966583525776198939\
322845344735694794962952168891485492538904755828834526096524096542889394\
538646625744927556381964410316979833061852019379384940057156333720548068\
540575867999670121372239475821426306585132217408832382947287617393647467\
837431960001592188807347857617252211867490424977366929207311096369721608\
933708661156734585334833295254675851644710757848602463601
15
1.4142135623730950488016887242096980785696718753769480731766797379907324\
784621070388503875343276415727350138462309122970249248360558507372126441\
214970999358314132226659275055927557999505011527820605714701095599716059\
702745345968620147285174186408891986095523292304843087143214508397626036\
279952514079896872533965463318088296406206152583523950547457502877599617\
298355752203375318570113543746034084988471603868999706990048150305440277\
903164542478230684929369186215805784631115966687130130156185689872372352\
885092648612494977154218334204285686060146824720771435854874155657069677\
653720226485447015858801620758474922657226002085584466521458398893944370\
926591800311388246468157082630100594858704003186480342194897278290641045\
072636881313739855256117322040245091227700226941127573627280495738108967\
504018369868368450725799364729060762996941380475654823728997180326802474\
420629269124859052181004459842150591120249441341728531478105803603371077\
309182869314710171111683916581726889419758716582152128229518488472089694\
633862891562882765952635140542267653239694617511291602408715510135150455\
381287560052631468017127402653969470240300517495318862925631385188163478\
001569369176881852378684052287837629389214300655869568685964595155501644\
724509836896036887323114389415576651040883914292338113206052433629485317\
049915771756228549741438999188021762430965206564211827316726257539594717\
255934637238632261482742622208671155839599926521176252698917540988159348\
640083457085181472231814204070426509056532333398436457865796796519267292\
399875366617215982578860263363617827495994219403777753681426217738799194\
551397231274066898329989895386728822856378697749662519966583525776198939\
322845344735694794962952168891485492538904755828834526096524096542889394\
538646625744927556381964410316979833061852019379384940057156333720548068\
540575867999670121372239475821426306585132217408832382947287617393647467\
837431960001592188807347857617252211867490424977366929207311096369721608\
933708661156734585334833295254675851644710757848602463601
16
1.4142135623730950488016887242096980785696718753769480731766797379907324\
784621070388503875343276415727350138462309122970249248360558507372126441\
214970999358314132226659275055927557999505011527820605714701095599716059\
702745345968620147285174186408891986095523292304843087143214508397626036\
279952514079896872533965463318088296406206152583523950547457502877599617\
298355752203375318570113543746034084988471603868999706990048150305440277\
903164542478230684929369186215805784631115966687130130156185689872372352\
885092648612494977154218334204285686060146824720771435854874155657069677\
653720226485447015858801620758474922657226002085584466521458398893944370\
926591800311388246468157082630100594858704003186480342194897278290641045\
072636881313739855256117322040245091227700226941127573627280495738108967\
504018369868368450725799364729060762996941380475654823728997180326802474\
420629269124859052181004459842150591120249441341728531478105803603371077\
309182869314710171111683916581726889419758716582152128229518488472089694\
633862891562882765952635140542267653239694617511291602408715510135150455\
381287560052631468017127402653969470240300517495318862925631385188163478\
001569369176881852378684052287837629389214300655869568685964595155501644\
724509836896036887323114389415576651040883914292338113206052433629485317\
049915771756228549741438999188021762430965206564211827316726257539594717\
255934637238632261482742622208671155839599926521176252698917540988159348\
640083457085181472231814204070426509056532333398436457865796796519267292\
399875366617215982578860263363617827495994219403777753681426217738799194\
551397231274066898329989895386728822856378697749662519966583525776198939\
322845344735694794962952168891485492538904755828834526096524096542889394\
538646625744927556381964410316979833061852019379384940057156333720548068\
540575867999670121372239475821426306585132217408832382947287617393647467\
837431960001592188807347857617252211867490424977366929207311096369721608\
933708661156734585334833295254675851644710757848602463601
17
1.4142135623730950488016887242096980785696718753769480731766797379907324\
784621070388503875343276415727350138462309122970249248360558507372126441\
214970999358314132226659275055927557999505011527820605714701095599716059\
702745345968620147285174186408891986095523292304843087143214508397626036\
279952514079896872533965463318088296406206152583523950547457502877599617\
298355752203375318570113543746034084988471603868999706990048150305440277\
903164542478230684929369186215805784631115966687130130156185689872372352\
885092648612494977154218334204285686060146824720771435854874155657069677\
653720226485447015858801620758474922657226002085584466521458398893944370\
926591800311388246468157082630100594858704003186480342194897278290641045\
072636881313739855256117322040245091227700226941127573627280495738108967\
504018369868368450725799364729060762996941380475654823728997180326802474\
420629269124859052181004459842150591120249441341728531478105803603371077\
309182869314710171111683916581726889419758716582152128229518488472089694\
633862891562882765952635140542267653239694617511291602408715510135150455\
381287560052631468017127402653969470240300517495318862925631385188163478\
001569369176881852378684052287837629389214300655869568685964595155501644\
724509836896036887323114389415576651040883914292338113206052433629485317\
049915771756228549741438999188021762430965206564211827316726257539594717\
255934637238632261482742622208671155839599926521176252698917540988159348\
640083457085181472231814204070426509056532333398436457865796796519267292\
399875366617215982578860263363617827495994219403777753681426217738799194\
551397231274066898329989895386728822856378697749662519966583525776198939\
322845344735694794962952168891485492538904755828834526096524096542889394\
538646625744927556381964410316979833061852019379384940057156333720548068\
540575867999670121372239475821426306585132217408832382947287617393647467\
837431960001592188807347857617252211867490424977366929207311096369721608\
933708661156734585334833295254675851644710757848602463601
18
1.4142135623730950488016887242096980785696718753769480731766797379907324\
784621070388503875343276415727350138462309122970249248360558507372126441\
214970999358314132226659275055927557999505011527820605714701095599716059\
702745345968620147285174186408891986095523292304843087143214508397626036\
279952514079896872533965463318088296406206152583523950547457502877599617\
298355752203375318570113543746034084988471603868999706990048150305440277\
903164542478230684929369186215805784631115966687130130156185689872372352\
885092648612494977154218334204285686060146824720771435854874155657069677\
653720226485447015858801620758474922657226002085584466521458398893944370\
926591800311388246468157082630100594858704003186480342194897278290641045\
072636881313739855256117322040245091227700226941127573627280495738108967\
504018369868368450725799364729060762996941380475654823728997180326802474\
420629269124859052181004459842150591120249441341728531478105803603371077\
309182869314710171111683916581726889419758716582152128229518488472089694\
633862891562882765952635140542267653239694617511291602408715510135150455\
381287560052631468017127402653969470240300517495318862925631385188163478\
001569369176881852378684052287837629389214300655869568685964595155501644\
724509836896036887323114389415576651040883914292338113206052433629485317\
049915771756228549741438999188021762430965206564211827316726257539594717\
255934637238632261482742622208671155839599926521176252698917540988159348\
640083457085181472231814204070426509056532333398436457865796796519267292\
399875366617215982578860263363617827495994219403777753681426217738799194\
551397231274066898329989895386728822856378697749662519966583525776198939\
322845344735694794962952168891485492538904755828834526096524096542889394\
538646625744927556381964410316979833061852019379384940057156333720548068\
540575867999670121372239475821426306585132217408832382947287617393647467\
837431960001592188807347857617252211867490424977366929207311096369721608\
933708661156734585334833295254675851644710757848602463601
19
1.4142135623730950488016887242096980785696718753769480731766797379907324\
784621070388503875343276415727350138462309122970249248360558507372126441\
214970999358314132226659275055927557999505011527820605714701095599716059\
702745345968620147285174186408891986095523292304843087143214508397626036\
279952514079896872533965463318088296406206152583523950547457502877599617\
298355752203375318570113543746034084988471603868999706990048150305440277\
903164542478230684929369186215805784631115966687130130156185689872372352\
885092648612494977154218334204285686060146824720771435854874155657069677\
653720226485447015858801620758474922657226002085584466521458398893944370\
926591800311388246468157082630100594858704003186480342194897278290641045\
072636881313739855256117322040245091227700226941127573627280495738108967\
504018369868368450725799364729060762996941380475654823728997180326802474\
420629269124859052181004459842150591120249441341728531478105803603371077\
309182869314710171111683916581726889419758716582152128229518488472089694\
633862891562882765952635140542267653239694617511291602408715510135150455\
381287560052631468017127402653969470240300517495318862925631385188163478\
001569369176881852378684052287837629389214300655869568685964595155501644\
724509836896036887323114389415576651040883914292338113206052433629485317\
049915771756228549741438999188021762430965206564211827316726257539594717\
255934637238632261482742622208671155839599926521176252698917540988159348\
640083457085181472231814204070426509056532333398436457865796796519267292\
399875366617215982578860263363617827495994219403777753681426217738799194\
551397231274066898329989895386728822856378697749662519966583525776198939\
322845344735694794962952168891485492538904755828834526096524096542889394\
538646625744927556381964410316979833061852019379384940057156333720548068\
540575867999670121372239475821426306585132217408832382947287617393647467\
837431960001592188807347857617252211867490424977366929207311096369721608\
933708661156734585334833295254675851644710757848602463601
WARNING: Output truncated!  
full_output.txt



0 1.5000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1 1.4166666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666667
2 1.4142156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392156862745098039215686274510
3 1.4142135623746899106262955788901349101165596221157440445849050192000543718353892683589900431576443402317599483467563801950589594590002378767798280490705814388146939885139497740170591633533829476331260407109117477146837937948142861997485302613246338396710503958949264281102388962517415978523125021238998198932952730485608454820403031229822951711013694906038671967920617120331668195874536989839263261630475413735684915213919189859652699901451048356951099330546776769633329935093621504060896455635980562068848336561661059571142148367145818466034594080266421993407414959051211472457267135623746899106262955788901349101165596221157440445849050192000543718353892683589900431576443402317599483467563801950589594590002378767798280490705814388146939885139497740170591633533829476331260407109117477146837937948142861997485302613246338396710503958949264281102388962517415978523125021238998198932952730485608454820403031229822951711013694906038671967920617120331668195874536989839263261630475413735684915213919189859652699901451048356951099330546776769633329935093621504060896455635980562068848336561661059571142148367145818466034594080266421993407414959051211472457267135623746899106262955788901349101165596221157440445849050192000543718353892683589900431576443402317599483467563801950589594590002378767798280490705814388146939885139497740170591633533829476331260407109117477146837937948142861997485302613246338396710503958949264281102388962517415978523125021238998198932952730485608454820403031229822951711013694906038671967920617120331668195874536989839263261630475413735684915213919189859652699901451048356951099330546776769633329935093621504060896455635980562068848336561661059571142148367145818466034594080266421993407414959051211472457267135623746899106262955788901349101165596221157440445849050192000543718353892683589900431576443402317599483467563801950589594590002378767798280490705814388146939885139497740170591633533829476331260407109117477146837937948142861997485302613246338396710503958949264281102
4 1.4142135623730950488016896235025302436149819257761974284982894986231958242289236217849418367358303565583143106750594820265773083173200262157783022220011129605191773121780900814121327577340130909205357952906146241595839698950627958901881012846713609037539941785243738720492533237177771692128694642593781865886293232828487039185102132414013985853899895810249191643659012636266258062842646075991843832534225417442335179017112225299410209548206665024032478555410459858120993074032137180978405521951715690544273880756632391146193550180671385332239802773346198169625220657279988434015095225495129764347449176739698227703887486654815696030042269596696367267049807932196492889365281039725488985820725493968985634817171865670248912043201394181519723417414948364871713921555180086431098614940186583591193055602281391996374274913493713474378482192568434563593979944203454383757678042933494446815832157852929224218825589552708930864615409801992163482957841063391001063216600243328073683688452225901208480641935573255502884101451580974454265816038492603890730420038862348694596836302995319653827433546495680110640871452355846109854215477575484638041111757020623435224063517485752375508704521355734403639561362577123338662018805099063992748196660784986205995933207786759762110530685740688626638816529085013140854307080875811959893003377099397300598802242775170660895703504247635739026599441273848334597046469548542063700213435162565135173162861856944547561617927923815191360081148251768614658514591845994125733784015073093916562072425726464303589134327322866172704949774101318903270964782671055781322264600725610614882885469316339317406117673639785892073171311863590168367342265635074905619372842293925907768782719490790777347299121574874573231173152137036359907757170798482621349970654662360859631235919284241891305995106997911804134872950103803812109254135370263745620820172509952729985306679888813249959789488832096663975623392060978274242112718238027069297213101564271052988532929854583751329839616159385773839
5 1.4142135623730950488016887242096980785696718753772340015610131331132652556303399785317871612507104752160483751112618376407188512661681161671621012388437834398681429658835007687704614910932258931832849630991506223392632878159092813277786538979868580721217647731492814500192417022947217181900603455529638446125210083975548948412149449735001953644272311860138925411176379829751630513437936591789693543057067828428677221360285957751288290660871162016116423633508637413567618595194220018754226180168615405368074919485172131970750428856565971232479853036383527834559732549166936392048706053544309428706776942298204943106759292501466412645913457281226540474057953952095640688020974185824746607391415094289244181294046128400910466421960032040430281463005784608194173836315836383172667212259809246136451654058147433250941443375791602792846717704429530759848470907873115868637473604206790706897671651034802886383180636303108567630314289653089597467378581775858402671773117237303676000713147684463812932912392756207132877121484077402650827443994448291514319868521995901527811389767397365894891299236246034306846011827758742150876076284405909722868816850666630103029666296757835035572014331309541189822994156940514352803632213000784991154885878106883792884539692184318362060713279232888084969374637245095479417539302841246879982932138665283056477704399346034397107022708366104992586025970428410618416425907593656047570917490484321619157505908024149271230545082030192466834516744441946210446487886245825758459464555363428183628677955703723785343879471866270559627417500173947710621627728431713732997046093682618774263446521516111198684824355608556786867853020693853786030417871038886669580859050380706647301997021727562998434948077530221464812486098956770777193637726759057997512792949010602774996277912293908454056386930281649381994153500795488814003435267776024642455212689170610315546867298385063077163210056793554786117427946324551482532167146932323654358158024881950021475033844994890971817691222755710246802
6 1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276416016397857783845578298249912463705876773932799692964435297099058203300391173630374124244480380770113378534551996722969338209180841198550709847544384006608139779059077241486084310572953336254789987301279188900511872748880916039303799225615983460364172902341523850600472694397293132700148249065547710266347654439593390710153528011862283915322385334215772711972022431678155494845274456738672953414232508972153531336374828502785923070827196612467991095067062344435545173194507060557143456761117083814042922724788045009115284582749443366407517931891188386187567638544954553217597756640187353556383164661233132567286790972259407515042952857123968833549003904019562090860694827516620178853047908228988964596740530241382544602895735022366006905628283187604964431705680743550195488048644558437788910784731238657483237175396259708183232334005059828444844340170157993012588307753042264781613973534532761475891876652308372692630203346547673093356894007462316575040017126464356580070371414933493535385772875460325424897403239258146396643189932929984963732097237539979846749744938337608546483201497466941703294351793018506246063052432162177996290581645544236180398301663434708256682578340347364556580908830829933587804297870669587479702066829307561635921274988511085285107750201706632193077119105160755412616918643916675580986072314274243961867946307063224498213260422619824231147946527648342224225333374873368267257025236730923290205109020122817513478730174568139371510445003505269448518951423823634748794761088939129912469807721700731077017912840536384213662530914714407144185101519261308619711519552000667610348760871111722568601807429121137874774957217795728648772675722558202265395811504195574711878175017969519160422347821789010112410794685993005602985178380183244683334502737522822863064048208728145568412185803128078878151998001386054561714817673282302203298159239026208423551324605024116516052545942389245267
7 1.41421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206086685896124367542648388524980445022706806183894594591367127656555213419618405964663274041400680281650151859887280447199768340901154497596779044990209686186132983469081460165109597043672924797760856667805462255825562187668252979631339743164391726740749462393910494318652425642320904277041044809654857440718447929974898681195906881316083142283684443036203314801305234634067999226293352676934638305094555778288220236924995908535604514110895520368079820218135994605610628711288973815916123882658976959125368673847113785435852459625177184436128182267600540089368412857165953130087215064352715448012680811816027171881930565939310775366502783779601823458576904061655988412595056800885269490807501301729290713620756594765965183745910034786200145889158855112719956905790290759028703916488631211945449951283037677814204144793295834864697987564773080998460128262228908910898740382821331513411857881568483451590100367203694405142374039256113819534181430446465875878325005882797326302124474120822943048577480485299738539416869637418356101334054895884405996371237867080622465880844819899011612755602885512381444966998600389665945599712156114507606746794697826630031767368608750120495098602319154360096897834971046897537673989301857164651866281125290776060470517678439282548302793484348288961057158174686038650720432490441148252960533511284174275738524876871324697169344474593108464681946264543875381652244758047091911737918138831065886912180276343367327513312080643036364817766650553562977774372002880274829079624615585509566714316513266121299591878208937223393648551112052224280984939262759796740273154210371898055116767247193703564559853180123571805417380925798962349374947025738635734667705916404441251927708584824858647652172075984686736361369163469272886950050782770348548016210690

...

785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927557999505011527820605714701095599716059702745345968620147285174186408891986095523292304843087143214508397626036279952514079896872533965463318088296406206152583523950547457502877599617298355752203375318570113543746034084988471603868999706990048150305440277903164542478230684929369186215805784631115966687130130156185689872372352885092648612494977154218334204285686060146824720771435854874155657069677653720226485447015858801620758474922657226002085584466521458398893944370926591800311388246468157082630100594858704003186480342194897278290641045072636881313739855256117322040245091227700226941127573627280495738108967504018369868368450725799364729060762996941380475654823728997180326802474420629269124859052181004459842150591120249441341728531478105803603371077309182869314710171111683916581726889419758716582152128229518488472089694633862891562882765952635140542267653239694617511291602408715510135150455381287560052631468017127402653969470240300517495318862925631385188163478001569369176881852378684052287837629389214300655869568685964595155501644724509836896036887323114389415576651040883914292338113206052433629485317049915771756228549741438999188021762430965206564211827316726257539594717255934637238632261482742622208671155839599926521176252698917540988159348640083457085181472231814204070426509056532333398436457865796796519267292399875366617215982578860263363617827495994219403777753681426217738799194551397231274066898329989895386728822856378697749662519966583525776198939322845344735694794962952168891485492538904755828834526096524096542889394538646625744927556381964410316979833061852019379384940057156333720548068540575867999670121372239475821426306585132217408832382947287617393647467837431960001592188807347857617252211867490424977366929207311096369721608933708661156734585334833295254675851644710757848602463601
13 1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927557999505011527820605714701095599716059702745345968620147285174186408891986095523292304843087143214508397626036279952514079896872533965463318088296406206152583523950547457502877599617298355752203375318570113543746034084988471603868999706990048150305440277903164542478230684929369186215805784631115966687130130156185689872372352885092648612494977154218334204285686060146824720771435854874155657069677653720226485447015858801620758474922657226002085584466521458398893944370926591800311388246468157082630100594858704003186480342194897278290641045072636881313739855256117322040245091227700226941127573627280495738108967504018369868368450725799364729060762996941380475654823728997180326802474420629269124859052181004459842150591120249441341728531478105803603371077309182869314710171111683916581726889419758716582152128229518488472089694633862891562882765952635140542267653239694617511291602408715510135150455381287560052631468017127402653969470240300517495318862925631385188163478001569369176881852378684052287837629389214300655869568685964595155501644724509836896036887323114389415576651040883914292338113206052433629485317049915771756228549741438999188021762430965206564211827316726257539594717255934637238632261482742622208671155839599926521176252698917540988159348640083457085181472231814204070426509056532333398436457865796796519267292399875366617215982578860263363617827495994219403777753681426217738799194551397231274066898329989895386728822856378697749662519966583525776198939322845344735694794962952168891485492538904755828834526096524096542889394538646625744927556381964410316979833061852019379384940057156333720548068540575867999670121372239475821426306585132217408832382947287617393647467837431960001592188807347857617252211867490424977366929207311096369721608933708661156734585334833295254675851644710757848602463601
14 1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927557999505011527820605714701095599716059702745345968620147285174186408891986095523292304843087143214508397626036279952514079896872533965463318088296406206152583523950547457502877599617298355752203375318570113543746034084988471603868999706990048150305440277903164542478230684929369186215805784631115966687130130156185689872372352885092648612494977154218334204285686060146824720771435854874155657069677653720226485447015858801620758474922657226002085584466521458398893944370926591800311388246468157082630100594858704003186480342194897278290641045072636881313739855256117322040245091227700226941127573627280495738108967504018369868368450725799364729060762996941380475654823728997180326802474420629269124859052181004459842150591120249441341728531478105803603371077309182869314710171111683916581726889419758716582152128229518488472089694633862891562882765952635140542267653239694617511291602408715510135150455381287560052631468017127402653969470240300517495318862925631385188163478001569369176881852378684052287837629389214300655869568685964595155501644724509836896036887323114389415576651040883914292338113206052433629485317049915771756228549741438999188021762430965206564211827316726257539594717255934637238632261482742622208671155839599926521176252698917540988159348640083457085181472231814204070426509056532333398436457865796796519267292399875366617215982578860263363617827495994219403777753681426217738799194551397231274066898329989895386728822856378697749662519966583525776198939322845344735694794962952168891485492538904755828834526096524096542889394538646625744927556381964410316979833061852019379384940057156333720548068540575867999670121372239475821426306585132217408832382947287617393647467837431960001592188807347857617252211867490424977366929207311096369721608933708661156734585334833295254675851644710757848602463601
15 1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927557999505011527820605714701095599716059702745345968620147285174186408891986095523292304843087143214508397626036279952514079896872533965463318088296406206152583523950547457502877599617298355752203375318570113543746034084988471603868999706990048150305440277903164542478230684929369186215805784631115966687130130156185689872372352885092648612494977154218334204285686060146824720771435854874155657069677653720226485447015858801620758474922657226002085584466521458398893944370926591800311388246468157082630100594858704003186480342194897278290641045072636881313739855256117322040245091227700226941127573627280495738108967504018369868368450725799364729060762996941380475654823728997180326802474420629269124859052181004459842150591120249441341728531478105803603371077309182869314710171111683916581726889419758716582152128229518488472089694633862891562882765952635140542267653239694617511291602408715510135150455381287560052631468017127402653969470240300517495318862925631385188163478001569369176881852378684052287837629389214300655869568685964595155501644724509836896036887323114389415576651040883914292338113206052433629485317049915771756228549741438999188021762430965206564211827316726257539594717255934637238632261482742622208671155839599926521176252698917540988159348640083457085181472231814204070426509056532333398436457865796796519267292399875366617215982578860263363617827495994219403777753681426217738799194551397231274066898329989895386728822856378697749662519966583525776198939322845344735694794962952168891485492538904755828834526096524096542889394538646625744927556381964410316979833061852019379384940057156333720548068540575867999670121372239475821426306585132217408832382947287617393647467837431960001592188807347857617252211867490424977366929207311096369721608933708661156734585334833295254675851644710757848602463601
16 1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927557999505011527820605714701095599716059702745345968620147285174186408891986095523292304843087143214508397626036279952514079896872533965463318088296406206152583523950547457502877599617298355752203375318570113543746034084988471603868999706990048150305440277903164542478230684929369186215805784631115966687130130156185689872372352885092648612494977154218334204285686060146824720771435854874155657069677653720226485447015858801620758474922657226002085584466521458398893944370926591800311388246468157082630100594858704003186480342194897278290641045072636881313739855256117322040245091227700226941127573627280495738108967504018369868368450725799364729060762996941380475654823728997180326802474420629269124859052181004459842150591120249441341728531478105803603371077309182869314710171111683916581726889419758716582152128229518488472089694633862891562882765952635140542267653239694617511291602408715510135150455381287560052631468017127402653969470240300517495318862925631385188163478001569369176881852378684052287837629389214300655869568685964595155501644724509836896036887323114389415576651040883914292338113206052433629485317049915771756228549741438999188021762430965206564211827316726257539594717255934637238632261482742622208671155839599926521176252698917540988159348640083457085181472231814204070426509056532333398436457865796796519267292399875366617215982578860263363617827495994219403777753681426217738799194551397231274066898329989895386728822856378697749662519966583525776198939322845344735694794962952168891485492538904755828834526096524096542889394538646625744927556381964410316979833061852019379384940057156333720548068540575867999670121372239475821426306585132217408832382947287617393647467837431960001592188807347857617252211867490424977366929207311096369721608933708661156734585334833295254675851644710757848602463601
17 1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927557999505011527820605714701095599716059702745345968620147285174186408891986095523292304843087143214508397626036279952514079896872533965463318088296406206152583523950547457502877599617298355752203375318570113543746034084988471603868999706990048150305440277903164542478230684929369186215805784631115966687130130156185689872372352885092648612494977154218334204285686060146824720771435854874155657069677653720226485447015858801620758474922657226002085584466521458398893944370926591800311388246468157082630100594858704003186480342194897278290641045072636881313739855256117322040245091227700226941127573627280495738108967504018369868368450725799364729060762996941380475654823728997180326802474420629269124859052181004459842150591120249441341728531478105803603371077309182869314710171111683916581726889419758716582152128229518488472089694633862891562882765952635140542267653239694617511291602408715510135150455381287560052631468017127402653969470240300517495318862925631385188163478001569369176881852378684052287837629389214300655869568685964595155501644724509836896036887323114389415576651040883914292338113206052433629485317049915771756228549741438999188021762430965206564211827316726257539594717255934637238632261482742622208671155839599926521176252698917540988159348640083457085181472231814204070426509056532333398436457865796796519267292399875366617215982578860263363617827495994219403777753681426217738799194551397231274066898329989895386728822856378697749662519966583525776198939322845344735694794962952168891485492538904755828834526096524096542889394538646625744927556381964410316979833061852019379384940057156333720548068540575867999670121372239475821426306585132217408832382947287617393647467837431960001592188807347857617252211867490424977366929207311096369721608933708661156734585334833295254675851644710757848602463601
18 1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927557999505011527820605714701095599716059702745345968620147285174186408891986095523292304843087143214508397626036279952514079896872533965463318088296406206152583523950547457502877599617298355752203375318570113543746034084988471603868999706990048150305440277903164542478230684929369186215805784631115966687130130156185689872372352885092648612494977154218334204285686060146824720771435854874155657069677653720226485447015858801620758474922657226002085584466521458398893944370926591800311388246468157082630100594858704003186480342194897278290641045072636881313739855256117322040245091227700226941127573627280495738108967504018369868368450725799364729060762996941380475654823728997180326802474420629269124859052181004459842150591120249441341728531478105803603371077309182869314710171111683916581726889419758716582152128229518488472089694633862891562882765952635140542267653239694617511291602408715510135150455381287560052631468017127402653969470240300517495318862925631385188163478001569369176881852378684052287837629389214300655869568685964595155501644724509836896036887323114389415576651040883914292338113206052433629485317049915771756228549741438999188021762430965206564211827316726257539594717255934637238632261482742622208671155839599926521176252698917540988159348640083457085181472231814204070426509056532333398436457865796796519267292399875366617215982578860263363617827495994219403777753681426217738799194551397231274066898329989895386728822856378697749662519966583525776198939322845344735694794962952168891485492538904755828834526096524096542889394538646625744927556381964410316979833061852019379384940057156333720548068540575867999670121372239475821426306585132217408832382947287617393647467837431960001592188807347857617252211867490424977366929207311096369721608933708661156734585334833295254675851644710757848602463601
19 1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927557999505011527820605714701095599716059702745345968620147285174186408891986095523292304843087143214508397626036279952514079896872533965463318088296406206152583523950547457502877599617298355752203375318570113543746034084988471603868999706990048150305440277903164542478230684929369186215805784631115966687130130156185689872372352885092648612494977154218334204285686060146824720771435854874155657069677653720226485447015858801620758474922657226002085584466521458398893944370926591800311388246468157082630100594858704003186480342194897278290641045072636881313739855256117322040245091227700226941127573627280495738108967504018369868368450725799364729060762996941380475654823728997180326802474420629269124859052181004459842150591120249441341728531478105803603371077309182869314710171111683916581726889419758716582152128229518488472089694633862891562882765952635140542267653239694617511291602408715510135150455381287560052631468017127402653969470240300517495318862925631385188163478001569369176881852378684052287837629389214300655869568685964595155501644724509836896036887323114389415576651040883914292338113206052433629485317049915771756228549741438999188021762430965206564211827316726257539594717255934637238632261482742622208671155839599926521176252698917540988159348640083457085181472231814204070426509056532333398436457865796796519267292399875366617215982578860263363617827495994219403777753681426217738799194551397231274066898329989895386728822856378697749662519966583525776198939322845344735694794962952168891485492538904755828834526096524096542889394538646625744927556381964410316979833061852019379384940057156333720548068540575867999670121372239475821426306585132217408832382947287617393647467837431960001592188807347857617252211867490424977366929207311096369721608933708661156734585334833295254675851644710757848602463601
def error_estimate(e): return(sqrt(2)*(1+e)/2 + 1/sqrt(2)/(1+e)-sqrt(2)) 
       
plot(error_estimate(e),(e,-.1,.1)) 
       
 
       
continued_fraction(3/2) 
       
continued_fraction(17/12) 
       
continued_fraction(577/408)