Mailing-List: contact core-commits-help@hadoop.apache.org; run by ezmlm
Precedence: bulk
Reply-To: core-dev@hadoop.apache.org
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: svn commit: r746864 - in /hadoop/core/trunk: ./
 src/examples/org/apache/hadoop/examples/ src/test/org/apache/hadoop/examples/
Date: Mon, 23 Feb 2009 02:52:13 -0000
To: core-commits@hadoop.apache.org
From: cdouglas@apache.org
Message-Id: <20090223025213.E84A123888A3@eris.apache.org>

Author: cdouglas
Date: Mon Feb 23 02:52:12 2009
New Revision: 746864

URL: http://svn.apache.org/viewvc?rev=746864&view=rev
Log:
HADOOP-5052. Add an example computing exact digits of pi using the
Bailey-Borwein-Plouffe algorithm. Contributed by Tsz Wo (Nicholas), SZE

Added:
    hadoop/core/trunk/src/examples/org/apache/hadoop/examples/BaileyBorweinPlouffe.java
    hadoop/core/trunk/src/test/org/apache/hadoop/examples/
    hadoop/core/trunk/src/test/org/apache/hadoop/examples/TestBaileyBorweinPlouffe.java
Modified:
    hadoop/core/trunk/CHANGES.txt
    hadoop/core/trunk/src/examples/org/apache/hadoop/examples/ExampleDriver.java

Modified: hadoop/core/trunk/CHANGES.txt
URL: http://svn.apache.org/viewvc/hadoop/core/trunk/CHANGES.txt?rev=746864&r1=746863&r2=746864&view=diff
==============================================================================
--- hadoop/core/trunk/CHANGES.txt (original)
+++ hadoop/core/trunk/CHANGES.txt Mon Feb 23 02:52:12 2009
@@ -43,6 +43,9 @@
 
     HADOOP-5018. Add pipelined writers to Chukwa. (Ari Rabkin via cdouglas)
 
+    HADOOP-5052. Add an example computing exact digits of pi using the
+    Bailey-Borwein-Plouffe algorithm. (Tsz Wo (Nicholas), SZE via cdouglas)
+
   IMPROVEMENTS
 
     HADOOP-4565. Added CombineFileInputFormat to use data locality information

