#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include "mpi.h"

// a)
// Returns the gcd of 2 numbers
int gcd(int a, int b){
    while(a != b)
        if(a > b)
      a -= b;
    else
      b -= a;

    return a;
}

// b) Implement the addreduce pattern
int main(int argc, char** argv) {

   int size, rank;
   MPI_Status status;

   MPI_Init(&argc, &argv);

   MPI_Comm_size(MPI_COMM_WORLD, &size);
   MPI_Comm_rank(MPI_COMM_WORLD, &rank);

   int shift = 1;

   // generate 2 random integers per process
   srand(time(NULL));
   int a = rank * 97 * rand(); // a always stays fix per process, will be the local result
   int b = rank * 311 * rand(); // b will be received from other processes (except in the first round)

   int num_rounds = size; // change this value to set how many rounds the algorithms will be executed.
                          // Standard value is: size
   while(num_rounds > 0) {
     int result = gcd(a, b);

     MPI_Status status;
   printf("Process: %d sends to:%d and receives from:%d\n",rank,(rank + shift) % size,(rank - shift / 2) % size);
     MPI_Sendrecv(&result, 1, MPI_INT, (rank + shift) % size    , 0,
                  &b     , 1, MPI_INT, (rank - shift / 2) % size, 0, MPI_COMM_WORLD, &status);
     a = result;
     shift *= 2;
     num_rounds--;
   }

   // do sth with the results e.g. print it:
   printf("Process %d result is: %d\n", rank, a);

   MPI_Finalize();

   return 0;
}