【多核程序设计】蒙特卡洛算法求 pi 背景知识： 蒙特卡洛是摩纳哥公国第一大城市，与澳门、美国拉斯维加斯并称世界三大赌城。位于地中 海沿岸，首都摩纳哥之北，建于阿尔卑斯山脉突出地中海的悬崖之上。景色优美，是地中海 地区旅游胜地。市内建有豪华的旅馆、俱乐部、歌剧院、商店、游泳池、温泉浴室、运动场 等娱乐设施 。城内开设有蒙特卡洛大赌场。赌场建于 1865 年，为双层楼建筑，上有钟楼、 塔厅和拱形亭阁，还饰以若干人物雕塑，庭前棕榈树成行，还辟有花园，旁边有大酒店和酒 吧间。整个城市在旺季时，约有赌场 70 多个，约有赌室 3500 间左右。蒙特卡罗赌场由国家 经营。当地的其他活动，许多也带有赌博色彩。游客住的旅店房间，有抽奖的号码，中奖的 免付部分房费。早餐的牛奶麦片粥里，如遇上金属牌子 ，亦可领奖。该城只有 1 万人口， 但每天报纸销量可达 100 万份 ，因为报纸上都印有可能得奖的号码。游客最后离境，购买 的车票上也印有彩票号码，于离境前开彩。经营赌业是摩纳哥的主要经济来源，每年都从赌 业中收取高额外汇利润。 蒙特卡洛算法简单描述： 以概率和统计理论方法为基础的一种计算方法。将所求解的问题同一定的概率模型相联系， 用计算机实现统计模拟或抽样，以获得问题的近似解。比如，给定 x=a，和 x=b，你要求某 一曲线 f 和这两竖线，及 x 轴围成的面积，你可以起定 y 轴一横线 y=c 其中 c>=f(a) and c>=f(b)，很简单的，你可以求出 y=c,x=a,x=b,及 x 轴围成的矩形面积，然后利用随机参生 生大量在这个矩形范围之类的点，统计出现在曲线上部点数和出现在曲线下部点的数目，记 为：doteUpCount,nodeDownCount,然后所要求的面积可以近似为 doteDownCounts 所占比例* 矩形面积。 问题描述： 在数值积分法中，利用求单位圆的 1/4 的面积来求得 Pi/4 从而得到 Pi。单位圆的 1/4 面积是 一个扇形，它是边长为 1 单位正方形的一部分。只要能求出扇形面积 S1 在正方形面积 S 中 占的比例 K=S1/S 就立即能得到 S1，从而得到 Pi 的值。怎样求出扇形面积在正方形面积中 占的比例 K 呢？一个办法是在正方形中随机投入很多点，使所投的点落在正方形中每一个 位置的机会相等看其中有多少个点落在扇形内。将落在扇形内的点数 m 与所投点的总数 n 的比 m/n 作为 k 的近似值。P 落在扇形内的充要条件是 x^2+y^2<=1。 算法： 1、确定产生点 n 的个数和缓冲区 m（m<=n）的值，声明互斥锁 2、某一线程进入临界区，上锁 3、该线程一次性生成 m 个数，其他线程若想进入则挂起等待 4、该线程退出临界区，解锁 ，开始对刚才生成的随机点进行计算 5、重复 2-4 步，直至每个线程均完成对所要求点的操作 6、统计 COUNTi 的值 7、计算的值 

程序代码： //并行算法 #include #include #include #include #include #include long cs=0; //循环次数 long count=0; //主线程有效次数 long count_thread=0; //thread 线程有效次数 struct timeval start, finish; //定义开始结束时间 double diffsec,diffusec; long t;//每次生成数据数量 pthread_mutex_t mutex; long double *data_thread,*data_main; //void *thread(void *) void thread(void) { int i=0,j=0; double x,y; //long double *data_thread; long double data_thread[t]; for(i=0;i

} //主线程计算量为总数的一半 int main(void) { printf("Please input the number:"); scanf("%d",&cs); cs=cs*1000000; printf("Please input the number for generating the data once:"); scanf("%d",&t); t=t*100000; pthread_t id; int ret; srand( (unsigned)time( NULL ) ); pthread_mutex_init(&mutex,NULL);//声明互斥锁 ret=pthread_create(&id,NULL,(void *)thread,NULL); //创建 thread 线程 gettimeofday(&start,NULL); //记录开始时间 int i=0,j=0; double x,y; long double data_main[t]; for(i=0;i

printf("Cost time=%f second \n",diffsec); printf("roop times=%d \n",cs); printf("effective times=%d \n",count); printf("pi= %f \n",4*(double)count/(double)cs); return(0); }