Menu
I need to parallel (with openmp) the Fibonacci sequence from this sequential code to calculate the 10 5-th term of the sequence, but I have been stuck for 3 weeks without any good idea, someone have any idea or tip of a good way to do it? Here is the sequential code in C. Write a C program to print Fibonacci series up to n terms using loop. Logic to print Fibonacci series in a given range in C programming. Learn C programming, Data Structures tutorials, exercises, examples, programs, hacks, tips and tricks online. Logic to print Fibonacci series upto n terms.
![Openmp Fibonacci Series C Program Openmp Fibonacci Series C Program](https://www.researchgate.net/profile/Andrew_Lumsdaine/publication/220782311/figure/fig1/AS:669994169946117@1536750466141/A-typical-view-of-Cilk-parallel-execution-of-Fibonacci-numbers-Programmers-have-no.png)
Active4 months ago
I need to parallel (with openmp) the Fibonacci sequence from this sequential code to calculate the 105-th term of the sequence, but I have been stuck for 3 weeks without any good idea, someone have any idea or tip of a good way to do it?
Here is the sequential code in C:
chqrlie![Openmp Fibonacci Series C Program Openmp Fibonacci Series C Program](/uploads/1/2/5/7/125733405/626902164.jpg)
69.3k99 gold badges6060 silver badges116116 bronze badges
JESUSJESUS
2 Answers
Instead of trying to parallelise the bignum addition, which is tricky, you can take try and compute multiple terms in parallel:
Note also that you should compute blocks of digits at a time: 8 or 9 base-10 digits can be computed using 32-bit array elements.
Here is a modified version with multiple improvements:
- it computes blocks of 8 digits at a time
- it can take command line arguments
- it uses much less memory
- it can handle much larger values
- it is much more efficient (20x)
You should be able to parallelise it easily.
chqrliechqrlie69.3k99 gold badges6060 silver badges116116 bronze badges
As you already know, F(100000) is an astronomically huge number. And to compute that value, you have to sum two other really huge numbers F(99999) and F(99998).
Here's my hint:
You've got two numbers that are many (thousands) of digits long and N processors. You can split the addition up across multiple threads. For example:
To compute F(169), you have to add both of those numbers above. But let's treat it as 4 separate additions of 9 digits each.
So now we've got 4 summations. Two of which,
C
and D
, have a carry operation. So we just need to adjust the result of the left of each by +1So your algorithm to compute Fib(100000) is something like the following. Where
BigNumber
is a struct that is a representation of your digits. You are using an array of characters, which is also acceptable.Your
selbieselbieParallelAdd
will break the numbers passed via pointer, f1 and f0, into N groups of K digits each, where N is the number of processors you have available or want to use. Then each processor computes the addition of each - using the code you already have. After those N operations have completed, scan the result set to see which additions contained a result that was K+1 digits long, and then adjust with +1 logic as described above. The combine into a single string and shove back into the pointer address referenced by pF2
.60.8k1111 gold badges6969 silver badges133133 bronze badges
Not the answer you're looking for? Browse other questions tagged cmultithreadingparallel-processingopenmpfibonacci or ask your own question.
Active6 years, 3 months ago
Is there any benefit by using OpenMP to parallelize the Fibonacci number calculations?
There are several examples online which calculate Fibonacci numbers using the
task
directive in OpenMP. For example at http://docs.oracle.com/cd/E19205-01/820-7883/girtd/index.html and here http://openmp.org/forum/viewtopic.php?f=3&t=1231Some of these examples claim the performance is better with OpenMP. I don't understand this as calculating the Fibonacci series is, to my understanding, fundamentally non parallel (ignoring methods based on closed form solutions, e.g. from Binet's formula).
Additionally, recursion, which the OpenMP examples are based on, has much worse performance (several orders of magnitude worse) than calculating the numbers iteratively (this is well known Iterative and recursive version has same complexity?). But when I use OpenMP it's even slower! It seems silly to use an example to demonstrate how to use a feature of OpenMP which gives worse performance.So I'm trying to understand why these code examples exist?
Here is the code I used to test the functions.
Community♦
user2088790
1 Answer
The code in the link you posted is almost equal to Example A.15.4c in the OpenMP 3.1 standard:
Under the example you can find the following:
Note: There are more efficient algorithms for computing Fibonacci numbers. This classic recursion algorithm is for illustrative purposes.
So I assume this is just to have a small example for didactic purposes.
MassimilianoMassimiliano5,66122 gold badges3535 silver badges5353 bronze badges