蒙特卡洛算法求 pi项目(1)

多核软件设计——蒙特卡洛算法求 项目

选自华南理工大学多核课程，由简单修改（原因是部分程序编译错误）。

一、问题描述

蒙特卡洛算法可理解为通过大量实验，模拟实际行为，来收集统计数据。本例中，算法随机产生一系列点，模拟这些点落在如下图所示的正方形区域内的情况。其几何解释如下

 

 

 

图1

 

如图1所示，正方形边长为1，左下顶点与原点重合，两边分别与x，y轴重合。曲线为1/4圆弧，圆心位于原点，与正方形左下定点重合，半径为1。正方形面积S₁=1，圆弧内面积S₂= 。算法模拟大量点随机落在此正方形区域内，落在圆弧内的点的数量（n₂）与点的总数（n₁）的比例与面积成正比关系。即

                                                                   （1）

由此可得                                   

                                   （2）

因此，只要计算出落在圆弧内的点的数量在点总数中所占的比例，就能求出 的值。

由图1可知，所有点均落在正方形范围内，因此点的x坐标满足

。又，当点落在圆弧范围内，则点的二维坐标关系满足。检验每一个点是否满足此关系即可判定改点是否落在圆弧内。

 

二、串行算法描述

本项目中使用了标准C语言库中的产生随机数函数。该函数原型为：

 

int rand( void );

此函数产生随机数列，每次调用时均返回0到RAND_MAX之间的一个整数。

void srand( unsigned int seed );

此函数为rand（）函数所生成的伪随机数序列设置起始点，使之产生不同的伪随机数。

算法：

      产生2n个随机数据，范围[0，1]，对每个数据点计算其坐标是否满足 ，统计满足此关系的点的数量count，则

示例见附件Serial.c。

 

#include

#include

#include

#include

#include

 

int main()

{

    printf("please input the number:");

    long cs=0;

    scanf("%d",&cs); //输入产生点的个数 

    cs=cs*1000000;

    srand( (unsigned)time( NULL ) ); //产生种子 

    struct timeval start, finish; //定义开始结束时间

    double diffsec,diffusec;       

    int i=0;

    double x,y;

    long count=0; //有效次数

    gettimeofday(&start,NULL); //记录开始时间       

    for(i=0;i循环体

    {                      

        x=(long double)rand()/(long double)RAND_MAX;

        y=(long double)rand()/(long double)RAND_MAX;       

        if((x*x+y*y)<=1)

            count++;

    }

   

    gettimeofday(&finish,NULL); //记录结束时间

    diffsec=(double)finish.tv_sec-start.tv_sec;

    diffusec=(double)(finish.tv_usec-start.tv_usec)/(double)1000000;

    diffsec+=diffusec;

    //输出结果  

    printf("Cost time=%f second \n",diffsec);  

    printf("loop times=%d \n",cs);

    printf("effective times= %d \n", count);

    printf("pi=%f \n",4*(double)count/(double)cs);

    return (0);

}