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 > <jesper.louis.ander...@gmail.com> 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 <advoretski...@gmail.com> >> 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 golang-nuts+unsubscr...@googlegroups.com. >> 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 golang-nuts+unsubscr...@googlegroups.com. > 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 golang-nuts+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
