[Cuis-dev] Really fast Fibonacci function

[Agustín Sansone]

Hi all,

I was exploring the *mathematical functions* category of the class *Integer*
and a I didn't find the very well-known Fibonacci function ("
*f(n)=f(n-1)+f(n-2)"*) , so I decided to implement it. I think this will be
interesting due to the complexity I found (wich is O(log(n))!!).

   - A simple way to implement it is by writing the direct recursive
   mathematical recurrence relation. This would be exponential.
   - An iterative solution wouldn't do all this repeated work, therefore it
   would be lineal.
   - I used a dynamic-programming-divide-and-conquer-aproach wich computes
   the n-th Fibonacci number in O(log(n)). I think from this comment you can
   see why it works:
   https://math.stackexchange.com/questions/1834242/derivation-of-fibonacci-logn-time-sequence
   .

Here are some running times:
exponential --> [1 to: 40 do: [:elem | elem fibonacciNumber]] timeToRun
38536
lineal -->           [1 to: 10000 do: [:elem | elem fibonacciNumber]]
timeToRun.   25558
logarithmic -->  [1 to: 10000 do: [:elem | elem fibonacciNumber]]
timeToRun.   1471

I leave you all three implementations, let me know what you think,
Agustín
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cuis.st/mailman/archives/cuis-dev/attachments/20191207/ce419c18/attachment.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Integer-fibonacciNumber.st
Type: application/octet-stream
Size: 400 bytes
Desc: not available
URL: <http://lists.cuis.st/mailman/archives/cuis-dev/attachments/20191207/ce419c18/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Integer-fibonacciNumber_Expontential.st
Type: application/octet-stream
Size: 380 bytes
Desc: not available
URL: <http://lists.cuis.st/mailman/archives/cuis-dev/attachments/20191207/ce419c18/attachment-0001.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Integer-fibonacciNumber_Lineal.st
Type: application/octet-stream
Size: 624 bytes
Desc: not available
URL: <http://lists.cuis.st/mailman/archives/cuis-dev/attachments/20191207/ce419c18/attachment-0002.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Integer-fibonacciNumberWith.st
Type: application/octet-stream
Size: 626 bytes
Desc: not available
URL: <http://lists.cuis.st/mailman/archives/cuis-dev/attachments/20191207/ce419c18/attachment-0003.obj>