[erlang-questions] or?

Alpár Jüttner <>
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).
> 
> 	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
bignums?

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.)

Regards,
Alpar




More information about the erlang-questions mailing list