文档章节

3月14日圆周率日—使用并行计算求圆周率π

fourinone
 fourinone
发布于 2013/03/14 15:34
字数 1466
阅读 5336
收藏 118

关于圆周率大家再熟悉不过了:
我们从课本上学习到早在一千多年前,祖冲之将圆周率计算到3.1415926到3.1415927之间…计算机诞生后,计算圆周率被用来检测计算机的硬件性能,昼夜燃烧cpu看会不会出问题…另外一些人也想看看这个无限延伸的神秘数字背后是否有规律,能发现一些宇宙的秘密…

 提起圆周率,不能不提及Fabrice Bellard,他被认为是一位计算机天才,在业界有着重要的影响。1996年他编写了一个简洁但是完整的C编译器和一个Java虚拟机Harissa。Fabrice Bellard发明的TinyCC是GNU/Linux环境下最小的ANSI C语言编译器,是目前号称编译速度最快的C编译器。Fabrice Bellard杰作众多且涉及广泛,1998年编写了一个简洁的OpenGL实现TinyGL,2003年开发了Emacs克隆QEmacs,2005年还设计了一个廉价的数字电视系统。

Fabrice Bellard使用一台普通的台式电脑,完成了冲击由超级计算机保持的圆周率运算记录的壮举,他使用台式机将圆周率计算到了小数点后2.7万亿位,超过了由目前排名世界第47位的T2K Open超级计算机于去年8月份创造的小数点后2.5万亿位的记录。

Bellard使用的电脑是一台基于2.93GHz Core i7处理器的电脑,这部电脑的内存容量是6GB,硬盘则使用的是五块RAID-0配置的1.5TB容量的希捷7200.11,系统运行64位Red Hat Fedora 10操作系统,文件系统则使用Linux的ext4.

这次计算出来的圆周率数据占去了1137GB的硬盘容量,Bellard花了103天的时间计算出了这样的结果。

计算圆周率的方法有很多种:
微积分割圆法求:


或者利用便于计算机计算的丘德诺夫斯基公式法求:



不过这些计算方法都比较复杂,难以让读者理解和使用并行计算来求,所幸数学上的泰勒级数是个好东西,它将微积分的东西改成用无限级数来表示,这样很容易进行并行计算分解:

π=4*∑(-1)^n+1/(2n-1) 或者写为: π=4*( 1-1/3+1/5-1/7+…)
也可以得到:πn =πn-1+(-1)^n+1/(2n-1),也就是可以通过迭代前面的π值去求当前π值。


我们根据上面公式先写个单机程序来求:
public class PiTest
{
	public static void main(String[] args)
	{
		double pi=0.0;
		for(double i=1.0;i<1000000001d;i++){
			pi += Math.pow(-1,i+1)/(2*i-1);
		}
		System.out.println(4*pi);
	}
}

运行以上程序,并对照pi的标准值:3.141592653589793238462643383279…
如果i<10000,得到pi = 3.141 6926635905345 (从红色部分以后不精确了)
如果i<1000000,得到pi = 3.14159 36535907742 (从红色部分以后不精确了)
如果i<1000000000,得到pi = 3.14159265 25880504(从红色部分以后不精确了)
……
可以看到,当迭代的轮数越大,求出的π值越精确。

由于是无限累加,我们可以很容易改成并行程序求解,比如i=4n,可以分成4段并行求解,再将4部分和合并起来得到最终π值。假设我们有4台计算机,并行计算设计如下: 

 
我们这里通过fourinone提供的各种并行计算模式去设计,第一次使用可以参考 分布式计算上手demo指南,开发包下载地址: http://code.google.com/p/fourinone/

程序实现:
PiWorker:是一个π计算工人实现,我们可以看到它通过命令行输入一个计算π值的起始值和结束值,我们同时启动4个PiWorker实例,启动时指定不同的起始结束参数。

PiCtor:是一个π计算包工头实现,它的实现很简单,获取到线上工人后,通过doTaskBatch进行阶段计算,等待每个工人计算完成后,将各工人返回的π计算结果合并累加。

运行步骤:
1、启动ParkServerDemo(它的IP端口已经在配置文件指定)
java -cp fourinone.jar; ParkServerDemo


2、运行4个PiWorker,将迭代100,000,000轮的计算拆分到4个工人并行完成,这里方便演示是在同一台机器上,现实应用中可以在多台计算机上完成。
java  -cp fourinone.jar; PiWorker localhost 2008 1 250000000
java  -cp fourinone.jar; PiWorker localhost 2009 250000000 500000000
java  -cp fourinone.jar; PiWorker localhost 2010 500000000 750000000
java  -cp fourinone.jar; PiWorker localhost 2011 750000000 100000000


