Sun Jun 22 12:56:15 CEST 2008
> In this case, it would be better to do
> fib(N) when is_integer(N), N >= 0 ->
> fib_aux(N) when N > 1 -> fib_aux(N-1) + fib_aux(N-2);
> fib_aux(N) -> N.
> Better still, of course, would be to use the standard
> linear-time tail-recursive version, or even better, the
> less well known logarithmic time version (an approach
> that works for other recurrences as well).
Does erlang implement some kind of fast multiplication algorithm for
I'm just wondering because if the multiplication is done in O(n^2) time,
then this 'logaritmic time' Fibonacci computation is actually not faster
then the 'linear time' one. (It does O(log n) operation, however not
only does it use additions but also multiplication.)
More information about the erlang-questions