Added: hadoop/core/trunk/src/examples/org/apache/hadoop/examples/BaileyBorweinPlouffe.java
URL: http://svn.apache.org/viewvc/hadoop/core/trunk/src/examples/org/apache/hadoop/examples/BaileyBorweinPlouffe.java?rev=746864&view=auto
==============================================================================
--- hadoop/core/trunk/src/examples/org/apache/hadoop/examples/BaileyBorweinPlouffe.java (added)
+++ hadoop/core/trunk/src/examples/org/apache/hadoop/examples/BaileyBorweinPlouffe.java Mon Feb 23 02:52:12 2009
@@ -0,0 +1,624 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.examples;
+
+import java.io.BufferedOutputStream;
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.io.OutputStream;
+import java.io.PrintStream;
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.hadoop.conf.Configuration;
+import org.apache.hadoop.conf.Configured;
+import org.apache.hadoop.fs.FileSystem;
+import org.apache.hadoop.fs.Path;
+import org.apache.hadoop.io.BytesWritable;
+import org.apache.hadoop.io.IntWritable;
+import org.apache.hadoop.io.LongWritable;
+import org.apache.hadoop.io.Writable;
+import org.apache.hadoop.mapreduce.InputFormat;
+import org.apache.hadoop.mapreduce.InputSplit;
+import org.apache.hadoop.mapreduce.Job;
+import org.apache.hadoop.mapreduce.JobContext;
+import org.apache.hadoop.mapreduce.Mapper;
+import org.apache.hadoop.mapreduce.RecordReader;
+import org.apache.hadoop.mapreduce.Reducer;
+import org.apache.hadoop.mapreduce.TaskAttemptContext;
+import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
+import org.apache.hadoop.util.Tool;
+import org.apache.hadoop.util.ToolRunner;
+
+/**
+ * A map/reduce program that uses Bailey-Borwein-Plouffe to compute exact digits
+ * of Pi.
+ */
+public class BaileyBorweinPlouffe extends Configured implements Tool {
+  public static final String DESCRIPTION
+      = "A map/reduce program that uses Bailey-Borwein-Plouffe to compute exact digits of Pi.";
+
+  private static final String NAME = BaileyBorweinPlouffe.class.getSimpleName();
+
+  //custom job properties
+  private static final String WORKING_DIR_PROPERTY = NAME + ".dir";
+  private static final String HEX_FILE_PROPERTY = NAME + ".hex.file";
+  private static final String DIGIT_START_PROPERTY = NAME + ".digit.start";
+  private static final String DIGIT_SIZE_PROPERTY = NAME + ".digit.size";
+  private static final String DIGIT_PARTS_PROPERTY = NAME + ".digit.parts";
+
+  private static final Log LOG = LogFactory.getLog(BaileyBorweinPlouffe.class);
+
+  /** Mapper class computing digits of Pi. */
+  public static class BbpMapper extends
+      Mapper<LongWritable, IntWritable, LongWritable, BytesWritable> {
+
+    /** Compute the (offset+1)th to (offset+length)th digits. */
+    protected void map(LongWritable offset, IntWritable length,
+        final Context context) throws IOException, InterruptedException {
+      LOG.info("offset=" + offset + ", length=" + length);
+
+      // compute digits
+      final byte[] bytes = new byte[length.get() >> 1];
+      long d = offset.get();
+      for (int i = 0; i < bytes.length; d += 4) {
+        final long digits = hexDigits(d);
+        bytes[i++] = (byte) (digits >> 8);
+        bytes[i++] = (byte) digits;
+      }
+
+      // output map results
+      context.write(offset, new BytesWritable(bytes));
+    }
+  }
+
+  /** Reducer for concatenating map outputs. */
+  public static class BbpReducer extends
+      Reducer<LongWritable, BytesWritable, LongWritable, BytesWritable> {
+
+    /** Storing hex digits */
+    private final List<Byte> hex = new ArrayList<Byte>();
+
+    /** Concatenate map outputs. */
+    @Override
+    protected void reduce(LongWritable offset, Iterable<BytesWritable> values,
+        Context context) throws IOException, InterruptedException {
+      // read map outputs
+      for (BytesWritable bytes : values) {
+        for (int i = 0; i < bytes.getLength(); i++)
+          hex.add(bytes.getBytes()[i]);
+      }
+
+      LOG.info("hex.size() = " + hex.size());
+    }
+
+    /** Write output to files. */
+    @Override
+    protected void cleanup(Context context
+        ) throws IOException, InterruptedException {
+      final Configuration conf = context.getConfiguration();
+      final Path dir = new Path(conf.get(WORKING_DIR_PROPERTY));
+      final FileSystem fs = dir.getFileSystem(conf);
+
+      // write hex output
+      {
+        final Path hexfile = new Path(conf.get(HEX_FILE_PROPERTY));
+        final OutputStream out = new BufferedOutputStream(fs.create(hexfile));
+        try {
+          for (byte b : hex)
+            out.write(b);
+        } finally {
+          out.close();
+        }
+      }
+
+      // If the starting digit is 1,
+      // the hex value can be converted to decimal value.
+      if (conf.getInt(DIGIT_START_PROPERTY, 1) == 1) {
+        final Path outfile = new Path(dir, "pi.txt");
+        LOG.info("Writing text output to " + outfile);
+        final OutputStream outputstream = fs.create(outfile);
+        try {
+          final PrintStream out = new PrintStream(outputstream, true);
+          // write hex text
+          print(out, hex.iterator(), "Pi = 0x3.", "%02X", 5, 5);
+          out.println("Total number of hexadecimal digits is "
+              + 2 * hex.size() + ".");
+
+          // write decimal text
+          final Fraction dec = new Fraction(hex);
+          final int decDigits = 2 * hex.size(); // TODO: this is conservative.
+          print(out, new Iterator<Integer>() {
+            private int i = 0;
+
+            public boolean hasNext() {
+              return i < decDigits;
+            }
+
+            public Integer next() {
+              i++;
+              return dec.times10();
+            }
+
+            public void remove() {
+            }
+          }, "Pi = 3.", "%d", 10, 5);
+          out.println("Total number of decimal digits is " + decDigits + ".");
+        } finally {
+          outputstream.close();
+        }
+      }
+    }
+  }
+
+  /** Print out elements in a nice format. */
+  private static <T> void print(PrintStream out, Iterator<T> iterator,
+      String prefix, String format, int elementsPerGroup, int groupsPerLine) {
+    final StringBuilder sb = new StringBuilder("\n");
+    for (int i = 0; i < prefix.length(); i++)
+      sb.append(" ");
+    final String spaces = sb.toString();
+
+    out.print("\n" + prefix);
+    for (int i = 0; iterator.hasNext(); i++) {
+      if (i > 0 && i % elementsPerGroup == 0)
+        out.print((i / elementsPerGroup) % groupsPerLine == 0 ? spaces : " ");
+      out.print(String.format(format, iterator.next()));
+    }
+    out.println();
+  }
+
+  /** Input split for the {@link BbpInputFormat}. */
+  public static class BbpSplit extends InputSplit implements Writable {
+    private final static String[] EMPTY = {};
+
+    private long offset;
+    private int size;
+
+    /** Public default constructor for the Writable interface. */
+    public BbpSplit() {
+    }
+
+    private BbpSplit(int i, long offset, int size) {
+      LOG.info("Map #" + i + ": workload=" + workload(offset, size)
+          + ", offset=" + offset + ", size=" + size);
+      this.offset = offset;
+      this.size = size;
+    }
+
+    private long getOffset() {
+      return offset;
+    }
+
+    /** {@inheritDoc} */
+    public long getLength() {
+      return size;
+    }
+
+    /** No location is needed. */
+    public String[] getLocations() {
+      return EMPTY;
+    }
+
+    /** {@inheritDoc} */
+    public void readFields(DataInput in) throws IOException {
+      offset = in.readLong();
+      size = in.readInt();
+    }
+
+    /** {@inheritDoc} */
+    public void write(DataOutput out) throws IOException {
+      out.writeLong(offset);
+      out.writeInt(size);
+    }
+  }
+
+  /**
+   * Input format for the {@link BbpMapper}.
+   * Keys and values represent offsets and sizes, respectively.
+   */
+  public static class BbpInputFormat
+      extends InputFormat<LongWritable, IntWritable> {
+
+    /** {@inheritDoc} */
+    public List<InputSplit> getSplits(JobContext context) {
+      //get the property values
+      final int startDigit = context.getConfiguration().getInt(
+          DIGIT_START_PROPERTY, 1);
+      final int nDigits = context.getConfiguration().getInt(
+          DIGIT_SIZE_PROPERTY, 100);
+      final int nMaps = context.getConfiguration().getInt(
+          DIGIT_PARTS_PROPERTY, 1);
+
+      //create splits
+      final List<InputSplit> splits = new ArrayList<InputSplit>(nMaps);
+      final int[] parts = partition(startDigit - 1, nDigits, nMaps);
+      for (int i = 0; i < parts.length; ++i) {
+        final int k = i < parts.length - 1 ? parts[i+1]: nDigits+startDigit-1;
+        splits.add(new BbpSplit(i, parts[i], k - parts[i]));
+      }
+      return splits;
+    }
+
+    /** {@inheritDoc} */
+    public RecordReader<LongWritable, IntWritable> createRecordReader(
+        InputSplit generic, TaskAttemptContext context) {
+      final BbpSplit split = (BbpSplit)generic;
+
+      //return a record reader
+      return new RecordReader<LongWritable, IntWritable>() {
+        boolean done = false;
+
+        public void initialize(InputSplit split, TaskAttemptContext context) {
+        }
+
+        public boolean nextKeyValue() {
+          //Each record only contains one key.
+          return !done ? done = true : false;
+        }
+
+        public LongWritable getCurrentKey() {
+          return new LongWritable(split.getOffset());
+        }
+
+        public IntWritable getCurrentValue() {
+          return new IntWritable((int)split.getLength());
+        }
+
+        public float getProgress() {
+          return done? 1f: 0f;
+        }
+
+        public void close() {
+        }
+      };
+    }
+  }
+
+  /** Create and setup a job */
+  private static Job createJob(String name, Configuration conf
+      ) throws IOException {
+    final Job job = new Job(conf, NAME + "_" + name);
+    final Configuration jobconf = job.getConfiguration();
+    job.setJarByClass(BaileyBorweinPlouffe.class);
+
+    // setup mapper
+    job.setMapperClass(BbpMapper.class);
+    job.setMapOutputKeyClass(LongWritable.class);
+    job.setMapOutputValueClass(BytesWritable.class);
+
+    // setup reducer
+    job.setReducerClass(BbpReducer.class);
+    job.setOutputKeyClass(LongWritable.class);
+    job.setOutputValueClass(BytesWritable.class);
+    job.setNumReduceTasks(1);
+
+    // setup input
+    job.setInputFormatClass(BbpInputFormat.class);
+
+    // disable task timeout
+    jobconf.setLong("mapred.task.timeout", 0);
+
+    // do not use speculative execution
+    jobconf.setBoolean("mapred.map.tasks.speculative.execution", false);
+    jobconf.setBoolean("mapred.reduce.tasks.speculative.execution", false);
+    return job;
+  }
+
+  /** Run a map/reduce job to compute Pi. */
+  private static void compute(int startDigit, int nDigits, int nMaps,
+      String workingDir, Configuration conf, PrintStream out
+      ) throws IOException {
+    final String name = startDigit + "_" + nDigits;
+
+    //setup wroking directory
+    out.println("Working Directory = " + workingDir);
+    out.println();
+    final FileSystem fs = FileSystem.get(conf);
+    final Path dir = fs.makeQualified(new Path(workingDir));
+    if (fs.exists(dir)) {
+      throw new IOException("Working directory " + dir
+          + " already exists.  Please remove it first.");
+    } else if (!fs.mkdirs(dir)) {
+      throw new IOException("Cannot create working directory " + dir);
+    }
+
+    out.println("Start Digit      = " + startDigit);
+    out.println("Number of Digits = " + nDigits);
+    out.println("Number of Maps   = " + nMaps);
+
+    // setup a job
+    final Job job = createJob(name, conf);
+    final Path hexfile = new Path(dir, "pi_" + name + ".hex");
+    FileOutputFormat.setOutputPath(job, dir);
+
+    // setup custom properties
+    job.getConfiguration().set(WORKING_DIR_PROPERTY, dir.toString());
+    job.getConfiguration().set(HEX_FILE_PROPERTY, hexfile.toString());
+
+    job.getConfiguration().setInt(DIGIT_START_PROPERTY, startDigit);
+    job.getConfiguration().setInt(DIGIT_SIZE_PROPERTY, nDigits);
+    job.getConfiguration().setInt(DIGIT_PARTS_PROPERTY, nMaps);
+
+    // start a map/reduce job
+    out.println("\nStarting Job ...");
+    final long startTime = System.currentTimeMillis();
+    try {
+      if (!job.waitForCompletion()) {
+        out.println("Job failed.");
+        System.exit(1);
+      }
+    } catch (Exception e) {
+      throw new RuntimeException(e);
+    } finally {
+      final double duration = (System.currentTimeMillis() - startTime)/1000.0;
+      out.println("Duration is " + duration + " seconds.");
+    }
+    out.println("Output file: " + hexfile);
+  }
+
+  /**
+   * Parse arguments and then runs a map/reduce job.
+   * @return a non-zero value if there is an error. Otherwise, return 0.
+   */
+  public int run(String[] args) throws IOException {
+    if (args.length != 4) {
+      System.err.println("Usage: java " + getClass().getName()
+          + " <startDigit> <nDigits> <nMaps> <workingDir>");
+      ToolRunner.printGenericCommandUsage(System.err);
+      return -1;
+    }
+
+    final int startDigit = Integer.parseInt(args[0]);
+    final int nDigits = Integer.parseInt(args[1]);
+    final int nMaps = Integer.parseInt(args[2]);
+    final String workingDir = args[3];
+
+    if (startDigit <= 0) {
+      throw new IllegalArgumentException("startDigit = " + startDigit+" <= 0");
+    } else if (nDigits <= 0) {
+      throw new IllegalArgumentException("nDigits = " + nDigits + " <= 0");
+    } else if (nDigits % BBP_HEX_DIGITS != 0) {
+      throw new IllegalArgumentException("nDigits = " + nDigits
+          + " is not a multiple of " + BBP_HEX_DIGITS);
+    } else if (nDigits - 1L + startDigit > IMPLEMENTATION_LIMIT + BBP_HEX_DIGITS) {
+      throw new UnsupportedOperationException("nDigits - 1 + startDigit = "
+          + (nDigits - 1L + startDigit)
+          + " > IMPLEMENTATION_LIMIT + BBP_HEX_DIGITS,"
+          + ", where IMPLEMENTATION_LIMIT=" + IMPLEMENTATION_LIMIT
+          + "and BBP_HEX_DIGITS=" + BBP_HEX_DIGITS);
+    } else if (nMaps <= 0) {
+      throw new IllegalArgumentException("nMaps = " + nMaps + " <= 0");
+    }
+
+    compute(startDigit, nDigits, nMaps, workingDir, getConf(), System.out);
+    return 0;
+  }
+
+  /** The main method for running it as a stand alone command. */
+  public static void main(String[] argv) throws Exception {
+    System.exit(ToolRunner.run(null, new BaileyBorweinPlouffe(), argv));
+  }
+
+    /////////////////////////////////////////////////////////////////////
+   // static fields and methods for Bailey-Borwein-Plouffe algorithm. //
+  /////////////////////////////////////////////////////////////////////
+
+  // TODO: the following value is conservative, should be at lease 2^28.
+  private static final long IMPLEMENTATION_LIMIT = 100000000;
+
+  private static final long ACCURACY_BIT = 32;
+  private static final long BBP_HEX_DIGITS = 4;
+  private static final long BBP_MULTIPLIER = 1 << (4 * BBP_HEX_DIGITS);
+
+  /**
+   * Compute the exact (d+1)th to (d+{@link #BBP_HEX_DIGITS})th
+   * hex digits of pi.
+   */
+  static long hexDigits(final long d) {
+    if (d < 0) {
+      throw new IllegalArgumentException("d = " + d + " < 0");
+    } else if (d > IMPLEMENTATION_LIMIT) {
+      throw new IllegalArgumentException("d = " + d
+          + " > IMPLEMENTATION_LIMIT = " + IMPLEMENTATION_LIMIT);
+    }
+
+    final double s1 = sum(1, d);
+    final double s4 = sum(4, d);
+    final double s5 = sum(5, d);
+    final double s6 = sum(6, d);
+
+    double pi = s1 + s1;
+    if (pi >= 1)
+      pi--;
+    pi *= 2;
+    if (pi >= 1)
+      pi--;
+
+    pi -= s4;
+    if (pi < 0)
+      pi++;
+    pi -= s4;
+    if (pi < 0)
+      pi++;
+    pi -= s5;
+    if (pi < 0)
+      pi++;
+    pi -= s6;
+    if (pi < 0)
+      pi++;
+
+    return (long) (pi * BBP_MULTIPLIER);
+  }
+
+  /**
+   * Approximate the fraction part of
+   * $16^d \sum_{k=0}^\infty \frac{16^{d-k}}{8k+j}$
+   * for d > 0 and j = 1, 4, 5, 6.
+   */
+  private static double sum(final long j, final long d) {
+    long k = j == 1 ? 1 : 0;
+    double s = 0;
+    if (k <= d) {
+      s = 1.0 / ((d << 3) | j);
+      for (; k < d; k++) {
+        final long n = (k << 3) | j;
+        s += mod((d - k) << 2, n) * 1.0 / n;
+        if (s >= 1)
+          s--;
+      }
+      k++;
+    }
+
+    if (k >= 1L << (ACCURACY_BIT - 7))
+      return s;
+
+    for (;; k++) {
+      final long n = (k << 3) | j;
+      final long shift = (k - d) << 2;
+      if (ACCURACY_BIT <= shift || 1L << (ACCURACY_BIT - shift) < n) {
+        return s;
+      }
+
+      s += 1.0 / (n << shift);
+      if (s >= 1)
+        s--;
+    }
+  }
+
+  /** Compute $2^e \mod n$ for e > 0, n > 2 */
+  static long mod(final long e, final long n) {
+    long mask = (e & 0xFFFFFFFF00000000L) == 0 ? 0x00000000FFFFFFFFL
+        : 0xFFFFFFFF00000000L;
+    mask &= (e & 0xFFFF0000FFFF0000L & mask) == 0 ? 0x0000FFFF0000FFFFL
+        : 0xFFFF0000FFFF0000L;
+    mask &= (e & 0xFF00FF00FF00FF00L & mask) == 0 ? 0x00FF00FF00FF00FFL
+        : 0xFF00FF00FF00FF00L;
+    mask &= (e & 0xF0F0F0F0F0F0F0F0L & mask) == 0 ? 0x0F0F0F0F0F0F0F0FL
+        : 0xF0F0F0F0F0F0F0F0L;
+    mask &= (e & 0xCCCCCCCCCCCCCCCCL & mask) == 0 ? 0x3333333333333333L
+        : 0xCCCCCCCCCCCCCCCCL;
+    mask &= (e & 0xAAAAAAAAAAAAAAAAL & mask) == 0 ? 0x5555555555555555L
+        : 0xAAAAAAAAAAAAAAAAL;
+
+    long r = 2;
+    for (mask >>= 1; mask > 0; mask >>= 1) {
+      r *= r;
+      r %= n;
+
+      if ((e & mask) != 0) {
+        r += r;
+        if (r >= n)
+          r -= n;
+      }
+    }
+    return r;
+  }
+
+  /** Represent a number x in hex for 1 > x >= 0 */
+  private static class Fraction {
+    private final int[] integers; // only use 24-bit
+
+    private int first = 0; // index to the first non-zero integer
+
+    /** Construct a fraction represented by the bytes. */
+    Fraction(List<Byte> bytes) {
+      integers = new int[(bytes.size() + 2) / 3];
+      for (int i = 0; i < bytes.size(); i++) {
+        final int b = 0xFF & bytes.get(i);
+        integers[integers.length - 1 - i / 3] |= b << ((2 - i % 3) << 3);
+      }
+      skipZeros();
+    }
+
+    /**
+     * Compute y = 10*x and then set x to the fraction part of y, where x is the
+     * fraction represented by this object.
+     * @return integer part of y
+     */
+    int times10() {
+      int carry = 0;
+      for (int i = first; i < integers.length; i++) {
+        integers[i] <<= 1;
+        integers[i] += carry + (integers[i] << 2);
+        carry = integers[i] >> 24;
+        integers[i] &= 0xFFFFFF;
+      }
+      skipZeros();
+      return carry;
+    }
+
+    private void skipZeros() {
+      for(; first < integers.length && integers[first] == 0; first++)
+        ;
+    }
+  }
+
+  /**
+   * Partition input so that the workload of each part is
+   * approximately the same.
+   */
+  static int[] partition(final int offset, final int size, final int nParts) {
+    final int[] parts = new int[nParts];
+    final long total = workload(offset, size);
+    final int remainder = offset % 4;
+
+    parts[0] = offset;
+    for (int i = 1; i < nParts; i++) {
+      final long target = offset + i*(total/nParts) + i*(total%nParts)/nParts;
+
+      //search the closest value
+      int low = parts[i - 1];
+      int high = offset + size;
+      for (; high > low + 4;) {
+        final int mid = (high + low - 2 * remainder) / 8 * 4 + remainder;
+        final long midvalue = workload(mid);
+        if (midvalue == target)
+          high = low = mid;
+        else if (midvalue > target)
+          high = mid;
+        else
+          low = mid;
+      }
+      parts[i] = high == low? high:
+          workload(high)-target > target-workload(low)?
+              low: high;
+    }
+    return parts;
+  }
+
+  private static final long MAX_N = 4294967295L; // prevent overflow
+
+  /** Estimate the workload for input size n (in some unit). */
+  private static long workload(final long n) {
+    if (n < 0) {
+      throw new IllegalArgumentException("n = " + n + " < 0");
+    } else if (n > MAX_N) {
+      throw new IllegalArgumentException("n = " + n + " > MAX_N = " + MAX_N);
+    }
+    return (n & 1L) == 0L ? (n >> 1) * (n + 1) : n * ((n + 1) >> 1);
+  }
+
+  private static long workload(long offset, long size) {
+    return workload(offset + size) - workload(offset);
+  }
+}

