Re:Google's Introduction to Parallel Programming and MapReduce
by SamReidHughes on Sunday October 23, 2011 @06:28PM
(#3147481)
Since 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.
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.