Skip to content

Instantly share code, notes, and snippets.

@joewiz
Forked from apb2006/fib.xq
Last active October 10, 2020 16:51
Show Gist options
  • Save joewiz/70a7ce6b50af2ca7bfc96dc59bb1e482 to your computer and use it in GitHub Desktop.
Save joewiz/70a7ce6b50af2ca7bfc96dc59bb1e482 to your computer and use it in GitHub Desktop.
XQuery tail recursive Fibonacci function, with timing, for eXist-db
xquery version "3.1";
(: forked from https://gist.github.com/apb2006/4eef5889017be4a50685a467b2754d27
: with tests returned in the style of https://so.nwalsh.com/2020/10/09-fib :)
declare function local:fib($n as xs:integer, $a as xs:integer, $b as xs:integer){
switch ($n)
case 0 return $a
case 1 return $b
default return local:fib($n - 1, $b, $a + $b)
};
declare function local:fib($n as xs:integer){
local:fib($n,0,1)
};
let $results :=
for $n in (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 20, 30, 40, 50, 60, 70, 80, 90)
let $start-time := util:system-time()
let $fib := local:fib($n)
return
$n || " = " || $fib || ", " || (util:system-time() - $start-time) div xs:dayTimeDuration("PT1S") || "s"
return
string-join($results, "
")
1 = 1, 0s
2 = 1, 0s
3 = 2, 0s
4 = 3, 0s
5 = 5, 0s
6 = 8, 0s
7 = 13, 0s
8 = 21, 0s
9 = 34, 0s
10 = 55, 0s
15 = 610, 0s
20 = 6765, 0s
30 = 832040, 0s
40 = 102334155, 0s
50 = 12586269025, 0s
60 = 1548008755920, 0s
70 = 190392490709135, 0s
80 = 23416728348467685, 0s
90 = 2880067194370816120, 0.001s
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment