Jump to content
  • Advertisement
Sign in to follow this  
  • entries
    14
  • comments
    15
  • views
    10613

Thinking Functionally

Sign in to follow this  
Ceoddyn

320 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.5
1: 7.25
2: 5.349137931034482
3: 5.011394106532552
4: 5.000012953048684
5.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.0
1: 6116306.666666666
2: 5825053.968253967
3: 5547670.4459561585
4: 5283495.662815389
5: 5031900.631252751
6: 4792286.31547881
7: 4564082.205217914
8: 4346744.957350394
9: 4139757.10223847
10: 3942625.811655686
11: 3754881.7253863676
12: 3576077.8337013023
13: 3405788.4130488588
14: 3243608.0124274846
15: 3089150.4880261756
16: 2942048.083834453
17: 2801950.556032812
18: 2668524.3390788687
19: 2541451.7515036846
20: 2420430.239527318
21: 2305171.6566926837
22: 2195401.5778025556
23: 2090858.6455262434
24: 1991293.9481202317
25: 1896470.426781173
26: 1806162.3112201646
27: 1720154.5821144425
28: 1638242.4591566117
29: 1560230.9134824872
30: 1485934.2033166543
31: 1415175.4317301468
32: 1347786.1254572824
33: 1283605.8337688402
34: 1222481.7464465143
35: 1164268.3299490612
36: 1108826.9809038676
37: 1056025.6960989216
38: 1005738.7581894491
39: 957846.4363709039
40: 912234.7013056226
41: 868794.9536244024
42: 827423.7653565736
43: 788022.6336729273
44: 750497.7463551689
45: 714759.7584334941
46: 680723.5794604706
47: 648308.1709147338
48: 617436.3532521274
49: 588034.6221448832
50: 560032.9734713172
51: 533364.7366393497
52: 507966.41584699973
53: 483777.5389019045
54: 460740.513239909
55: 438800.4887999134
56: 417905.22742848896
57: 398004.9785033228
58: 379052.36047935503
59: 361002.2480755762
60: 343811.66483388207
61: 327439.6807941734
62: 311847.3150420699
63: 296997.4428972094
64: 282854.70752115175
65: 269385.4357344302
66: 256557.5578423145
67: 244340.53127839477
68: 232705.26788418548
69: 221624.0646516052
70: 211070.53776343353
71: 201019.5597746986
72: 191447.19978542722
73: 182330.6664623116
74: 173648.2537736301
75: 165379.28930821913
76: 157504.08505544678
77: 150003.8905289969
78: 142860.8481228542
79: 136057.9505931945
80: 129579.00056494711
81: 123408.57196661629
82: 117531.97330153933
83: 111935.21266813269
84: 106604.96444584065
85: 101528.53756746728
86: 96693.8453023498
87: 92089.37647842837
88: 87704.16807469368
89: 83527.77911875588
90: 79550.26582738655
91: 75762.15793084433
92: 72154.43612461365
93: 68718.51059487014
94: 65446.20056654298
95: 62329.71482527903
96: 59361.633166932406
97: 56534.88873041181
98: 53842.751171820775
99: 51278.8106398293
100: 48836.962514123145
101: 46511.39287059347
102: 44296.56463866044
103: 42187.20441777185
104: 40178.28992168747
105: 38265.038020654734
106: 36442.8933530045
107: 34707.51747905191
108: 33054.778551478004
109: 31480.741477598098
110: 29981.658550093427
111: 28553.960523898502
112: 27194.248117998573
113: 25899.283921903403
114: 24665.98468752705
115: 23491.413988120996
116: 22372.7752267819
117: 21307.404977887523
118: 20292.766645607164
119: 19326.444424387773
120: 18406.13754703597
121: 17529.65480670092
122: 16694.90933971516
123: 15899.913656871578
124: 15142.774911306265
125: 14421.690391720253
126: 13734.943230209763
127: 13080.898314485486
128: 12457.998394748081
129: 11864.760375950553
130: 11299.771786619573
131: 10761.687415828164
132: 10249.226110312537
133: 9761.167724107178
134: 9296.350213435406
135: 8853.66686993848
136: 8432.063685655696
137: 8030.536843481615
138: 7648.130327125347
139: 7283.933644881283
140: 6937.079661791698
141: 6606.742535039712
142: 6292.135747656867
143: 5992.510235863682
144: 5707.152605584459
145: 5435.3834338899605
146: 5176.555651323772
147: 4930.053001260734
148: 4695.288572629271
149: 4471.703402504067
150: 4258.765145241968
151: 4055.96680499235
152: 3862.8255285641426
153: 3678.8814557753735
154: 3503.696624547975
155: 3336.8539281409285
156: 3177.956122038979
157: 3026.6248781323607
158: 2882.4998839355817
159: 2745.2379847005536
160: 2614.5123663814798
161: 2490.011777506171
162: 2371.4397881011146
163: 2258.514083905823
164: 2150.9657941960218
165: 2048.5388516152584
166: 1950.9893824907222
167: 1858.0851261816401
168: 1769.6048820777526
169: 1685.337982931193
170: 1605.0837932678028
171: 1528.6512316836215
172: 1455.8583158891634
173: 1386.5317294182507
174: 1320.5064089697626
175: 1257.6251513997738
176: 1197.7382394283559
177: 1140.7030851698628
178: 1086.3838906379644
179: 1034.651324417109
180: 985.38221373058
181: 938.4592511719809
182: 893.7707154018866
183: 851.2102051446539
184: 810.6763858520512
185: 772.0727484305249
186: 735.3073794576427
187: 700.292742340612
188: 666.9454688958209
189: 635.1861608531627
190: 604.9392008125359
191: 576.1325722024151
192: 548.6976878118238
193: 522.5692264874513
194: 497.68497760709647
195: 473.9856929591395
196: 451.4149456753709
197: 429.91899588130565
198: 409.4466627441006
199: 389.9492026134291
200: 371.3801929651706
201: 353.695421871591
202: 336.8527827348486
203: 320.8121740331891
204: 305.5354038411324
205: 290.98609889631655
206: 277.1296179964919
207: 263.9329695204685
208: 251.36473287663665
209: 239.3949836920349
210: 227.9952225638428
211: 217.1383072036598
212: 206.7983878130093
213: 196.95084553619935
214: 187.57223384399938
215: 178.64022270857083
216: 170.13354543673412
217: 162.03194803498488
218: 154.3161409856999
219: 146.96775331971418
220: 139.96928887591824
221: 133.30408464373164
222: 126.95627108926821
223: 120.91073437073163
224: 115.15308035307775
225: 109.66960033626452
226: 104.44723841549
227: 99.47356039570477
228: 94.73672418638549
229: 90.2254516060814
230: 85.92900152960134
231: 81.83714431390604
232: 77.94013744181527
233: 74.22870232553835
234: 70.69400221479842
235: 67.32762115695087
236: 64.12154395900082
237: 61.068137103810294
238: 58.16013057505742
239: 55.390600547673735
240: 52.75295290254642
241: 50.24090752623468
242: 47.84848335831874
243: 45.569984150779746
244: 43.39998490550452
245: 41.33331895762335
246: 39.365065673927
247: 37.49053873707333
248: 35.70527498768888
249: 34.005023797798934
250: 32.3857369502847
251: 30.843559000271142
252: 29.374818095496323
253: 27.976017233806022
254: 26.643825936958113
255: 25.375072320912487
256: 24.16673554372618
257: 23.01593861307255
258: 21.919941536259568
259: 20.876134796437682
260: 19.882033139464458
261: 18.935269656632816
262: 18.03359014917411
263: 17.174847761118198
264: 16.356997867731618
265: 15.578093207363445
266: 14.836279245108043
267: 14.129789757245755
268: 13.456942625948336
269: 12.816135834236508
270: 12.205843651653817
271: 11.624613001575062
272: 11.071060001500058
273: 10.543866668095294
274: 10.041777779138377
275: 9.563597884893698
276: 9.108188461803536
277: 8.674465201717693
278: 8.261395430207433
279: 7.86799564781688
280: 7.493329188397769
281: 7.136503988952219
282: 6.796670465673989
283: 6.473019491131907
284: 6.1647804677813465
285: 5.871219493222397
286: 5.591637612850939
287: 5.325369155781161
288: 5.0717801501805955
289: 4.8302668145184
290: 4.6002541218609245
291: 4.381194435723326
292: 4.1725662193424515
293: 3.9738728288645904
294: 3.784641423571073
295: 3.6044220860537064
296: 3.4327874036355905
297: 3.269333182232988
298: 3.113682076939584
299: 2.965494870717574
300: 2.8245019073472775
301: 2.6905874849393436
302: 2.5640114729390593
303: 2.4459716140163272
304: 2.339907021423322
305: 2.2537477575579974
306: 2.199930047543687
307: 2.1819299313374882
308: 2.18028084576654
309: 2.1802682525677963
310: 2.1802682518403618
2.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
Sign in to follow this  


0 Comments


Recommended Comments

There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!