API tools faq
paste
Advertisement
Guest User

Untitled

a guest
May 31st, 2015
315
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.83 KB | None | 0 0
raw download clone embed print report
  1. /* Some experiments for memoization functions on Fibonacci sequence. */
  2. /* This uses the SpiderMonkey JS Shell functions print and dateNow for its output. */
  3. let
  4. fix=
  5. f=>(
  6. (f=>f(f))
  7. (g=>f((...a)=>g(g)(...a)))),
  8. memo=
  9. f=>(
  10. (map=>a=>(
  11. map.has(a)
  12. ?map.get(a)
  13. :map.set(a,f(a)).get(a)))
  14. (new Map)),
  15. fixmemo =
  16. f=>(
  17. (map=>fix(
  18. z=>a=>(
  19. map.has(a)
  20. ?map.get(a)
  21. :map.set(a,f(b=>z(b))(a)).get(a))))
  22. (new Map)),
  23. memocurried=
  24. ((m=>fix(
  25. z=>f=>l=>(
  26. m((0<l?z(f)(l-1):f)))))
  27. (memo)),
  28. time=
  29. f=>(
  30. (n=>[f(),dateNow()-n])
  31. (dateNow())),
  32. memfib=
  33. memo(
  34. n=>(
  35. n===0
  36. ?0
  37. :n===1
  38. ?1
  39. :memfib(n-1)+memfib(n-2))),
  40. memofib=(
  41. memocurried(
  42. n=>(
  43. n===0
  44. ?0
  45. :n===1
  46. ?1
  47. :(memofib(n-1)+memofib(n-2))))
  48. (1)),
  49. fmfib=
  50. fixmemo(
  51. fib=>n=>(
  52. n===0
  53. ?0
  54. :n===1
  55. ?1
  56. :fib(n-1)+fib(n-2))),
  57. Fibonacci=
  58. fix(
  59. fib=>n=>(
  60. n===0
  61. ?0
  62. :n===1
  63. ?1
  64. :fib(n-1)+fib(n-2))),
  65. recfromcorec=(
  66. (f,...a) => fix(
  67. z => n => (
  68. a.length > n
  69. ? a[n]
  70. : (a[a.length]=f(),z(n))))),
  71. cofibs=
  72. (m=0,n=1,o)=>(
  73. ()=>(
  74. [m,n,o]=[n,m+n,m],
  75. o)),
  76. fibco=recfromcorec(cofibs()),
  77. fdfib=(
  78. (f=>n=>(
  79. n<0
  80. ?(()=>{throw 'Fibonacci takes a positive integral argument.'})()
  81. :f(n)[0]))
  82. (fix(
  83. z=>n=>(
  84. n===0
  85. ?[0,1]
  86. :(
  87. (([a,b])=>(
  88. ((c,d)=>(
  89. n%2===0
  90. ?[c,d]
  91. :[d,c+d]))
  92. (a*(b*2-a),a*a+b*b)))
  93. (z(Math.floor(n/2))))))))
  94. ;
  95.  
  96.  
  97.  
  98. print(
  99. 'Unmemoized: fib(0x20):\n\t',
  100. time(()=>Fibonacci(0x20)),'\n\t',
  101. time(()=>Fibonacci(0x20)));
  102. print(
  103. 'Memoized: fib(0x20):\n\t',
  104. time(()=>memfib(0x20)),'\n\t',
  105. time(()=>memfib(0x20)));
  106. print(
  107. 'Curry memoized: fib(0x20):\n\t',
  108. time(()=>memofib(0x20)),'\n\t',
  109. time(()=>memofib(0x20)));
  110. print(
  111. 'Fixmemoized: fib(0x20):\n\t',
  112. time(()=>fmfib(0x20)),'\n\t',
  113. time(()=>fmfib(0x20)));
  114. print(
  115. 'Corecursion: fib(0x20):\n\t',
  116. time(()=>fibco(0x20)),'\n\t',
  117. time(()=>fibco(0x20)));
  118. print(
  119. 'Fast Doubling Fibbonacci algorithm: fib(0x20):\n\t',
  120. time(()=>fdfib(0x20)),'\n\t',
  121. time(()=>fdfib(0x20)));
  122. print(
  123. 'Memoized: fib(0x40):\n\t',
  124. time(()=>memfib(0x40)),'\n\t',
  125. time(()=>memfib(0x40)));
  126. print(
  127. 'Curry memoized: fib(0x40):\n\t',
  128. time(()=>memofib(0x40)),'\n\t',
  129. time(()=>memofib(0x40)));
  130. print(
  131. 'Fixmemoized: fib(0x40):\n\t',
  132. time(()=>fmfib(0x40)),'\n\t',
  133. time(()=>fmfib(0x40)));
  134. print(
  135. 'Corecursion: fib(0x40):\n\t',
  136. time(()=>fibco(0x40)),'\n\t',
  137. time(()=>fibco(0x40)));
  138. print(
  139. 'Fast Doubling Fibbonacci algorithm: fib(0x40):\n\t',
  140. time(()=>fdfib(0x40)),'\n\t',
  141. time(()=>fdfib(0x40)));
  142. print(
  143. 'Memoized: fib(0x400):\n\t',
  144. time(()=>memfib(0x400)),'\n\t',
  145. time(()=>memfib(0x400)));
  146. print(
  147. 'Curry memoized: fib(0x400):\n\t',
  148. time(()=>memofib(0x400)),'\n\t',
  149. time(()=>memofib(0x400)));
  150. print(
  151. 'Fixmemoized: fib(0x400):\n\t',
  152. time(()=>fmfib(0x400)),'\n\t',
  153. time(()=>fmfib(0x400)));
  154. print(
  155. 'Corecursion: fib(0x400):\n\t',
  156. time(()=>fibco(0x400)),'\n\t',
  157. time(()=>fibco(0x400)));
  158. print(
  159. 'Fast Doubling Fibbonacci algorithm: fib(0x400):\n\t',
  160. time(()=>fdfib(0x400)),'\n\t',
  161. time(()=>fdfib(0x400)));
  162. print(
  163. 'Memoized: fib(0x800):\n\t',
  164. time(()=>memfib(0x800)),'\n\t',
  165. time(()=>memfib(0x800)));
  166. print(
  167. 'Curry memoized: fib(0x800):\n\t',
  168. time(()=>memofib(0x800)),'\n\t',
  169. time(()=>memofib(0x800)));
  170. print(
  171. 'Fixmemoized: fib(0x800):\n\t',
  172. time(()=>fmfib(0x800)),'\n\t',
  173. time(()=>fmfib(0x800)));
  174. print(
  175. 'Corecursion: fib(0x800):\n\t',
  176. time(()=>fibco(0x800)),'\n\t',
  177. time(()=>fibco(0x800)));
  178. print(
  179. 'Fast Doubling Fibbonacci algorithm: fib(0x800):\n\t',
  180. time(()=>fdfib(0x800)),'\n\t',
  181. time(()=>fdfib(0x800)));
  182. print(
  183. 'Memoized: fib(0x1000):\n\t',
  184. time(()=>memfib(0x1000)),'\n\t',
  185. time(()=>memfib(0x1000)));
  186. print(
  187. 'Curry memoized: fib(0x1000):\n\t',
  188. time(()=>memofib(0x1000)),'\n\t',
  189. time(()=>memofib(0x1000)))
  190. print(
  191. 'Fixmemoized: fib(0x1000):\n\t',
  192. time(()=>fmfib(0x1000)),'\n\t',
  193. time(()=>fmfib(0x1000)));
  194. print(
  195. 'Corecursion: fib(0x1000):\n\t',
  196. time(()=>fibco(0x1000)),'\n\t',
  197. time(()=>fibco(0x1000)));
  198. print(
  199. 'Fast Doubling Fibbonacci algorithm: fib(0x1000):\n\t',
  200. time(()=>fdfib(0x1000)),'\n\t',
  201. time(()=>fdfib(0x1000)));
  202.  
  203. /* RESULTS:
  204. Unmemoized: fib(0x20):
  205. 2178309,13702.607177734375
  206. 2178309,14864.7529296875
  207. Memoized: fib(0x20):
  208. 2178309,0.52783203125
  209. 2178309,0.008056640625
  210. Curry memoized: fib(0x20):
  211. 2178309,0.2958984375
  212. 2178309,0.0048828125
  213. Fixmemoized: fib(0x20):
  214. 2178309,36.14892578125
  215. 2178309,0.0048828125
  216. Corecursion: fib(0x20):
  217. 2178309,0.6240234375
  218. 2178309,0.0048828125
  219. Fast Doubling Fibbonacci algorithm: fib(0x20):
  220. 2178309,0.281982421875
  221. 2178309,0.575927734375
  222. Memoized: fib(0x40):
  223. 10610209857723,0.310791015625
  224. 10610209857723,0.005859375
  225. Curry memoized: fib(0x40):
  226. 10610209857723,0.154052734375
  227. 10610209857723,0.0048828125
  228. Fixmemoized: fib(0x40):
  229. 10610209857723,0.380126953125
  230. 10610209857723,0.076171875
  231. Corecursion: fib(0x40):
  232. 10610209857723,0.27685546875
  233. 10610209857723,0.006103515625
  234. Fast Doubling Fibbonacci algorithm: fib(0x40):
  235. 10610209857723,0.14306640625
  236. 10610209857723,0.078125
  237. Memoized: fib(0x400):
  238. 4.506699633677816e+213,2.569091796875
  239. 4.506699633677816e+213,0.015869140625
  240. Curry memoized: fib(0x400):
  241. 4.506699633677816e+213,0.67919921875
  242. 4.506699633677816e+213,0.008056640625
  243. Fixmemoized: fib(0x400):
  244. 4.506699633677816e+213,12.121826171875
  245. 4.506699633677816e+213,0.01611328125
  246. Corecursion: fib(0x400):
  247. 4.506699633677816e+213,12.364990234375
  248. 4.506699633677816e+213,0.010986328125
  249. Fast Doubling Fibbonacci algorithm: fib(0x400):
  250. 4.506699633677817e+213,0.1259765625
  251. 4.506699633677817e+213,0.136962890625
  252. Memoized: fib(0x800):
  253. Infinity,0.322998046875
  254. Infinity,0.00390625
  255. Curry memoized: fib(0x800):
  256. Infinity,0.906982421875
  257. Infinity,0.01318359375
  258. Fixmemoized: fib(0x800):
  259. Infinity,6.6689453125
  260. Infinity,0.011962890625
  261. Corecursion: fib(0x800):
  262. Infinity,1.593994140625
  263. Infinity,0.0068359375
  264. Fast Doubling Fibbonacci algorithm: fib(0x800):
  265. Infinity,0.0869140625
  266. Infinity,0.06689453125
  267. Memoized: fib(0x1000):
  268. Infinity,0.658935546875
  269. Infinity,0.006103515625
  270. Curry memoized: fib(0x1000):
  271. Infinity,1.137939453125
  272. Infinity,0.006103515625
  273. Fixmemoized: fib(0x1000):
  274. Infinity,11.991943359375
  275. Infinity,0.012939453125
  276. Corecursion: fib(0x1000):
  277. Infinity,3.60107421875
  278. Infinity,0.012939453125
  279. Fast Doubling Fibbonacci algorithm: fib(0x1000):
  280. NaN,0.10205078125
  281. NaN,0.0791015625
  282. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!