<div dir="ltr">Thank you Mario, that was interesting in and of itself.<br></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, May 11, 2016 at 8:34 AM, Mario Lang <span dir="ltr"><<a href="mailto:mlang@delysid.org" target="_blank">mlang@delysid.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">Michael Litchard <<a href="mailto:michael@schmong.org">michael@schmong.org</a>> writes:<br>
<br>
> I am trying to efficiently use multicores for my fizzbuzz<br>
</span>> <<a href="https://github.com/mlitchard/swiftfizz" rel="noreferrer" target="_blank">https://github.com/mlitchard/swiftfizz</a>> project. My fizzbuzz uses a<br>
<span class="">> Fibonacci generator as input, and this is where it can get computationally<br>
> heavy. I believe I have picked the best algorithm for my project (please<br>
> correct this if wrong),<br>
<br>
</span>I'd like to point you to this rather interesting task and code example I<br>
happened to stumble across recently:<br>
<br>
<a href="https://www.youtube.com/watch?v=32f6JrQPV8c" rel="noreferrer" target="_blank">https://www.youtube.com/watch?v=32f6JrQPV8c</a> (18:30-21:40)<br>
<a href="https://github.com/sean-parent/scratch/blob/master/scratch/main.cpp" rel="noreferrer" target="_blank">https://github.com/sean-parent/scratch/blob/master/scratch/main.cpp</a><br>
<br>
Sean is basically saying that doing fibonacci via recursion is wrong.<br>
Fibonacci is actually a linear recurrance, and can be calculated with a<br>
power algorithm.<br>
<br>
The Haskell Wiki has a section about this approach:<br>
<a href="https://wiki.haskell.org/The_Fibonacci_sequence#Using_2x2_matrices" rel="noreferrer" target="_blank">https://wiki.haskell.org/The_Fibonacci_sequence#Using_2x2_matrices</a><br>
<br>
The code below gives fib of 100000000 in a few seconds on my PC.<br>
No need to go paralell.<br>
<br>
And if you need the complete series, [fib n | n <- [1..1000000]] still<br>
just takes a second here.<br>
<br>
```Haskell<br>
module PowerFib where<br>
import Data.List (transpose)<br>
<br>
newtype Matrix a = Matrix [[a]] deriving (Eq, Show)<br>
instance Num a => Num (Matrix a) where<br>
   Matrix as + Matrix bs = Matrix (zipWith (zipWith (+)) as bs)<br>
   Matrix as - Matrix bs = Matrix (zipWith (zipWith (-)) as bs)<br>
   Matrix as * Matrix bs = Matrix [[sum $ zipWith (*) a b | b <- transpose bs] | a <- as]<br>
   negate (Matrix as) = Matrix (map (map negate) as)<br>
   fromInteger x = Matrix (iterate (0:) (fromInteger x : repeat 0))<br>
   abs m = m<br>
   signum _ = 1<br>
<br>
apply (Matrix as) b = [sum (zipWith (*) a b) | a <- as]<br>
<br>
fib n = head (apply (Matrix [[0,1], [1,1]] ^ n) [0,1])<br>
```<br>
<span class="HOEnZb"><font color="#888888"><br>
--<br>
CYa,<br>
  ⡍⠁⠗⠊⠕<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
</font></span></blockquote></div><br></div>