Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Tail Recursion Tactics: Fibonacci

blog.des.io

Post reply on HN
Print view View original

31–38 of 38 posts

Re: Tail Recursion Tactics: Fibonacci

#31

Post by cousin_it »

engnr567 wrote: post #30
cousin_it wrote: post #22

If you're computing Fibonacci numbers using only addition, no matter how clever your recursion, you will always lose out to algorithms that use multiplication. https://www.nayuki.io/page/fast-fibonacci-algorithms

Exactly. And fibonacci numbers also have a closed form which can be (in theory) evaluated in O(1): http://austinrochford.com/posts/2013-11-01-generating-functi...

The number of digits in the nth Fibonacci number grows linearly with n, so you can't compute these digits in O(1). The fastest algorithms, described in the link I gave, have complexity O(n * something) where "something" grows much slower than n and depends on the bigint multiplication algorithm used.

Re: Tail Recursion Tactics: Fibonacci

#32

Post by UncleEntity »

kerkeslager wrote: post #19

Tail call optimization is a clever, but even in functional languages, twisting your code around to use tail calls is often a code smell. Most uses of tail recursion would be better-served by using some higher-order functions. The reason is that when you write something tail recursively, it's sort of like rolling your own iteration. This is particularly true because many platforms don't supply tail call optimization,…

Poked around on the google[0]:

  def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return b
No itertools, not overly complex, no tail recursion.

If you were careful of the scoping rules something like foo(get_next(i) for i in whatever()) could be made to work without too much trouble (also without itertools) if you needed a sequence. Probably just throw a lambda in there instead of get_next and python would be happy, too lazy to work it out.

[0]http://www.koderdojo.com/blog/python-fibonacci-number-genera...

--edit--

Actually, I think this function gives the wrong result for 0 and maybe 1, just copypasta'd the code so blame them...

Re: Tail Recursion Tactics: Fibonacci

#33

Post by kerkeslager »

UncleEntity wrote: post #32
kerkeslager wrote: post #19

Tail call optimization is a clever, but even in functional languages, twisting your code around to use tail calls is often a code smell. Most uses of tail recursion would be better-served by using some higher-order functions. The reason is that when you write something tail recursively, it's sort of like rolling your own iteration. This is particularly true because many platforms don't supply tail call optimization,…

Poked around on the google[0]: def fib(n): a, b = 0, 1 for _ in range(n): a, b = b, a + b return b No itertools, not overly complex, no tail recursion. If you were careful of the scoping rules something like foo(get_next(i) for i in whatever()) could be made to work without too much trouble (also without itertools) if you needed a sequence. Probably just throw a lambda in there instead of get_next and python would be…

I think this is the correct way to do this in a Python codebase where procedural programming is the dominant paradigm, but that's not really what my previous post is about.

EDIT: Also c'mon man. This is not a problem that you need to Google. :P

Re: Tail Recursion Tactics: Fibonacci

#34

Post by e12e »

cousin_it wrote: post #22

If you're computing Fibonacci numbers using only addition, no matter how clever your recursion, you will always lose out to algorithms that use multiplication. https://www.nayuki.io/page/fast-fibonacci-algorithms

How do you implement multiplication without addition?

Re: Tail Recursion Tactics: Fibonacci

#35

Post by e12e »

dustingetz wrote: post #13

https://wiki.haskell.org/The_Fibonacci_sequence

Seems to be a case of reality imitating satire:

https://www.willamette.edu/~fruehr/haskell/evolution.html

;-)

But, thanks for the pointer - from a glance it looks like a fine way to compare and contrast approaches/flavours of haskell programming.

Re: Tail Recursion Tactics: Fibonacci

#36

Post by desio »

dwilding wrote: post #10

I love your explanation of how to arrive at the vector transformation function. You might enjoy reading an article I wrote a few years ago that touches on maxtrix/vector computation of linear recurrences: http://aperiodical.com/2014/06/discovering-integer-sequences... Not as detailed as your post though. Thanks for a great write up!

Thanks for the feedback and sharing your article. I also find the matrix solution so satisfying especially when the eignenvalues come out as the golden ratio. I would really like to do a write-up on the intuition behind this and what it means to approach a linear recurrence as a vector space, solving with a matrix and the characteristic equation.

Re: Tail Recursion Tactics: Fibonacci

#37

Post by engnr567 »

cousin_it wrote: post #31
engnr567 wrote: post #30

Earlier quoted context omitted.

Exactly. And fibonacci numbers also have a closed form which can be (in theory) evaluated in O(1): http://austinrochford.com/posts/2013-11-01-generating-functi...

The number of digits in the nth Fibonacci number grows linearly with n, so you can't compute these digits in O(1). The fastest algorithms, described in the link I gave, have complexity O(n * something) where "something" grows much slower than n and depends on the bigint multiplication algorithm used.

The matrix exponentiation algorithm in the link you sent is O(log(n)). Yes, this might seem strange because the output (F_n) itself has n bits. But in practice most of the implementations would use long integers for output, so log(F_n) < 64 for these implementations.

Re: Tail Recursion Tactics: Fibonacci

#38

Post by cousin_it »

engnr567 wrote: post #37
cousin_it wrote: post #31

Earlier quoted context omitted.

The number of digits in the nth Fibonacci number grows linearly with n, so you can't compute these digits in O(1). The fastest algorithms, described in the link I gave, have complexity O(n * something) where "something" grows much slower than n and depends on the bigint multiplication algorithm used.

The matrix exponentiation algorithm in the link you sent is O(log(n)). Yes, this might seem strange because the output (F_n) itself has n bits. But in practice most of the implementations would use long integers for output, so log(F_n) < 64 for these implementations.

The article I linked has code examples in four languages, all use bigints, not longs.
Post reply on HN