Mapreduce框架求Pi值的思路

关于在mapreduce框架上求近似Pi的值，hadoop源码包的example中源代码，在这里只是简单写写学习笔记

 

首先说下大概思路：

这个图大家在网上肯定见都见过

 

正方形的面积 As = (2r)*（2r）也就是 4r*r. 内切圆形的面积 Ac = pi * r*r.  
pi = Ac / r*r
As = 4r*r
r*r= As / 4
pi = 4 * Ac / As

所以最后求pi 的近似值就可以通过求圆的面积与正方形的面积的比值即可，

hadoop中example的实现的思想就是 在整个正方形的内取随机点，然后计算出在内切圆内的点的个数比除以总体的随机点的个数。这个值在乘以4即可近似求出PI的近似值 ，

因为是随机点  有一定的概率行，所以是求近似值。

概算法一个重要难点就是这个随机点的如何生成，采用java自带的Random函数显然不合适，mapreduce采用的是Halton随机点生成算法，他就是才单位正方形内（1,1）内生若干个数据组，该算法需要一个基础值

比如，以2作为基数，那么得到的序列就是将(0,1）区段反复二分：

1/2, 1/4, 3/4, 1/8, 5/8, 3/8, 7/8, 1/16, 9/16

 

实现的伪代码如下：
   FUNCTION (index, base)
   BEGIN
       result = 0;
       f = 1 / base;
       i = index;
       WHILE (i > 0)
       BEGIN
           result = result + f * (i % base);
           i = FLOOR(i / base);
           f = f / base;
       END
       RETURN result;
   END
 

 

这样就得到一组随机的点，

接下来mapreduce要做的工作就是分布这些生成的随机点到各个map任务中区，

而map要做的就是计算这些点实在圆内还是圆外：

final double x = point[0] - 0.5;
		        final double y = point[1] - 0.5;
		        if (x*x + y*y > 0.25) {
		          numOutside++;
		        } else {
		          numInside++;
		        }

 (0.5,0.5)就是圆心的坐标，然后计算随机点到圆心点 两点之间的距离  与半径进行比较，最后计数圆内点的个数

 

然后用一个reduce任务对各个map产生的计数进行全局的统计，并作最后的计算。