factorial and fibonacci in bko
Last post I defined arithmetic. So here a couple of examples:
Factorial:
|context> => |context: factorial>
fact |0> => |1>
n-1 |*> #=> arithmetic(|_self>,|->,|1>)
fact |*> #=> arithmetic( |_self>, |*>, fact n-1 |_self>)
eg:
sa: fact |5>
|120>
Fibonacci:
|context> => |context: Fibonacci>
fib |0> => |0>
fib |1> => |1>
n-1 |*> #=> arithmetic(|_self>,|->,|1>)
n-2 |*> #=> arithmetic(|_self>,|->,|2>)
fib |*> #=> arithmetic( fib n-1 |_self>, |+>, fib n-2 |_self>)
fib-ratio |*> #=> arithmetic( fib |_self> , |/>, fib n-1 |_self> )
eg:
sa: fib |10>
|55>
sa: fib |11>
|89>
sa: fib |20>
|6765>
sa: fib |21>
|10946>
sa: fib-ratio |30>
|1.6180339887482036>
-- NB: if we have only defined fib |0> and fib |1> the debugging info for fib-ratio |30> is insane!
So a massive speed up is to do these first:
fib |10> => fib |10>
fib |11> => fib |11>
fib |20> => fib |20>
fib |21> => fib |21>
-- NB: these work by making use of label descent.
-- and are an example of "memoization".
Next thing to observe is that fib/fact are linear and are applied separately to all kets in the superposition:
sa: fib (|10> + |11> + |12> + |13> + |14> + |15>)
|55> + |89> + |144> + |233> + |377> + |610>
sa: fact (|0> + |1> + |2> + |3> + |4> + |5> + |6> + |7>)
2.000|1> + |2> + |6> + |24> + |120> + |720> + |5040>
And that's it for now.
I guess I will also mention that I had not intended BKO to handle recursion, it just emerged naturally after implementing stored rules.
Update: First, it is time I explained these:
fib |10> => fib |10>
what is going on is that fib |10> on the right hand side is being computed. Then the result is being stored at "fib |10>". So next time you ask what is "fib |10>" it does a simple look-up, and not a full computation. The reason is that a simple look up has higher precedence than the general "fib |*>" rule (which is because of how we implemented label-descent).
Next, a quick example of the magic of tables:
sa: table[number,fact,fib] range(|1>,|11>)
+--------+----------+-----+
| number | fact | fib |
+--------+----------+-----+
| 1 | 1 | 1 |
| 2 | 2 | 1 |
| 3 | 6 | 2 |
| 4 | 24 | 3 |
| 5 | 120 | 5 |
| 6 | 720 | 8 |
| 7 | 5040 | 13 |
| 8 | 40320 | 21 |
| 9 | 362880 | 34 |
| 10 | 3628800 | 55 |
| 11 | 39916800 | 89 |
+--------+----------+-----+
Home
previous: arithmetic
next: diversion the tidy language underneath
updated: 19/12/2016
by Garry Morrison
email: garry -at- semantic-db.org