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

/*
SOMMA AD ALBERO
sia N numero di processi
sia M la prima potenza di 2 >= N
allo step I dell'algoritmo (I comincia da 1) i processi per cui (M - rank) è un multiplo di 2 alla I 
sommano i contributi dei processi rank + 2 alla I-1 
*/

int main(int argc, char *argv[])
{
  
  int myid, numprocs, i, d, sum, val, proc;
  MPI_Status status;
  int M=1;
  
  
  MPI_Init(&argc,&argv);
  MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
  MPI_Comm_rank(MPI_COMM_WORLD,&myid);
  
  /* M: prima potenza di 2 maggiore di numprocs */
  while (M < numprocs)
    M *= 2;
  
  i = M - myid;
  d = 1;
  sum = myid;
  
  while (i % 2 == 0)
  {
    proc = myid + d;
    if (proc < numprocs)
    {
	MPI_Recv(&val, 1, MPI_INT, proc, 0, MPI_COMM_WORLD, &status);
	sum += val;
    }
    i /= 2;
    d *= 2;
  }
  if (myid == 0)
  {
      printf("Sum = %d\n", sum);
  }
  else
  {
      proc = myid - d;
      printf("I'm %d and I send a file to proc %d\n", myid, proc); 
      MPI_Send(&sum, 1, MPI_INT, proc, 0, MPI_COMM_WORLD);
  }
  MPI_Finalize();  
}
