3 ms·
The article says that Fibonacci can't be parallelized. But I seem to recall that there is a true data-parallel way of doing Fibonacci - one of those virtuoso tr
by gruseom 15y ago
The article says that Fibonacci can't be parallelized. But I seem to recall that there is a true data-parallel way of doing Fibonacci - one of those virtuoso tricks where something that seems intrinsically sequential gets transformed into a parallel computation. Does anyone know what I'm talking about?
Edit: to be clear, I don't mean the obvious but useless trick where you can compute F(n-1) and F(n-2) recursively in parallel, which is just redoing most of the work. I mean a way to model the problem as operations on data-parallel vectors.
- defen 15y ago[1 1; 1 0]^n = [Fn+1 Fn; Fn Fn-1] So you could rewrite n as a sum of m powers of 2 (just write it in binary), then for each "1" there, send it to a separate processor to compute [1 1; 1 0]^k using exponentiation by squaring (where k is the corresponding power of 2). Your reduce step multiplies the resulting matrices together. Note: this is just the first thing that comes to mind, I have no idea if this is what you were thinking of, or if it's even a good idea.
- SamReidHughes 15y agoSince computing [1 1; 1 0]^(2k) where k is a power of 2 would involve computing [1 1; 1 0]^k first, you'll end up reproducing the exact same work on all your machines, and you might as well just use the one.