3、运行PiCtor
java  -cp fourinone.jar; PiCtor

 
可以看到,4个工人实例在同台机器并行完成计算π值的时间为29秒,如果是运行单机程序PiTest完成的时间在45秒,精准度都是到小数点后8位“3.14159265”,但是耗时上有明显差距,如果多机多实例,效率还会进一步提升,并行计算性能提升分析可以参考“使用并行计算大幅提升递归算法效率”。

完整demo源码如下:
// ParkServerDemo
import com.fourinone.BeanContext;
public class ParkServerDemo
{
	public static void main(String[] args)
	{
		BeanContext.startPark();
	}
}

//PiWorker

import com.fourinone.MigrantWorker;
import com.fourinone.WareHouse;

public class PiWorker extends MigrantWorker
{
	public double m=0.0,n=0.0;
	
	public PiWorker(double m, double n){
		this.m = m;
		this.n = n;
	}
	
	public WareHouse doTask(WareHouse inhouse)
	{
		double pi=0.0;
		for(double i=m;i<n;i++){
			pi += Math.pow(-1,i+1)/(2*i-1);
		}
		
		System.out.println(4*pi);
		inhouse.setObj("pi",4*pi);

		return inhouse;
	}
	
	public static void main(String[] args)
	{
		PiWorker mw = new PiWorker(Double.parseDouble(args[2]),Double.parseDouble(args[3]));
		mw.waitWorking(args[0],Integer.parseInt(args[1]),"PiWorker");
	}
}

//PiCtor
import com.fourinone.Contractor;
import com.fourinone.WareHouse;
import com.fourinone.WorkerLocal;
import java.util.Date;

public class PiCtor extends Contractor
{
	public WareHouse giveTask(WareHouse inhouse)
	{
		WorkerLocal[] wks = getWaitingWorkers("PiWorker");
		System.out.println("wks.length:"+wks.length);
		
		WareHouse[] hmarr = doTaskBatch(wks, inhouse);
		
		double pi=0.0;
		for(WareHouse result:hmarr){
			pi = pi + (Double)result.getObj("pi");
		}
		
		System.out.println("pi:"+pi);
		return inhouse;
	}
	
	public static void main(String[] args)
	{
		PiCtor a = new PiCtor();
		long begin = (new Date()).getTime();
		a.giveTask(new WareHouse());
		long end = (new Date()).getTime();
		System.out.println("time:"+(end-begin)/1000+"s");
		a.exit();
	}
}

 

© 著作权归作者所有

共有 人打赏支持
fourinone

fourinone

粉丝 273
博文 43
码字总数 49961
作品 1
杭州
私信 提问
加载中

评论(25)

七液
七液

引用来自“羊半仙”的评论

能用OpenCL加速不?

这个只是计算加速,而不是算法加速在牛逼的计算机计算O(n2)n超大的话,也比不了老式计算机的O(1).
瑾锋少侠
瑾锋少侠

引用来自“红尘一人”的评论

我只想问 这东西计算到几个亿后面 中毛用啊 实际计算 能取10位都不是一般的程序了

一般是拿这个做计算机的性能测试的。
Administra
Administra
Mathematica一个函数N[Pi, 10^6](显示π的前100万位)用个人电脑也不到1s
沙发迪
沙发迪
还可以啊,不错
永远对你好
永远对你好

引用来自“红尘一人”的评论

我只想问 这东西计算到几个亿后面 中毛用啊 实际计算 能取10位都不是一般的程序了

所做的一切都没用。前面提到的他哪些做得东西你看来估计都是重复造轮子。所以这种想法太多导致咱们国家计算机上没啥建树。
风林火山
风林火山
他更牛的是 ffmpeg的项目创建者
scugxl
scugxl

引用来自“CloudLee”的评论

可以用Hadoop挑战下

hadoop自带的demo里面就有额!
红尘一人
红尘一人

引用来自“沉默的拖把”的评论

引用来自“红尘一人”的评论

引用来自“nhm”的评论

引用来自“红尘一人”的评论

我只想问 这东西计算到几个亿后面 中毛用啊 实际计算 能取10位都不是一般的程序了

如果是宇宙中计算星系中某个数据用到pi,你看有没有用

