• entries
14
15
• views
10690

# Thinking Functionally

355 views

I've been reading SICP and watching UC Berkeley's videos on programming paradigms. It uses Scheme and starts with functional programming, something I've been finding very enlightening compared to the C++ stuff I've done (and fun!)

Just now I wrote an Nth root solver:

; find nth power(define (nth x power)  (if (= power 1)      x      (* x (nth x (- power 1))))); find roots(define (rootsolve actual guess prec power count)  (define newguess (* (/ 1 power) (+ (* (- power 1) guess) (/ actual (nth guess (- power 1))))))  (if (> prec (abs (- actual (nth guess power))))      guess      (rootsolve actual newguess prec power (+ count 1))))    ; less precise root(define (root x power)  (rootsolve x (/ x 2.0) 0.001 power 0)); more precise root(define (root-prec x power)  (rootsolve x (/ x 2.0) 0.00000001 power 0))

And (root 25 2) reasonably solves as such:
> (root 25 2)0: 12.51: 7.252: 5.3491379310344823: 5.0113941065325524: 5.0000129530486845.000012953048684>

I just wiki'd an algorithm for nth roots, but I believe its a derivative of newton's method. The problem I'm having with it is for rather large values, say, (root 12844244 21), I'm starting at very poor guesses:

> (root 12844244 21)0: 6422122.01: 6116306.6666666662: 5825053.9682539673: 5547670.44595615854: 5283495.6628153895: 5031900.6312527516: 4792286.315478817: 4564082.2052179148: 4346744.9573503949: 4139757.1022384710: 3942625.81165568611: 3754881.725386367612: 3576077.833701302313: 3405788.413048858814: 3243608.012427484615: 3089150.488026175616: 2942048.08383445317: 2801950.55603281218: 2668524.339078868719: 2541451.751503684620: 2420430.23952731821: 2305171.656692683722: 2195401.577802555623: 2090858.645526243424: 1991293.948120231725: 1896470.42678117326: 1806162.311220164627: 1720154.582114442528: 1638242.459156611729: 1560230.913482487230: 1485934.203316654331: 1415175.431730146832: 1347786.125457282433: 1283605.833768840234: 1222481.746446514335: 1164268.329949061236: 1108826.980903867637: 1056025.696098921638: 1005738.758189449139: 957846.436370903940: 912234.701305622641: 868794.953624402442: 827423.765356573643: 788022.633672927344: 750497.746355168945: 714759.758433494146: 680723.579460470647: 648308.170914733848: 617436.353252127449: 588034.622144883250: 560032.973471317251: 533364.736639349752: 507966.4158469997353: 483777.538901904554: 460740.51323990955: 438800.488799913456: 417905.2274284889657: 398004.978503322858: 379052.3604793550359: 361002.248075576260: 343811.6648338820761: 327439.680794173462: 311847.315042069963: 296997.442897209464: 282854.7075211517565: 269385.435734430266: 256557.557842314567: 244340.5312783947768: 232705.2678841854869: 221624.064651605270: 211070.5377634335371: 201019.559774698672: 191447.1997854272273: 182330.666462311674: 173648.253773630175: 165379.2893082191376: 157504.0850554467877: 150003.890528996978: 142860.848122854279: 136057.950593194580: 129579.0005649471181: 123408.5719666162982: 117531.9733015393383: 111935.2126681326984: 106604.9644458406585: 101528.5375674672886: 96693.845302349887: 92089.3764784283788: 87704.1680746936889: 83527.7791187558890: 79550.2658273865591: 75762.1579308443392: 72154.4361246136593: 68718.5105948701494: 65446.2005665429895: 62329.7148252790396: 59361.63316693240697: 56534.8887304118198: 53842.75117182077599: 51278.8106398293100: 48836.962514123145101: 46511.39287059347102: 44296.56463866044103: 42187.20441777185104: 40178.28992168747105: 38265.038020654734106: 36442.8933530045107: 34707.51747905191108: 33054.778551478004109: 31480.741477598098110: 29981.658550093427111: 28553.960523898502112: 27194.248117998573113: 25899.283921903403114: 24665.98468752705115: 23491.413988120996116: 22372.7752267819117: 21307.404977887523118: 20292.766645607164119: 19326.444424387773120: 18406.13754703597121: 17529.65480670092122: 16694.90933971516123: 15899.913656871578124: 15142.774911306265125: 14421.690391720253126: 13734.943230209763127: 13080.898314485486128: 12457.998394748081129: 11864.760375950553130: 11299.771786619573131: 10761.687415828164132: 10249.226110312537133: 9761.167724107178134: 9296.350213435406135: 8853.66686993848136: 8432.063685655696137: 8030.536843481615138: 7648.130327125347139: 7283.933644881283140: 6937.079661791698141: 6606.742535039712142: 6292.135747656867143: 5992.510235863682144: 5707.152605584459145: 5435.3834338899605146: 5176.555651323772147: 4930.053001260734148: 4695.288572629271149: 4471.703402504067150: 4258.765145241968151: 4055.96680499235152: 3862.8255285641426153: 3678.8814557753735154: 3503.696624547975155: 3336.8539281409285156: 3177.956122038979157: 3026.6248781323607158: 2882.4998839355817159: 2745.2379847005536160: 2614.5123663814798161: 2490.011777506171162: 2371.4397881011146163: 2258.514083905823164: 2150.9657941960218165: 2048.5388516152584166: 1950.9893824907222167: 1858.0851261816401168: 1769.6048820777526169: 1685.337982931193170: 1605.0837932678028171: 1528.6512316836215172: 1455.8583158891634173: 1386.5317294182507174: 1320.5064089697626175: 1257.6251513997738176: 1197.7382394283559177: 1140.7030851698628178: 1086.3838906379644179: 1034.651324417109180: 985.38221373058181: 938.4592511719809182: 893.7707154018866183: 851.2102051446539184: 810.6763858520512185: 772.0727484305249186: 735.3073794576427187: 700.292742340612188: 666.9454688958209189: 635.1861608531627190: 604.9392008125359191: 576.1325722024151192: 548.6976878118238193: 522.5692264874513194: 497.68497760709647195: 473.9856929591395196: 451.4149456753709197: 429.91899588130565198: 409.4466627441006199: 389.9492026134291200: 371.3801929651706201: 353.695421871591202: 336.8527827348486203: 320.8121740331891204: 305.5354038411324205: 290.98609889631655206: 277.1296179964919207: 263.9329695204685208: 251.36473287663665209: 239.3949836920349210: 227.9952225638428211: 217.1383072036598212: 206.7983878130093213: 196.95084553619935214: 187.57223384399938215: 178.64022270857083216: 170.13354543673412217: 162.03194803498488218: 154.3161409856999219: 146.96775331971418220: 139.96928887591824221: 133.30408464373164222: 126.95627108926821223: 120.91073437073163224: 115.15308035307775225: 109.66960033626452226: 104.44723841549227: 99.47356039570477228: 94.73672418638549229: 90.2254516060814230: 85.92900152960134231: 81.83714431390604232: 77.94013744181527233: 74.22870232553835234: 70.69400221479842235: 67.32762115695087236: 64.12154395900082237: 61.068137103810294238: 58.16013057505742239: 55.390600547673735240: 52.75295290254642241: 50.24090752623468242: 47.84848335831874243: 45.569984150779746244: 43.39998490550452245: 41.33331895762335246: 39.365065673927247: 37.49053873707333248: 35.70527498768888249: 34.005023797798934250: 32.3857369502847251: 30.843559000271142252: 29.374818095496323253: 27.976017233806022254: 26.643825936958113255: 25.375072320912487256: 24.16673554372618257: 23.01593861307255258: 21.919941536259568259: 20.876134796437682260: 19.882033139464458261: 18.935269656632816262: 18.03359014917411263: 17.174847761118198264: 16.356997867731618265: 15.578093207363445266: 14.836279245108043267: 14.129789757245755268: 13.456942625948336269: 12.816135834236508270: 12.205843651653817271: 11.624613001575062272: 11.071060001500058273: 10.543866668095294274: 10.041777779138377275: 9.563597884893698276: 9.108188461803536277: 8.674465201717693278: 8.261395430207433279: 7.86799564781688280: 7.493329188397769281: 7.136503988952219282: 6.796670465673989283: 6.473019491131907284: 6.1647804677813465285: 5.871219493222397286: 5.591637612850939287: 5.325369155781161288: 5.0717801501805955289: 4.8302668145184290: 4.6002541218609245291: 4.381194435723326292: 4.1725662193424515293: 3.9738728288645904294: 3.784641423571073295: 3.6044220860537064296: 3.4327874036355905297: 3.269333182232988298: 3.113682076939584299: 2.965494870717574300: 2.8245019073472775301: 2.6905874849393436302: 2.5640114729390593303: 2.4459716140163272304: 2.339907021423322305: 2.2537477575579974306: 2.199930047543687307: 2.1819299313374882308: 2.18028084576654309: 2.1802682525677963310: 2.18026825184036182.1802682518403618>

is there a better function to find a decent place to start checking than dividing the input in half? Or some other fun things to do in Scheme?

p.s. <3 parenthesis h8 college apps kkthx bbai

There are no comments to display.

## Create an account

Register a new account