Urban Hafner

CTM: Exercise 4-3

Posted by Urban Hafner Wed, 02 Nov 2005 16:13:16 GMT

The problem

Concurrent Fibonacci. Consider the following sequential definition of the Fibonacci function:

fun {Fib X}
   if X=<2 then 1
   else {Fib X-1}+{Fib X-2} end
end

and compare it with the concurrent definition given in section 4.2.3. Run both on the Mozart system and compare their performance. How much faster is the sequential definition? How many threads are created by the concurrent call {Fib N} as a function if N?

My solution

For timing I used the following function. Even though it can only count in seconds, it’s enough for this purpose.

fun {Timer Fun Arg}
   Before
in
   Before={Time.time}
   {Fun Arg _}
   {Time.time}-Before
end

For N=30 the normal Fibonacci function took 1 second, the concurrent one 19. For N=40 the normal one took 289 seconds and the concurrent one made my computer swap so I stopped it.

The number of thread created should be in the same order as the number of function calls done, because every other function call is done in its own thread. As the number of function calls is exponential so is the number of threads. Of course this is quite a lame answer, but neither did I have skills nor the motivation to find an exact solution. Maybe Wikipedia can help?