我们所谓的科学 都是构建在一个不完整的模型之上的 或者说本身就可能是错误的 在这样一个基础上 所谓精确 多少都有点自欺欺人 ;再者 光计算这个pi就花了这么久 耗了这么大空间 用这个pi来计算 不是很滑稽么 等你计算出来 人家或者因为什么陨石 什么太阳风 早就偏差了

哇 这个人好聪明啊

。。。。。。。。。。。。。。。(省略2.7万亿位)
沉默的拖把
沉默的拖把

引用来自“红尘一人”的评论

引用来自“nhm”的评论

引用来自“红尘一人”的评论

我只想问 这东西计算到几个亿后面 中毛用啊 实际计算 能取10位都不是一般的程序了

如果是宇宙中计算星系中某个数据用到pi,你看有没有用

我们所谓的科学 都是构建在一个不完整的模型之上的 或者说本身就可能是错误的 在这样一个基础上 所谓精确 多少都有点自欺欺人 ;再者 光计算这个pi就花了这么久 耗了这么大空间 用这个pi来计算 不是很滑稽么 等你计算出来 人家或者因为什么陨石 什么太阳风 早就偏差了

哇 这个人好聪明啊
贝才
贝才
我看着就是天书阿
π-Day的庆祝方式——用蒙特卡洛方法近似求π

2009年,在麻省理工学院的首先倡议下,美国众议院正式通过一项无约束力决议(Non-binding resolution)(HRES 224),将每年的3月14号设定为“圆周率日”即“Pi Day”。2011年,国际数学协会...

qq_33414271
2018/03/14
0
0
#3.14 Piday#我的圆周率日

本文来自网易云社区 作者:马宝 圆周率日(Pi day) 2011年国际数学协会正式宣布,将每年的3月14日设为国际数学节,来源则是中国古代数学家祖冲之的圆周率。“终极”圆周率日是1592年3月14日...

网易云
2018/09/25
0
0
新世界纪录:谷歌将圆周率计算到 31 万亿位

为了挑战更精确的圆周率,谷歌工程师 Emma Iwao 在25台谷歌云的虚拟机上,执行专为圆周率设计的算法,计算出31万亿数字的圆周率。 3.1415926,相信不少人都背诵过这串数字,并将它代入算式中...

段段段落
03/16
0
0
Objective-c常用的函数

来自:http://blog.sina.com.cn/s/blog_71715bf80101bnvn.html 介绍一下Objective-c常用的函数,常数变量 算术函数 【算术函数】 函数名 说明 int rand() 随机数生成。 (例) srand(time(n...

水一样的人儿
2016/07/06
15
0
急急急急急在线等CUDA问题

采用积分法计算圆周率/π的值。其计算原理是:在[0,1]范围内积分1/(1+x*x) /* 串行计算PI的程序,基本思想为:将积分区间均分为num小块,将每小块的面积加起来。 */ float cpuPI(int num){ f...

ldl123292
2013/01/17
313
1

没有更多内容

加载失败,请刷新页面

加载更多

关于360插件化Replugin Activity动态修改父类的字节码操作

近期在接入360插件化方案Replugin时,发现出现崩溃情况。 大概崩溃内容如下: aused by: java.lang.ClassNotFoundException: Didn't find class "x.x.x.xActivity" on path: 我自己在插件代码......

Gemini-Lin
21分钟前
0
0
mybatis缓存的装饰器模式

一般在开发生产中,对于新需求的实现,我们一般会有两种方式来处理,一种是直接修改已有组件的代码,另一种是使用继承方式。第一种显然会破坏已有组件的稳定性。第二种,会导致大量子类的出现...

算法之名
昨天
15
0
单元测试

右键方法 Go To --> Test,简便快速生成测试方法。 相关注解 @RunWith(SpringRunner.class) 表示要在测试环境中跑,底层实现是 jUnit测试工具。 @SpringBootTest 表示启动整个 Spring工程 @A...

imbiao
昨天
4
0
欧拉公式

欧拉公式表达式 欧拉公式的几何意 cosθ + j sinθ 是个复数,实数部分也就是实部为 cosθ ,虚数部分也就是虚部为 j sinθ ,对应复平面单位圆上的一个点。 根据欧拉公式和这个点可以用 复指...

sharelocked
昨天
5
0
burpsuite无法抓取https数据包

1.将浏览器和burpsuite的代理都设置好 2.在浏览器地址栏输入: http://burp 3.下载下面的证书,并将证书导入浏览器 cacert.der

Frost729
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部