When I see func FibTailVecSum(n int) int { if n < 2 ... and func FibTailVec(acc int, a int, b int) (int, int) { if acc == 1 { I go full Terry Pratchett and began to yell Guards! Guards! I mean, these are perfect examples of Elixir guards. Is there a similar functionality in Go?
Tail Recursion Tactics: Fibonacci
11–20 of 38 posts
Re: Tail Recursion Tactics: Fibonacci
#12Would be neat to see how the vector version works using successive squares.
Re: Tail Recursion Tactics: Fibonacci
#13Re: Tail Recursion Tactics: Fibonacci
#14Unfortunate, that your results for `n = 90` are completely useless, since F_90 > 2^32 which is the size of int.
Also, you could have shown a method which is O(log n), namely [[F(n+1) F(n)], [F(n) F(n-1)]] equals [[1, 1] [1, 0]] raised to the power of n.
Re: Tail Recursion Tactics: Fibonacci
#15Unfortunate, that your results for `n = 90` are completely useless, since F_90 > 2^32 which is the size of int. Also, you could have shown a method which is O(log n), namely [[F(n+1) F(n)], [F(n) F(n-1)]] equals [[1, 1] [1, 0]] raised to the power of n.
Actually F_90 Indeed you can compute Fibonacci numbers (and other linear recurrences) with matrix exponentiation, or with a closed-form equation like the Binet Formula - but I limited the scope of this article to tail recursion.
Binet Formula: http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.ht...
Re: Tail Recursion Tactics: Fibonacci
#16https://wiki.haskell.org/The_Fibonacci_sequence
The canonical zipWith solution is a thing of beauty.
Re: Tail Recursion Tactics: Fibonacci
#17Unfortunate, that your results for `n = 90` are completely useless, since F_90 > 2^32 which is the size of int. Also, you could have shown a method which is O(log n), namely [[F(n+1) F(n)], [F(n) F(n-1)]] equals [[1, 1] [1, 0]] raised to the power of n.
Actually F_90 Indeed you can compute Fibonacci numbers (and other linear recurrences) with matrix exponentiation, or with a closed-form equation like the Binet Formula - but I limited the scope of this article to tail recursion. Binet Formula: http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.ht...
I suspect that computing Fibonacci numbers with Binet formula is slower than with matrix form - if mul(n) is the number of multiplications required to compute x^n, then matrix form will use 8 * mul(n) integer multiplications, while Binet's formula requires 2 * mul(n) floating point operations. I suspect the latter is slower.
Re: Tail Recursion Tactics: Fibonacci
#18Unfortunate, that your results for `n = 90` are completely useless, since F_90 > 2^32 which is the size of int. Also, you could have shown a method which is O(log n), namely [[F(n+1) F(n)], [F(n) F(n-1)]] equals [[1, 1] [1, 0]] raised to the power of n.
Actually F_90 Indeed you can compute Fibonacci numbers (and other linear recurrences) with matrix exponentiation, or with a closed-form equation like the Binet Formula - but I limited the scope of this article to tail recursion. Binet Formula: http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.ht...
You can implement matrix exponentiation recursively however.
Re: Tail Recursion Tactics: Fibonacci
#19Tail 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, but do supply higher-order function.
For example, Python 3:
import functools
import itertools
def fib(n):
def get_next(i):
a, b = i
return (b, a + b)
a, b = functools.reduce(
get_next,
itertools.repeat(None, n),
(0, 1),
)
return b
def generate(get_next, c):
while True:
yield c
c = get_next(c)
import itertools
def fib(n):
def get_next(i):
a, b = i
return (b, a + b)
a, b = next(itertools.islice(
generate(get_next, (0, 1)),
n,
))
return b
def nth(seq, n):
return next(itertools.islice(seq, n))
def fib(n):
def get_next(i):
a, b = i
return (b, a + b)
a, b = nth(generate(get_next, (0, 1)), n)
return b
Re: Tail Recursion Tactics: Fibonacci
#20Earlier quoted context omitted.
Actually F_90 Indeed you can compute Fibonacci numbers (and other linear recurrences) with matrix exponentiation, or with a closed-form equation like the Binet Formula - but I limited the scope of this article to tail recursion. Binet Formula: http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.ht...
You can implement matrix exponentiation recursively however.
> You can implement matrix exponentiation recursively however.
And tail recursively, and – going full circle – you can convert that tail recursion into iteration (see [1] for example, using techniques described in [2]).
[1] Iterative fast-power implementation in Python https://github.com/tmoertel/practice/blob/master/libraries/t...
[2] Recursion to Iteration, Part 1: The Simple Method, secret features, and accumulators http://blog.moertel.com/posts/2013-05-11-recursive-to-iterat...