Hi Alex,
You may want to have logic tests in place to be sure your improvements are
correct.
Capturing the complete call graph and CPU/memory usage using pprof may help
reveal improvements. The visualization output has options you might want to
adjust.
Inspecting the assembly output is
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
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
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
Thanks! Cashing improved things dramatically.
--
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
You can memoize i.e. cache results of kbonacci().
See https://play.golang.org/p/Q2RjWZ2VTh3 for a working but not production
ready implementation (for example, cache is specific to k etc.).
When running locally for (5,35):
Running for n=35
res: 2809074173, time: 12.189908825s
res: 2809074173,
Thanks!
--
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 should be able to generalize the solution from the common
implementation of DP Fibonacci.
One caveat would be that expressing the integers as strings will make it
harder to do arithmetic on them.
On Monday, May 14, 2018 at 8:22:00 PM UTC-4, Alex Dvoretskiy wrote:
>
> Hello Golang Nuts
>
>
