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 | +--------+----------+-----+

## No comments:

## Post a Comment