The Fibonacci sequence using threads in C

Question

I wrote a program in C to generate a Fibonacci sequence with n numbers where each Fibonacci number created by a separate thread, the parent thread outputs whole produced Fibonacci sequence yet I got wrong sequence for n>2 it some how rewrite the value of the last element in the Fibonacci sequence array to 0 if n>2 .How i can fix it? please find the code below.

/*============================================================================
   Description :The Fibonacci sequence
  ============================================================================ */
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

int n;                          // size of fibonacci sequence.
int *fibseq;                    // arry holds the value of each fibonacci term.
int i;                          // counter for the threads.

void *runn(void *arg);

int main(int argc, char *argv[])
{
    if (argc != 2)
    {
        printf("format is:./a.out <intgervalue>\n");
        return -1;
    }                           // valdiate num of args.

    if (atoi(argv[1]) < 0)
    {
        printf("%d must be>=0\n", atoi(argv[1]));
        return -1;
    }                           // valdiate value of arg1.

    n = atoi(argv[1]);
    fibseq = (int *)malloc(n * sizeof(int));
    pthread_t *threads = (pthread_t *) malloc(n * sizeof(pthread_t));
    pthread_attr_t attr;        // set of thread attribute

    pthread_attr_init(&attr);

    for (i = 0; i < n; i++)
    {
        pthread_create(&threads[i], &attr, runn, NULL);
    }                           // End of creating threads.

    int j;

    for (j = 0; j < n; j++)
    {
        pthread_join(threads[j], NULL);
    }                           // End of wating the threads to exit.

    // printing fibseq.
    printf("The Fibonacci sequence.:");
    int k;

    for (k = 0; k < n; k++)
    {
        printf("%d,", fibseq[k]);
    }                           // End of printing fibseq.
    return 0;
}                               // End of main.

void *runn(void *arg)
{
    if (i == 0)
    {
        fibseq[i] = 0;
        pthread_exit(0);
    }                           // first fib term

    if (i == 1)
    {
        fibseq[i] = 1;
        pthread_exit(0);
    }                           // seconed fib term
    else
    {
        fibseq[0] = 0;
        fibseq[1] = 1;

        int p, pp, fibp, fibpp;

        p = (i - 1);
        pp = (i - 2);
        fibp = fibseq[p];
        // printf("fibseq[%d]%d\n",p,fibp);
        fibpp = fibseq[pp];
        // printf("fibseq[%d]%d\n",pp,fibpp);
        fibseq[i] = fibseq[i - 1] + fibseq[i - 2];
        // printf("fibseq[%d]%d,\n",i,fibseq[i]);
        pthread_exit(0);        // thread exit.
    }                           // End of else
}                               // End of run.

Answer 1

I see that this post is from December of 2015, however the answer to your problem is quite simple. The reason is because you are using two separate for loops to create and join your threads. What this is doing is causing i < n threads to create and run through your *runn function at the same time. Meaning the threads are not waiting for the array to be updated.

They should be in a single for loop, that way the thread_join statement regulates each thread during each loop cycle. As I did below.

for (i = 0; i < n; i++)
{
    pthread_create(&threads[i], &attr, runn, NULL);
    pthread_join(threads[i], NULL);
}   

Now your threads are going through your *runn function one at a time. Thus fixing your issue.

On a side note you seem to have some unnecessary code towards the bottom of your *runn function this isn't necessary and is just redoing the work you have already done.

 fibseq[0] = 0; //this is unnecessary, because from your first threads fibseq[0] should 
                //already equal 0
 fibseq[1] = 1; //same for here this value should be equal to 1 already

Also, this is unnecessary. Although if I understand it correctly, this was used for debugging purposes right?

int p, pp, fibp, fibpp;

p = (i - 1);
pp = (i - 2);
fibp = fibseq[p];
// printf("fibseq[%d]%d\n",p,fibp);
fibpp = fibseq[pp];
// printf("fibseq[%d]%d\n",pp,fibpp);

The only relevant code needed for the else statement is here

fibseq[i] = fibseq[i - 1] + fibseq[i - 2];
pthread_exit(0);        // thread exit.

I hope this helps answer this question.

Answer 2

The Fibonnaci sequence is ill-suited to a parallelized solution. There's actually a closed-form solution that's not too difficult to compute and almost certainly faster than even a thread-based solution:

Fn = (φn - ψn) / √5

where φ = (1 + √5) / 2 and ψ = (1 - √5) / 2.

^{Edit - on my system, the closed form diverges for n > 71 due to accumulated rounding errors; using an arbitrary-precision library would help with that.}

If you're determined to make this work, however, you have to keep the following in mind:

1. You cannot compute fibseq[i] unless fibseq[i-1] and fibseq[i-2] have already been computed; you will need to use a condition variable to pause execution of thread i until threads i-1 and i-2 have completed;

2. You have a race condition where main is updating the value of i while the threads are trying to use the value of i at the same time. You could use a mutex to synchronize accesses of i, but honestly a better solution would be to pass the value of i as an argument to the thread (passing the address won't help; you'll have the same synchronization issue).