##### Site index · List index
Message view
Top
From szets...@apache.org
Date Fri, 10 Jul 2009 23:00:12 GMT
Author: szetszwo
Date: Fri Jul 10 23:00:12 2009
New Revision: 793136

URL: http://svn.apache.org/viewvc?rev=793136&view=rev
Log:
MAPREDUCE-742. Fix output messages and java comments in the Pi related examples.

Modified:

==============================================================================
+++ hadoop/mapreduce/trunk/CHANGES.txt Fri Jul 10 23:00:12 2009
@@ -188,4 +188,6 @@
MAPREDUCE-153. Fix timeout in TestJobInProgressListener. (Amar

+    MAPREDUCE-742. Fix output messages and java comments in the Pi related
+    examples.  (szetszwo)

==============================================================================
(original)
Fri Jul 10 23:00:12 2009
@@ -50,8 +50,19 @@

/**
- * A map/reduce program that uses Bailey-Borwein-Plouffe to compute exact digits
- * of Pi.
+ * A map/reduce program that uses Bailey-Borwein-Plouffe to compute exact
+ * digits of Pi.
+ * This program is able to calculate digit positions
+ * lower than a certain limit, which is roughly 10^8.
+ * If the limit is exceeded,
+ * the corresponding results may be incorrect due to overflow errors.
+ * For computing higher bits of Pi, consider using distbbp.
+ *
+ * Reference:
+ *
+ * [1] David H. Bailey, Peter B. Borwein and Simon Plouffe.  On the Rapid
+ *     Computation of Various Polylogarithmic Constants.
+ *     Math. Comp., 66:903-913, 1996.
*/
public class BaileyBorweinPlouffe extends Configured implements Tool {
public static final String DESCRIPTION
@@ -423,7 +434,11 @@
// static fields and methods for Bailey-Borwein-Plouffe algorithm. //
/////////////////////////////////////////////////////////////////////

-  // TODO: the following value is conservative, should be at lease 2^28.
+  /** Limitation of the program.
+   * The program may return incorrect results if the limit is exceeded.
+   * The default value is 10^8.
+   * The program probably can handle some higher values such as 2^28.
+   */
private static final long IMPLEMENTATION_LIMIT = 100000000;

private static final long ACCURACY_BIT = 32;

==============================================================================
Jul 10 23:00:12 2009
@@ -49,10 +49,12 @@
"A map/reduce program that writes 10GB of random textual data per node.");
pgd.addClass("sort", Sort.class, "A map/reduce program that sorts the data written
by the random writer.");
-                   "A map/reduce program that estimates Pi using quasi-Monte Carlo method.");
+
+      //Pi computation examples
+
"A map/reduce tile laying program to find solutions to pentomino problems.");

==============================================================================
10 23:00:12 2009
@@ -40,8 +40,23 @@

/**
- * A Map-reduce program to estimate the value of Pi
- * using quasi-Monte Carlo method.
+ * A map/reduce program that estimates the value of Pi
+ * using a quasi-Monte Carlo (qMC) method.
+ * Arbitrary integrals can be approximated numerically by qMC methods.
+ * In this example,
+ * we use a qMC method to approximate the integral $I = \int_S f(x) dx$,
+ * where $S=[0,1)^2$ is a unit square,
+ * $x=(x_1,x_2)$ is a 2-dimensional point,
+ * and $f$ is a function describing the inscribed circle of the square $S$,
+ * $f(x)=1$ if $(2x_1-1)^2+(2x_2-1)^2 <= 1$ and $f(x)=0$, otherwise.
+ * It is easy to see that Pi is equal to $4I$.
+ * So an approximation of Pi is obtained once $I$ is evaluated numerically.
+ *
+ * There are better methods for computing Pi.
+ * We emphasize numerical approximation of arbitrary integrals in this example.
+ * For computing many digits of Pi, consider using bbp.
+ *
+ * The implementation is discussed below.
*
* Mapper:
*   Generate points in a unit square
@@ -52,12 +67,14 @@
*
* Let numTotal = numInside + numOutside.
* The fraction numInside/numTotal is a rational approximation of
- * the value (Area of the circle)/(Area of the square),
+ * the value (Area of the circle)/(Area of the square) = $I$,
* where the area of the inscribed circle is Pi/4
* and the area of unit square is 1.
- * Then, Pi is estimated value to be 4(numInside/numTotal).
+ * Finally, the estimated value of Pi is 4(numInside/numTotal).
*/
public class PiEstimator extends Configured implements Tool {
+  static final String DESCRIPTION
+      = "A map/reduce program that estimates Pi using a quasi-Monte Carlo method.";
/** tmp directory for input/output */
static private final Path TMP_DIR = new Path(
PiEstimator.class.getSimpleName() + "_TMP_3_141592654");

==============================================================================
10 23:00:12 2009
@@ -32,15 +32,21 @@

/**
- * The main class for launching DistSum jobs to compute Pi.
- * The steps are:
+ * A map/reduce program that uses a BBP-type method to compute exact
+ * binary digits of Pi.
+ * This program is designed for computing the n th bit of Pi,
+ * for large n, say n >= 10^8.
+ * For computing lower bits of Pi, consider using bbp.
+ *
+ * The actually computation is done by DistSum jobs.
+ * The steps for launching the jobs are:
*
* (1) Initialize parameters.
* (2) Create a list of sums.
* (3) Read computed values from the given local directory.
* (4) Remove the computed values from the sums.
* (5) Partition the remaining sums into computation jobs.
- * (6) Summit the computation jobs to a cluster.
+ * (6) Submit the computation jobs to a cluster and then wait for the results.
* (7) Write job outputs to the given local directory.
* (8) Combine the job outputs and print the Pi bits.
*/

==============================================================================
23:00:12 2009
@@ -97,7 +97,7 @@
return n + "ms";

final StringBuilder b = new StringBuilder();
-    final int millis = (int)n % 1000;
+    final int millis = (int)(n % 1000L);
if (millis != 0)
b.append(String.format(".%03d", millis));
if ((n /= 1000) < 60)


Mime
View raw message