gmane.comp.lang.erlang.general

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

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

<div>
<table cellspacing="0" cellpadding="0" border="0"><tr><td valign="top">what does when N&gt;0 do here? seems like no difference.<br>
and would you consider this good idiomatic erlang(ofc there is an even faster one that i found, posted at the end)?<br><br>
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.<br><br>
fib_i(A, _B, 0) -&gt; A;<br>
fib_i(A, B, N) when N &gt; 0 -&gt; fib_i(B, A + B, N - 1).<br>
fib(N) -&gt; fib_i(0, 1, N).<br><br>
fib_i(A, _B, 0) -&gt; A;<br>
fib_i(A, B, N)&nbsp; -&gt; fib_i(B, A + B, N - 1).<br>
fib(N) -&gt; fib_i(0, 1, N).<br><br><br><br><br><br><br>
fibo3(0, _, Pair) -&gt; Pair;<br>
fibo3(N, {Fib1, Fib2}, Pair) when N rem 2 == 0 -&gt;<br>
&nbsp;&nbsp;&nbsp; SquareFib1 = Fib1*Fib1,<br>
&nbsp;&nbsp;&nbsp; fibo3(N div 2, {2*Fib1*Fib2 - SquareFib1, SquareFib1 + Fib2*Fib2}, Pair);<br>
fibo3(N, {FibA1, FibA2}=Pair, {FibB1, FibB2}) -&gt;<br>
&nbsp;&nbsp;&nbsp; fibo3(N-1, Pair, {FibA1*FibB2 + FibB1*(FibA2 - FibA1), FibA1*FibB1 + FibA2*FibB2}).</td></tr></table>
<br><table><tr><td>Ta semester! - s&ouml;k efter resor hos Kelkoo. <br>J&auml;mf&ouml;r pris p&aring; flygbiljetter och hotellrum: <a href="http://www.kelkoo.se/c-169901-resor-biljetter.html?partnerId=96914051">http://www.kelkoo.se/c-169901-resor-biljetter.html</a>
</td></tr></table>
</div>

headers

t ty | 1 Jul 15:23

Re: what does when do here? fib(1200000) so slow, erlang cant handle big numbers?

What would happen if you didn't have the 'when N > 0' and you call
using fib(-1) ?

2008/7/1 Circular Function <circularfunc <at> yahoo.se>:
> 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)?
>

headers

Edwin Fine | 1 Jul 15:38

Re: what does when do here? fib(1200000) so slow, erlang cant handle big numbers?

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 <circularfunc <at> yahoo.se>:

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

_______________________________________________
erlang-questions mailing list
erlang-questions <at> erlang.org
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)

<div>
<p>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 &gt; 0 prevents infinite recursion if you call fib(-1). <br><br></p>
<div class="gmail_quote">2008/7/1 Circular Function &lt;<a href="mailto:circularfunc <at> yahoo.se">circularfunc <at> yahoo.se</a>&gt;:<br><blockquote class="gmail_quote">
<table border="0" cellpadding="0" cellspacing="0"><tr><td valign="top">
what does when N&gt;0 do here? seems like no difference.<br>
and would you consider this good idiomatic erlang(ofc there is an even faster one that i found, posted at the end)?<br><br>
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.<br><br>
fib_i(A, _B, 0) -&gt; A;<br>
fib_i(A, B, N) when N &gt; 0 -&gt; fib_i(B, A + B, N - 1).<br>
fib(N) -&gt; fib_i(0, 1, N).<br><br>
fib_i(A, _B, 0) -&gt; A;<br>
fib_i(A, B, N)&nbsp; -&gt; fib_i(B, A + B, N - 1).<br>
fib(N) -&gt; fib_i(0, 1, N).<br><br><br><br><br><br><br>
fibo3(0, _, Pair) -&gt; Pair;<br>
fibo3(N, {Fib1, Fib2}, Pair) when N rem 2 == 0 -&gt;<br>
&nbsp;&nbsp;&nbsp; SquareFib1 = Fib1*Fib1,<br>
&nbsp;&nbsp;&nbsp; fibo3(N div 2, {2*Fib1*Fib2 - SquareFib1, SquareFib1 + Fib2*Fib2}, Pair);<br>
fibo3(N, {FibA1, FibA2}=Pair, {FibB1, FibB2}) -&gt;<br>
&nbsp;&nbsp;&nbsp; fibo3(N-1, Pair, {FibA1*FibB2 + FibB1*(FibA2 - FibA1), FibA1*FibB1 + FibA2*FibB2}).</td></tr></table>
<br><table><tr>
<td>Ta semester! - s&ouml;k efter resor hos Kelkoo. <br>J&auml;mf&ouml;r pris p&aring; flygbiljetter och hotellrum: <a href="http://www.kelkoo.se/c-169901-resor-biljetter.html?partnerId=96914051" target="_blank">http://www.kelkoo.se/c-169901-resor-biljetter.html</a>
</td>
</tr></table>
<br>_______________________________________________<br>
erlang-questions mailing list<br><a href="mailto:erlang-questions <at> erlang.org">erlang-questions <at> erlang.org</a><br><a href="http://www.erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://www.erlang.org/mailman/listinfo/erlang-questions</a><br>
</blockquote>
</div>
<br><br clear="all"><br>-- <br>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.<br>
John F. Kennedy 35th president of US 1961-1963 (1917 - 1963)
</div>

headers

Jesper Louis Andersen | 1 Jul 16:06

Re: what does when do here? fib(1200000) so slow, erlang cant handle big numbers?

2008/7/1 Edwin Fine <erlang-questions_efine <at> usa.net>:

>The N > 0 prevents infinite recursion if you call fib(-1).

It is much more powerful than that, as it also fails calls like fib(0.5) though
it does so after a considerable amount of time. One could imagine moving
the guard to the fib/1 call rather than having it on fib_i/3 with the
possibility
that the VM has to check it each time (I don't know what the VM does here,
specifically). A check on is_integer/1 could eliminate the wait time as well.

headers

Alpár Jüttner | 1 Jul 15:42

Re: what does when do here? fib(1200000) so slow, erlang cant handle big numbers?

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