#include "mpi.h"
#include <cstdio>
#include <cstdlib>


int *initial(int *a, int d)                       //初始化
{
    a = (int *)malloc(sizeof(int) * d);
    for(int i = 0; i < d; i++)
    {
        a[i] = 0;
    }
    return a;
}

void divide(int *a, int d, int num)         //求倒數,num為欲求倒數的數
{
    int i = 0, n = 1;       //n為被除數,且=1
    while(i < d)            //d為小數點後的位數
    {
        if(n==0)
        {
            break;
        }
        while(n < num)          //除數大於被除數(商為0),則跳到下一位計算
        {
            a[i] = 0;
            n *= 10;
            i++;
        }
        a[i] = n/num;
        n = n - a[i] * num;
        n *= 10;
        i++;
    }
}

void add(int *a, int *b, int d)
{
    int i = d - 1;
    while(i >= 0)               //元素各自相加
    {
        b[i] = a[i] + b[i];
        i--;
    }
    i = d - 1;
    while(i >= 0)       //進位
    {
        if(b[i] >= 10)
        {
            if(i != 0)      //我假設元素0為整數部分，因此整數部分暫時不需要考慮相加
            {
                b[i - 1] += b[i] / 10;
                b[i] %= 10;
            }
        }
        i--;
    }
}

int main(int argc, char *argv[])
{
    double begintime, endtime;
    int n, d;       //n為加到某數的上限，d為小數後幾位
    int myid, numprocs;         //myid處理器編號，numprocs處理器數量
    int *temp, *proctemp, *result;          //用來存數字的陣列
    MPI_Init(&argc, &argv);
    MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
    MPI_Comm_rank(MPI_COMM_WORLD, &myid);
    if(myid == 0)
    {
        printf("Enter n:");
        scanf("%d", &n);
        printf("Enter d:");
        scanf("%d", &d);
    }
    begintime = MPI_Wtime();
    MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);   //將n, d傳給每個處理器
    MPI_Bcast(&d, 1, MPI_INT, 0, MPI_COMM_WORLD);
    d += 8;                                         //多取8位使得數字變動較小(小數點後d位才不會有誤差)
    temp=initial(temp, d);
    proctemp=initial(proctemp, d);
    result=initial(result, d);
    for(int i = 1 + myid; i <= n; i += numprocs)            //倒數除法存到temp後再做加法存到proctemp
    {
        divide(temp, d, i);
        add(temp, proctemp, d);
        for(int i = 0; i < d; i++)
        {
            temp[i] = 0;
        }
    }
    MPI_Reduce(proctemp, result, d, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);       //把各個處理器proctemp陣列的元素分別加到result陣列
    int i = d - 1;
    while(i >= 0)       //進位
    {
        if(result[i] >= 10)
        {
            if(i != 0)      //我假設元素0為整數部分，因此整數部分暫時不需要考慮相加
            {
                result[i - 1] += result[i] / 10;
                result[i] %= 10;
            }
        }
        i--;
    }
    d -= 8;                                         //d值減回來
    i = 0;
    endtime = MPI_Wtime();
    MPI_Finalize();
    if(myid == 0){
    printf("The result is:\n");
    while(i <= d)                                   //印出結果
    {
        if(i == 0)
            printf("%3d.", result[0]);
        else
            printf("%d", result[i]);
        if(i%5 == 0)
            printf("\n");
        i++;
    }
    printf("\nThe execution time is %.6f\n", endtime - begintime);
    }
/*  if(myid == 0)
    {
        printf("The result is:\n");
        while(d > 0)                                    //印出結果
        {
            if(i == 0)
                printf("%3d.", result[0]);
            else
                printf("%d", result[i]);
            if(i%5 == 0)
                printf("\n");
            d--;
            i++;
        }
        printf("\nThe execution time is %.6f\n", endtime - begintime);
    }*/
}