Skip to content

Instantly share code, notes, and snippets.

@gyng
Created March 11, 2014 17:02
Show Gist options
  • Save gyng/f50ef749fb34df45cc70 to your computer and use it in GitHub Desktop.
Save gyng/f50ef749fb34df45cc70 to your computer and use it in GitHub Desktop.
amazing revolutionary parallel fibonacci algorithm do not steal
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
#include <errno.h>
void handle_error(void);
int main(int argc, char **argv)
{
int n = atoi(argv[1]);
int superdaddy = getpid();
int p1[2];
int p2[2];
int *pipes[2] = { p1, p2 };
int savedoutput, result1, result2, result, cpid;
int output = STDOUT_FILENO;
int i;
// Trivial cases
if (n <= 2)
{
printf("Result: 1\n");
return 0;
}
fib:
if (n <= 1)
{
// Base case
if (write(output, &n, sizeof(n)) < 0) handle_error();
return 0;
}
// Pipe to parent, write fib(n) into this
savedoutput = output;
// Fork twice, once for fib(n-1) and another for fib(n-2)
for (i = 0; i < 2; i++)
{
n--;
if (pipe(pipes[i]) < 0) handle_error();
output = pipes[i][1];
if ((cpid = fork()) == 0)
{
// In child process
// Close pipe reading ends and perform recursion
if (close(pipes[i][0]) < 0) handle_error();
goto fib;
}
else if (cpid < 0)
handle_error();
}
// Close pipe outputs
if (output == p1[1] && close(p1[1]) < 0) handle_error();
if (output == p2[1] && close(p2[1]) < 0) handle_error();
// fib(n) = fib(n-1) + fib(n-2)
if (read(p1[0], &result1, sizeof(result1)) < 0) handle_error();
if (read(p2[0], &result2, sizeof(result2)) < 0) handle_error();
result = result1 + result2;
if (getpid() == superdaddy)
printf("Result: %d\n", result);
else if (write(savedoutput, &result, sizeof(result)) < 0)
handle_error();
wait(NULL);
wait(NULL);
return 0;
}
void handle_error(void)
{
perror(NULL);
exit(EXIT_FAILURE);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment