+- Forums - Open Redstone Engineers (https://forum.openredstone.org)
+-- Forum: Off-Topic (https://forum.openredstone.org/forum-4.html)
+--- Forum: Programming (https://forum.openredstone.org/forum-8.html)
+--- Thread: [Theory] Solving Fibonacci in Parallel (/thread-6144.html)
[Theory] Solving Fibonacci in Parallel - AltruismAndCake - 04-10-2015
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
RE: [Theory] Solving Fibonacci in Parallel - jxu - 04-11-2015
Yes, you have essentially described memoization (which is also easier and faster than shifting)
RE: [Theory] Solving Fibonacci in Parallel - AltruismAndCake - 04-11-2015
Yep, I already knew about memoization, the part I wanted to know more about was the ability to skip over terms, so that it's possible to save time getting the final result(s). Is there a significant amount of time saved by solving in parallel? Is time saved by trying to solve two (or more) terms at the same time?
RE: [Theory] Solving Fibonacci in Parallel - AltruismAndCake - 04-13-2015
I decided to test my idea with actual code, and it turns out that it's not so easy in implementation. For my test I used a 3.8GHz AMD processor for one thread and my Nvidia GPU's 700MHz cuda cores with many threads. In the end I realized that the parallel/threaded code could never compete with a single thread program, because the multithreaded code requires checking if Fibonacci terms already exist, plus the over head of branching.
If anyone has any recommendations, I'll listen, but I think the overhead for trying to run a multi-threaded Fibonacci solver is too high and the simplest way is to simply just add.
Edit fixed typo
RE: [Theory] Solving Fibonacci in Parallel - Jallen - 04-13-2015
up to a point it's easier to do sequential adds, after a certain point (depending on processor architecture) you can use the formula that doesn't rely on any previous values. The formula involves irrational numbers though so there will be rounding errors: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html
RE: [Theory] Solving Fibonacci in Parallel - jxu - 04-18-2015
as Jallen says, the closed form formula is by far the best for finding individual terms
memoization is much more efficient than skipping terms. sequential adds are essentially the same method but in reverse (bottom up)
RE: [Theory] Solving Fibonacci in Parallel - tokumei - 04-24-2015
Yes, if at all possible, I would choose repetition over recursion in most cases. Particularly with Fibonacci, a problem that would take 5 minutes under recursion would take a mere second approx. The reason is the 2-branch recursion that the Fibonacci sequence is based on. Using that method, the time taken to solve a problem increases exponentially as the given number gets higher, whereas an iteration would generally have a linear increase in time.