[erlang-questions] what does when do here? fib(1200000) so slow, erlang cant handle big numbers?
Alpár Jüttner
alpar@REDACTED
Tue Jul 1 15:42:43 CEST 2008
On my computer fib(1200000) finishes correctly in around 100 seconds.
Remember, that Fibonacci calculation is not linear because you must do
linear number of operations, but on huge numbers. So your algorithm is
in fact O(n^2), therefore you should expect 100 times higher running
time for a 10 times bigger input.
Regards,
Alpar
On Tue, 2008-07-01 at 12:31 +0000, Circular Function wrote:
> what does when N>0 do here? seems like no difference.
> and would you consider this good idiomatic erlang(ofc there is an even
> faster one that i found, posted at the end)?
>
> also, this is linear right? so why does fib(1200000) never finsih?
> erlang cant handle such big numbers? because 12000 is pretty much
> instant and 120000 takes a second or so.
>
> fib_i(A, _B, 0) -> A;
> fib_i(A, B, N) when N > 0 -> fib_i(B, A + B, N - 1).
> fib(N) -> fib_i(0, 1, N).
>
> fib_i(A, _B, 0) -> A;
> fib_i(A, B, N) -> fib_i(B, A + B, N - 1).
> fib(N) -> fib_i(0, 1, N).
More information about the erlang-questions
mailing list