04-10-2015, 10:39 PM
I was wondering if there are any preexisting designs for solving Fibonacci in parallel? I found some "examples", but it seems that they failed to reuse numbers. For example they made set fib(9)=fib(8)+fib(7) and when solving fib(8) they do fib(8)=fib(7)+fib(6). It seems that they only use parallel because they are using an inefficient way of solving Fibonacci... recalculating everything over and over again, never storing values for future use.
I was wondering if there are any preexisting ones, because I think I might have found a more useful way of solving in parallel. Lets start with a list of the first few values. In my examples fib(0)=0.
0 1 1 2 3 5 8 13 21 34 55 89 144
Ok lets say you want the value for fib(0) to fib(100). You start with a few answers already: fib(0) to fib(12). The goal is to solve all the way up to fib(100). fib(13) is an obvious next step, so we work on solving it. While it's being solved another number can be calculated, fib(14). But how do we find the value for fib(14) without fib(13)? Instead of waiting for fib(13), we just convert it to a fib number we do know: fib(12)+fib(11). So the final formula for fib(14) is 2*fib(12)+fib(11). Instead of multiplying by two, which could possibly be slower than just waiting for fib(13), we could shift the number over by 1.
It might be possible that solving fib(14) like this might be a wasted effort, because you might not be solving the equation that much faster. But you can extend the rule to larger numbers that wouldn't be a waste of time. For example, fib(17)=8fib(12)+4fib(11)+fib(10)+fib(9). Using just shifting and adding, you could solve a problem that is 4 or 5 terms ahead of your highest Fibonacci term.
The problems I see with doing this in parallel is:
1) It's not very fast at solving smaller numbers
2) It depends on a table to look up solved fib numbers, so how do you prevent two (or more) threads reading the same term, or reading something that is currently being written to?
Feel free to comment or critique. Thank you for your time
I was wondering if there are any preexisting ones, because I think I might have found a more useful way of solving in parallel. Lets start with a list of the first few values. In my examples fib(0)=0.
0 1 1 2 3 5 8 13 21 34 55 89 144
Ok lets say you want the value for fib(0) to fib(100). You start with a few answers already: fib(0) to fib(12). The goal is to solve all the way up to fib(100). fib(13) is an obvious next step, so we work on solving it. While it's being solved another number can be calculated, fib(14). But how do we find the value for fib(14) without fib(13)? Instead of waiting for fib(13), we just convert it to a fib number we do know: fib(12)+fib(11). So the final formula for fib(14) is 2*fib(12)+fib(11). Instead of multiplying by two, which could possibly be slower than just waiting for fib(13), we could shift the number over by 1.
It might be possible that solving fib(14) like this might be a wasted effort, because you might not be solving the equation that much faster. But you can extend the rule to larger numbers that wouldn't be a waste of time. For example, fib(17)=8fib(12)+4fib(11)+fib(10)+fib(9). Using just shifting and adding, you could solve a problem that is 4 or 5 terms ahead of your highest Fibonacci term.
The problems I see with doing this in parallel is:
1) It's not very fast at solving smaller numbers
2) It depends on a table to look up solved fib numbers, so how do you prevent two (or more) threads reading the same term, or reading something that is currently being written to?
Feel free to comment or critique. Thank you for your time