Modified: hadoop/core/trunk/src/examples/org/apache/hadoop/examples/ExampleDriver.java
URL: http://svn.apache.org/viewvc/hadoop/core/trunk/src/examples/org/apache/hadoop/examples/ExampleDriver.java?rev=746864&r1=746863&r2=746864&view=diff
==============================================================================
--- hadoop/core/trunk/src/examples/org/apache/hadoop/examples/ExampleDriver.java (original)
+++ hadoop/core/trunk/src/examples/org/apache/hadoop/examples/ExampleDriver.java Mon Feb 23 02:52:12 2009
@@ -48,7 +48,9 @@
       pgd.addClass("randomtextwriter", RandomTextWriter.class, 
       "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.");
-      pgd.addClass("pi", PiEstimator.class, "A map/reduce program that estimates Pi using monte-carlo method.");
+      pgd.addClass("pi", PiEstimator.class,
+                   "A map/reduce program that estimates Pi using quasi-Monte Carlo method.");
+      pgd.addClass("bbp", BaileyBorweinPlouffe.class, BaileyBorweinPlouffe.DESCRIPTION);
       pgd.addClass("pentomino", DistributedPentomino.class,
       "A map/reduce tile laying program to find solutions to pentomino problems.");
       pgd.addClass("secondarysort", SecondarySort.class,

Added: hadoop/core/trunk/src/test/org/apache/hadoop/examples/TestBaileyBorweinPlouffe.java
URL: http://svn.apache.org/viewvc/hadoop/core/trunk/src/test/org/apache/hadoop/examples/TestBaileyBorweinPlouffe.java?rev=746864&view=auto
==============================================================================
--- hadoop/core/trunk/src/test/org/apache/hadoop/examples/TestBaileyBorweinPlouffe.java (added)
+++ hadoop/core/trunk/src/test/org/apache/hadoop/examples/TestBaileyBorweinPlouffe.java Mon Feb 23 02:52:12 2009
@@ -0,0 +1,46 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.examples;
+
+import java.math.BigInteger;
+
+/** Tests for BaileyBorweinPlouffe */
+public class TestBaileyBorweinPlouffe extends junit.framework.TestCase {
+
+  public void testMod() {
+    final BigInteger TWO = BigInteger.ONE.add(BigInteger.ONE);
+    for(long n = 3; n < 100; n++) {
+      for (long e = 1; e < 100; e++) {
+        final long r = TWO.modPow(
+            BigInteger.valueOf(e), BigInteger.valueOf(n)).longValue();
+        assertEquals("e=" + e + ", n=" + n, r, BaileyBorweinPlouffe.mod(e, n));
+      }
+    }
+  }
+
+  public void testHexDigit() {
+    final long[] answers = {0x43F6, 0xA308, 0x29B7, 0x49F1, 0x8AC8, 0x35EA};
+    long d = 1;
+    for(int i = 0; i < answers.length; i++) {
+      assertEquals("d=" + d, answers[i], BaileyBorweinPlouffe.hexDigits(d));
+      d *= 10;
+    }
+
+    assertEquals(0x243FL, BaileyBorweinPlouffe.hexDigits(0));
+ }
+}
\ No newline at end of file