#include <stdlib.h>
#include <stdio.h>
#include <mpi.h>
#include <math.h>

int main(int argc, char* argv[ ]) {

   // MPI bookkeeping variables
   int numP;
   int pid;
   MPI_Request sendR, recvR;
   MPI_Status sendS, recvS;

   // MPI Initialization 
   MPI_Init(&argc, &argv); 
   MPI_Comm_size(MPI_COMM_WORLD, &numP);
   MPI_Comm_rank(MPI_COMM_WORLD, &pid);

   int log2NumP = (int) log2(numP);
   int rVal; // received value in reduction
   int sVal = pid; // sent value in reduction

   // time the MPI reduction
   double t = MPI_Wtime( );
   MPI_Reduce(&sVal, &rVal, 1, MPI_INTEGER, MPI_SUM, 0, MPI_COMM_WORLD);
   t = MPI_Wtime( ) - t;
   
   if (pid == 0) {
      printf("MPI reduction time on pid %d is %f\n", pid, t);
      printf("MPI reduction value is %d\n", rVal);
   }

   // time our reduction
   t = MPI_Wtime( );
   int level = 1;
   for (int i = 1; i < log2NumP+1; i++) {
      if (pid%(2*level) == 0) { // a receiver
         MPI_Irecv(&rVal, 1, MPI_INTEGER, pid+level, 0, MPI_COMM_WORLD, &recvR);
      }

      if (pid%(2*level) == level) { // a sender
         MPI_Isend(&sVal, 1, MPI_INTEGER, pid-level, 0, MPI_COMM_WORLD, &sendR);
      }
         
      if (pid%(2*level) == 0) { // a receiver
         MPI_Wait(&recvR, &recvS);
         sVal += rVal;
      }

      if (pid%(2*level) == level) { // a sender
         MPI_Wait(&sendR, &sendS);
      }
      level *= 2;
   }

   t = MPI_Wtime( ) - t;
   
   if (pid == 0) {
      printf("pid %d time for my reduction on %d processes is  %f, the value is %d\n", pid, numP, t, sVal);
   }
}