The O(lg n) recursion with memorization algorithm for computing fib(n) can be directly derived from its formula by repeated application of it.
f(n)= f(n-1)+f(n-2)= 2*f(n-2)+f(n-3)=f(2)*f(n-2)+f)1)*(n-3)= 3*f(n-3)+2*f(n-4)=f(3)*f(n-3)+f(2)*f(n-4)= and so on until you reach an expression built with nothing larger than f(n/2). > On May 15, 2018, at 5:46 AM, Jesper Louis Andersen > <[email protected]> wrote: > > Immediate idea would be to try to exploit > > https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form > > and its representation. This yields the memoization trick from above. If done > correctly, it might be possible to get the O(lg n) run-time which would be > highly desired. > >> On Tue, May 15, 2018 at 6:51 AM Alex Dvoretskiy <[email protected]> >> wrote: >> Just noticed. Even restructuring the code the way kjk did improved runing >> time, without caching. Amazing. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "golang-nuts" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> For more options, visit https://groups.google.com/d/optout. > > -- > You received this message because you are subscribed to the Google Groups > "golang-nuts" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout.
