[firebacon]

Interesting to consider the total complexity of that approach though.

An iterative fibonacci solution runs in linear time. Calculating the N'th fibonacci number requires O(N) serial operations.

A fully parallel, recursive solution without memoization requires that each value in the sequence is computed more than once. Consider the example of fib(4):

   fib(4) = fib(3) + fib(2)
   fib(3) = fib(2) + fib(1)
   fib(2) = fib(1) + fib(0)

You can see, that if we run this in parallel, the value of fib(1) has to be calculated twice. As the tree of operation branches out, more and more duplicate calculations are required.

A quick google suggests that the time complexity of the recursive approach is O(2^N).

[chrisseaton]

> An iterative fibonacci solution runs in linear time.

Absolutely nobody is under the impression that the naive parallel implementation of fib is actually useful code or the most efficient way to do it. You're missing the point if you're suggesting a different way to do it in the first place.

It's just something to use as a running example... like on the original article this whole thread is about.

[SamBam]

Ok, but it's a bit odd that you kept reacting with incredulity at people not knowing that fib was THE parallel example to know, and then it turns out it's a poor example because synchronous fib with memoization (which is the way many people learn it in any early CS class, and which wouldn't be possible async) is so much faster.

I think maybe if there hadn't been such a vibe of "what, you don't know X?!?" then it would have just been an interesting fact to mention that parallelization demos often use fib, because it's an easy example to grok (though a confusing one if you already understand the faster method).