[erlang-questions] what does when do here? fib(1200000) so slow, erlang cant handle big numbers?

Edwin Fine <>
Tue Jul 1 15:38:59 CEST 2008


It finishes on my system in 46 seconds. It produces a number that is 250785
digits long. That's a humungous, massive, mind-bogglingly large number. A
googol (10^100) only has 100 digits. This is 2500x the size of a googol. I
would *guess* that although the *algorithm* is linear, you are hitting a
non-linearity in the large number representation in Erlang, maybe due to GC
or memory growth. I dunno. I mean, you are adding together two massive
numbers over and over towards the end. The N > 0 prevents infinite recursion
if you call fib(-1).

2008/7/1 Circular Function <>:

> 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).
>
>
>
>
>
>
> fibo3(0, _, Pair) -> Pair;
> fibo3(N, {Fib1, Fib2}, Pair) when N rem 2 == 0 ->
>     SquareFib1 = Fib1*Fib1,
>     fibo3(N div 2, {2*Fib1*Fib2 - SquareFib1, SquareFib1 + Fib2*Fib2},
> Pair);
> fibo3(N, {FibA1, FibA2}=Pair, {FibB1, FibB2}) ->
>     fibo3(N-1, Pair, {FibA1*FibB2 + FibB1*(FibA2 - FibA1), FibA1*FibB1 +
> FibA2*FibB2}).
> ------------------------------
> Ta semester! - sök efter resor hos Kelkoo.
> Jämför pris på flygbiljetter och hotellrum:
> http://www.kelkoo.se/c-169901-resor-biljetter.html<http://www.kelkoo.se/c-169901-resor-biljetter.html?partnerId=96914051>
> _______________________________________________
> erlang-questions mailing list
> 
> http://www.erlang.org/mailman/listinfo/erlang-questions
>



-- 
The great enemy of the truth is very often not the lie -- deliberate,
contrived and dishonest, but the myth, persistent, persuasive, and
unrealistic. Belief in myths allows the comfort of opinion without the
discomfort of thought.
John F. Kennedy 35th president of US 1961-1963 (1917 - 1963)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20080701/c8837430/attachment.html>


More information about the erlang-questions mailing list