hadoop-mapreduce-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From szets...@apache.org
Subject svn commit: r790015 [2/2] - in /hadoop/mapreduce/trunk: ./ src/examples/org/apache/hadoop/examples/ src/examples/org/apache/hadoop/examples/pi/ src/examples/org/apache/hadoop/examples/pi/math/ src/test/mapred/org/apache/hadoop/examples/pi/ src/test/map...
Date Wed, 01 Jul 2009 01:35:56 GMT
Added: hadoop/mapreduce/trunk/src/examples/org/apache/hadoop/examples/pi/math/Montgomery.java
URL: http://svn.apache.org/viewvc/hadoop/mapreduce/trunk/src/examples/org/apache/hadoop/examples/pi/math/Montgomery.java?rev=790015&view=auto
==============================================================================
--- hadoop/mapreduce/trunk/src/examples/org/apache/hadoop/examples/pi/math/Montgomery.java
(added)
+++ hadoop/mapreduce/trunk/src/examples/org/apache/hadoop/examples/pi/math/Montgomery.java
Wed Jul  1 01:35:55 2009
@@ -0,0 +1,78 @@
+/**
+ * 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.pi.math;
+
+/** Montgomery method.
+ * 
+ * References:
+ * 
+ * [1] Richard Crandall and Carl Pomerance.  Prime Numbers: A Computational 
+ *     Perspective.  Springer-Verlag, 2001. 
+ * 
+ * [2] Peter Montgomery.  Modular multiplication without trial division.
+ *     Math. Comp., 44:519-521, 1985.
+ */
+class Montgomery {
+  protected final Product product = new Product();
+
+  protected long N;
+  protected long N_I;  // N'
+  protected long R;
+  protected long R_1;  // R - 1
+  protected int s;
+
+  /** Set the modular and initialize this object. */
+  Montgomery set(long n) {
+    if (n % 2 != 1)
+      throw new IllegalArgumentException("n % 2 != 1, n=" + n);
+    N = n;
+    R = Long.highestOneBit(n) << 1;
+    N_I = R - Modular.modInverse(N, R);
+    R_1 = R - 1;
+    s = Long.numberOfTrailingZeros(R);
+    return this;
+  }
+
+  /** Compute 2^y mod N for N odd. */
+  long mod(final long y) {
+    long p = R - N; 
+    long x = p << 1;
+    if (x >= N) x -= N;
+    
+    for(long mask = Long.highestOneBit(y); mask > 0; mask >>>= 1) {
+      p = product.m(p, p);
+      if ((mask & y) != 0) p = product.m(p, x);
+    }
+    return product.m(p, 1);
+  }
+
+  class Product {
+    private final LongLong x = new LongLong();
+    private final LongLong xN_I = new LongLong();
+    private final LongLong aN = new LongLong();
+
+    long m(final long c, final long d) {
+      LongLong.multiplication(x, c, d);
+      // a = (x * N')&(R - 1) = ((x & R_1) * N') & R_1
+      final long a = LongLong.multiplication(xN_I, x.and(R_1), N_I).and(R_1);
+      LongLong.multiplication(aN, a, N);
+      final long z = aN.plusEqual(x).shiftRight(s);
+      return z < N? z: z - N;      
+    }
+  }
+}
\ No newline at end of file

Added: hadoop/mapreduce/trunk/src/examples/org/apache/hadoop/examples/pi/math/Summation.java
URL: http://svn.apache.org/viewvc/hadoop/mapreduce/trunk/src/examples/org/apache/hadoop/examples/pi/math/Summation.java?rev=790015&view=auto
==============================================================================
--- hadoop/mapreduce/trunk/src/examples/org/apache/hadoop/examples/pi/math/Summation.java
(added)
+++ hadoop/mapreduce/trunk/src/examples/org/apache/hadoop/examples/pi/math/Summation.java
Wed Jul  1 01:35:55 2009
@@ -0,0 +1,242 @@
+/**
+ * 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.pi.math;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.hadoop.examples.pi.Combinable;
+import org.apache.hadoop.examples.pi.Container;
+import org.apache.hadoop.examples.pi.Util;
+
+/** Represent the summation \sum \frac{2^e \mod n}{n}. */
+public class Summation implements Container<Summation>, Combinable<Summation>
{
+  /** Variable n in the summation. */
+  public final ArithmeticProgression N;
+  /** Variable e in the summation. */
+  public final ArithmeticProgression E;
+  private Double value = null;
+
+  /** Constructor */
+  public Summation(ArithmeticProgression N, ArithmeticProgression E) {
+    if (N.getSteps() != E.getSteps()) {
+      throw new IllegalArgumentException("N.getSteps() != E.getSteps(),"
+          + "\n  N.getSteps()=" + N.getSteps() + ", N=" + N
+          + "\n  E.getSteps()=" + E.getSteps() + ", E=" + E);
+    }
+    this.N = N;
+    this.E = E;
+  }
+
+  /** Constructor */
+  Summation(long valueN, long deltaN, 
+            long valueE, long deltaE, long limitE) {
+    this(valueN, deltaN, valueN - deltaN*((valueE - limitE)/deltaE),
+         valueE, deltaE, limitE);
+  }
+
+  /** Constructor */
+  Summation(long valueN, long deltaN, long limitN, 
+            long valueE, long deltaE, long limitE) {
+    this(new ArithmeticProgression('n', valueN, deltaN, limitN),
+         new ArithmeticProgression('e', valueE, deltaE, limitE));
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public Summation getElement() {return this;}
+
+  /** Return the number of steps of this summation */
+  long getSteps() {return E.getSteps();}
+  
+  /** Return the value of this summation */
+  public Double getValue() {return value;}
+  /** Set the value of this summation */
+  public void setValue(double v) {this.value = v;}
+
+  /** {@inheritDoc} */
+  @Override
+  public String toString() {
+    return "[" + N + "; " + E + (value == null? "]": "]value=" + Double.doubleToLongBits(value));

+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public boolean equals(Object obj) {
+    if (obj == this)
+      return true;
+    if (obj != null && obj instanceof Summation) {
+      final Summation that = (Summation)obj;
+      return this.N.equals(that.N) && this.E.equals(that.E);
+    }
+    throw new IllegalArgumentException(obj == null? "obj == null":
+      "obj.getClass()=" + obj.getClass());
+  }
+
+  /** Not supported */
+  @Override
+  public int hashCode() {
+    throw new UnsupportedOperationException();
+  }
+
+  /** Covert a String to a Summation. */
+  public static Summation valueOf(final String s) {
+    int i = 1;
+    int j = s.indexOf("; ", i);
+    if (j < 0)
+      throw new IllegalArgumentException("i=" + i + ", j=" + j + " < 0, s=" + s);
+    final ArithmeticProgression N = ArithmeticProgression.valueOf(s.substring(i, j));
+
+    i = j + 2;
+    j = s.indexOf("]", i);
+    if (j < 0)
+      throw new IllegalArgumentException("i=" + i + ", j=" + j + " < 0, s=" + s);
+    final ArithmeticProgression E = ArithmeticProgression.valueOf(s.substring(i, j));
+
+    final Summation sigma = new Summation(N, E);
+    i = j + 1;
+    if (s.length() > i) {
+      final String value = Util.parseStringVariable("value", s.substring(i));
+      sigma.setValue(value.indexOf('.') < 0?
+          Double.longBitsToDouble(Long.parseLong(value)):
+          Double.parseDouble(value));
+    }
+    return sigma;
+  }
+
+  /** Compute the value of the summation. */
+  public double compute() {
+    if (value == null)
+      value = N.limit <= MAX_MODULAR? compute_modular(): compute_montgomery();
+    return value;
+  }
+
+  private static final long MAX_MODULAR = 1L << 32;
+  /** Compute the value using {@link Modular#mod(long, long)}. */
+  double compute_modular() {
+    long e = E.value;
+    long n = N.value;
+    double s = 0;
+    for(; e > E.limit; e += E.delta) {
+      s = Modular.addMod(s, Modular.mod(e, n)/(double)n);
+      n += N.delta;
+    }
+    return s;
+  }
+
+  final Montgomery montgomery = new Montgomery();
+  /** Compute the value using {@link Montgomery#mod(long)}. */
+  double compute_montgomery() {
+    long e = E.value;
+    long n = N.value;
+    double s = 0;
+    for(; e > E.limit; e += E.delta) {
+      s = Modular.addMod(s, montgomery.set(n).mod(e)/(double)n);
+      n += N.delta;
+    }
+    return s;
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public int compareTo(Summation that) {
+    final int de = this.E.compareTo(that.E);
+    if (de != 0) return de;
+    return this.N.compareTo(that.N);
+  }
+
+  /** {@inheritDoc} */
+  @Override
+  public Summation combine(Summation that) {
+    if (this.N.delta != that.N.delta || this.E.delta != that.E.delta) 
+      throw new IllegalArgumentException(
+          "this.N.delta != that.N.delta || this.E.delta != that.E.delta"
+          + ",\n  this=" + this
+          + ",\n  that=" + that);
+    if (this.E.limit == that.E.value && this.N.limit == that.N.value) {
+      final double v = Modular.addMod(this.value, that.value);
+      final Summation s = new Summation(
+          new ArithmeticProgression(N.symbol, N.value, N.delta, that.N.limit),
+          new ArithmeticProgression(E.symbol, E.value, E.delta, that.E.limit));
+      s.setValue(v);
+      return s;
+    }
+    return null;
+  }
+
+  /** Find the remaining terms. */
+  public <T extends Container<Summation>> List<Summation> remainingTerms(List<T>
sorted) {
+    final List<Summation> results = new ArrayList<Summation>();
+    Summation remaining = this;
+
+    if (sorted != null)
+      for(Container<Summation> c : sorted) {
+        final Summation sigma = c.getElement();
+        if (!remaining.contains(sigma))
+          throw new IllegalArgumentException("!remaining.contains(s),"
+              + "\n  remaining = " + remaining
+              + "\n  s         = " + sigma          
+              + "\n  this      = " + this
+              + "\n  sorted    = " + sorted);
+
+        final Summation s = new Summation(sigma.N.limit, N.delta, remaining.N.limit,
+                                          sigma.E.limit, E.delta, remaining.E.limit);
+        if (s.getSteps() > 0)
+          results.add(s);
+        remaining = new Summation(remaining.N.value, N.delta, sigma.N.value,
+                                  remaining.E.value, E.delta, sigma.E.value);
+      }
+
+    if (remaining.getSteps() > 0)
+      results.add(remaining);
+  
+    return results;
+  }
+
+  /** Does this contains that? */
+  public boolean contains(Summation that) {
+    return this.N.contains(that.N) && this.E.contains(that.E);    
+  }
+
+  /** Partition the summation. */
+  public Summation[] partition(final int nParts) {
+    final Summation[] parts = new Summation[nParts];
+    final long steps = (E.limit - E.value)/E.delta + 1;
+
+    long prevN = N.value;
+    long prevE = E.value;
+
+    for(int i = 1; i < parts.length; i++) {
+      final long k = (i * steps)/parts.length;
+
+      final long currN = N.skip(k);
+      final long currE = E.skip(k);
+      parts[i - 1] = new Summation(
+          new ArithmeticProgression(N.symbol, prevN, N.delta, currN),
+          new ArithmeticProgression(E.symbol, prevE, E.delta, currE));
+
+      prevN = currN;
+      prevE = currE;
+    }
+
+    parts[parts.length - 1] = new Summation(
+        new ArithmeticProgression(N.symbol, prevN, N.delta, N.limit),
+        new ArithmeticProgression(E.symbol, prevE, E.delta, E.limit));
+    return parts;
+  }
+}
\ No newline at end of file

Added: hadoop/mapreduce/trunk/src/test/mapred/org/apache/hadoop/examples/pi/math/TestLongLong.java
URL: http://svn.apache.org/viewvc/hadoop/mapreduce/trunk/src/test/mapred/org/apache/hadoop/examples/pi/math/TestLongLong.java?rev=790015&view=auto
==============================================================================
--- hadoop/mapreduce/trunk/src/test/mapred/org/apache/hadoop/examples/pi/math/TestLongLong.java
(added)
+++ hadoop/mapreduce/trunk/src/test/mapred/org/apache/hadoop/examples/pi/math/TestLongLong.java
Wed Jul  1 01:35:55 2009
@@ -0,0 +1,73 @@
+/**
+ * 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.pi.math;
+
+import java.math.BigInteger;
+import java.util.Random;
+
+public class TestLongLong extends junit.framework.TestCase {
+  static final Random RAN = new Random(); 
+  static final long MASK = (1L << (LongLong.SIZE >> 1)) - 1;
+
+  static long nextPositiveLong() {
+    return RAN.nextLong() & MASK;
+  }
+  
+  static void verifyMultiplication(long a, long b) {
+    final LongLong ll = LongLong.multiplication(new LongLong(), a, b);
+    final BigInteger bi = BigInteger.valueOf(a).multiply(BigInteger.valueOf(b));
+
+    final String s = String.format("\na = %x\nb = %x\nll= " + ll + "\nbi= " + bi.toString(16)
+ "\n", a, b);
+    //System.out.println(s);
+    assertEquals(s, bi, ll.toBigInteger());
+  }
+
+  public void testMultiplication() {
+    for(int i = 0; i < 100; i++) {
+      final long a = nextPositiveLong();
+      final long b = nextPositiveLong();
+      verifyMultiplication(a, b);
+    }
+    final long max = Long.MAX_VALUE & MASK;
+    verifyMultiplication(max, max);
+  }
+
+  static void verifyRightShift(long a, long b) {
+    final LongLong ll = new LongLong().set(a, b);
+    final BigInteger bi = ll.toBigInteger();
+    
+    for(int i = 0; i < LongLong.SIZE >> 1; i++) {
+      final long result = ll.shiftRight(i) & MASK;
+      final long expected = bi.shiftRight(i).longValue() & MASK;
+      final String s = String.format("\na = %x\nb = %x\nll= " + ll + "\nbi= " + bi.toString(16)
+ "\n", a, b);
+      assertEquals(s, expected, result);
+    }
+
+    final String s = String.format("\na = %x\nb = %x\nll= " + ll + "\nbi= " + bi.toString(16)
+ "\n", a, b);
+    //System.out.println(s);
+    assertEquals(s, bi, ll.toBigInteger());
+  }
+
+  public void testRightShift() {
+    for(int i = 0; i < 1000; i++) {
+      final long a = nextPositiveLong();
+      final long b = nextPositiveLong();
+      verifyMultiplication(a, b);
+    }
+  }
+}

Added: hadoop/mapreduce/trunk/src/test/mapred/org/apache/hadoop/examples/pi/math/TestModular.java
URL: http://svn.apache.org/viewvc/hadoop/mapreduce/trunk/src/test/mapred/org/apache/hadoop/examples/pi/math/TestModular.java?rev=790015&view=auto
==============================================================================
--- hadoop/mapreduce/trunk/src/test/mapred/org/apache/hadoop/examples/pi/math/TestModular.java
(added)
+++ hadoop/mapreduce/trunk/src/test/mapred/org/apache/hadoop/examples/pi/math/TestModular.java
Wed Jul  1 01:35:55 2009
@@ -0,0 +1,337 @@
+/**
+ * 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.pi.math;
+
+import java.math.BigInteger;
+import java.util.Random;
+
+import org.apache.hadoop.examples.pi.Util.Timer;
+
+public class TestModular extends junit.framework.TestCase { 
+  private static final Random RANDOM = new Random(); 
+  private static final BigInteger TWO = BigInteger.valueOf(2);
+
+
+  static final int DIV_VALID_BIT = 32;
+  static final long DIV_LIMIT = 1L << DIV_VALID_BIT; 
+
+  // return r/n for n > r > 0
+  static long div(long sum, long r, long n) {
+    long q = 0;
+    int i = DIV_VALID_BIT - 1;
+    for(r <<= 1; r < n; r <<= 1) i--;
+//System.out.printf("  r=%d, n=%d, q=%d\n", r, n, q);
+    
+    for(; i >= 0 ;) {
+      r -= n;
+      q |= (1L << i);
+      if (r <= 0) break;
+      for(; r < n; r <<= 1) i--;
+//System.out.printf("  r=%d, n=%d, q=%d\n", r, n, q);
+    }
+
+    sum += q;
+    return sum < DIV_LIMIT? sum: sum - DIV_LIMIT;
+  }
+ 
+  public void testDiv() {
+    for(long n = 2; n < 100; n++)
+      for(long r = 1; r < n; r++) {
+        final long a = div(0, r, n);
+        final long b = (long)((r*1.0/n) * (1L << DIV_VALID_BIT));
+        final String s = String.format("r=%d, n=%d, a=%X, b=%X", r, n, a, b);
+        assertEquals(s, b, a);
+      }
+  }
+
+  static long[][][] generateRN(int nsize, int rsize) {
+    final long[][][] rn = new long[nsize][][];
+
+    for(int i = 0; i < rn.length; i++) {
+      rn[i] = new long[rsize + 1][];
+      long n = RANDOM.nextLong() & 0xFFFFFFFFFFFFFFFL; 
+      if (n <= 1) n = 0xFFFFFFFFFFFFFFFL - n;
+      rn[i][0] = new long[]{n};
+      final BigInteger N = BigInteger.valueOf(n); 
+
+      for(int j = 1; j < rn[i].length; j++) {
+        long r = RANDOM.nextLong();
+        if (r < 0) r = -r;
+        if (r >= n) r %= n;
+        final BigInteger R = BigInteger.valueOf(r); 
+        rn[i][j] = new long[]{r, R.multiply(R).mod(N).longValue()};
+      }
+    }
+    return rn;
+  }
+
+  static long square_slow(long z, final long n) {
+    long r = 0;
+    for(long s = z; z > 0; z >>= 1) {
+      if ((((int)z) & 1) == 1) {
+        r += s;
+        if (r >= n) r -= n;
+      }
+
+      s <<= 1;
+      if (s >= n) s -= n;
+    }
+    return r;
+  }
+
+  //0 <= r < n < max/2
+  static long square(long r, final long n, long r2p64) {
+    if (r <= Modular.MAX_SQRT_LONG) {
+      r *= r;
+      if (r >= n) r %= n;
+    } else {
+      final int HALF = (63 - Long.numberOfLeadingZeros(n)) >> 1;
+      final int FULL = HALF << 1;
+      final long ONES = (1 << HALF) - 1; 
+  
+      final long high = r >>> HALF;
+      final long low  = r &= ONES;
+
+      r *= r;
+      if (r >= n) r %= n;
+  
+      if (high != 0) {
+        long s = high * high;
+        if (s >= n) s %= n;
+        for(int i = 0; i < FULL; i++)
+          if ((s <<= 1) >= n) s -= n;
+        
+        if (low == 0)
+          r = s;
+        else {
+          long t = high * low;
+          if (t >= n) t %= n;
+          for(int i = -1; i < HALF; i++)
+            if ((t <<= 1) >= n) t -= n;
+          
+          r += s;
+          if (r >= n) r -= n;
+          r += t;
+          if (r >= n) r -= n;
+        }
+      }
+    }
+    return r;
+  }
+  
+  static void squareBenchmarks() {
+    final Timer t = new Timer(false);
+    t.tick("squareBenchmarks(), MAX_SQRT=" + Modular.MAX_SQRT_LONG);
+
+    final long[][][] rn = generateRN(1000, 1000);
+    t.tick("generateRN");
+
+    for(int i = 0; i < rn.length; i++) {
+      final long n = rn[i][0][0];
+      for(int j = 1; j < rn[i].length; j++) {
+        final long r = rn[i][j][0];
+        final long answer = rn[i][j][1];
+        final long s = square_slow(r, n);
+        if (s != answer)
+          assertEquals("r=" + r + ", n=" + n + ", answer=" + answer + " but s=" + s, answer,
s);
+      }
+    }
+    t.tick("square_slow");
+
+    for(int i = 0; i < rn.length; i++) {
+      final long n = rn[i][0][0];
+      long r2p64 = (0x4000000000000000L % n) << 1;
+      if (r2p64 >= n) r2p64 -= n;
+      for(int j = 1; j < rn[i].length; j++) {
+        final long r = rn[i][j][0];
+        final long answer = rn[i][j][1];
+        final long s = square(r, n, r2p64);
+        if (s != answer)
+          assertEquals("r=" + r + ", n=" + n + ", answer=" + answer + " but s=" + s, answer,
s);
+      }
+    }
+    t.tick("square");
+
+    for(int i = 0; i < rn.length; i++) {
+      final long n = rn[i][0][0];
+      final BigInteger N = BigInteger.valueOf(n);
+      for(int j = 1; j < rn[i].length; j++) {
+        final long r = rn[i][j][0];
+        final long answer = rn[i][j][1];
+        final BigInteger R = BigInteger.valueOf(r);
+        final long s = R.multiply(R).mod(N).longValue();
+        if (s != answer)
+          assertEquals("r=" + r + ", n=" + n + ", answer=" + answer + " but s=" + s, answer,
s);
+      }
+    }
+    t.tick("R.multiply(R).mod(N)");
+
+    for(int i = 0; i < rn.length; i++) {
+      final long n = rn[i][0][0];
+      final BigInteger N = BigInteger.valueOf(n);
+      for(int j = 1; j < rn[i].length; j++) {
+        final long r = rn[i][j][0];
+        final long answer = rn[i][j][1];
+        final BigInteger R = BigInteger.valueOf(r);
+        final long s = R.modPow(TWO, N).longValue();
+        if (s != answer)
+          assertEquals("r=" + r + ", n=" + n + ", answer=" + answer + " but s=" + s, answer,
s);
+      }
+    }
+    t.tick("R.modPow(TWO, N)");
+  }
+
+  static long[][][] generateEN(int nsize, int esize) {
+    final long[][][] en = new long[nsize][][];
+
+    for(int i = 0; i < en.length; i++) {
+      en[i] = new long[esize + 1][];
+      long n = (RANDOM.nextLong() & 0xFFFFFFFFFFFFFFFL) | 1L; 
+      if (n == 1) n = 3;
+      en[i][0] = new long[]{n};
+      final BigInteger N = BigInteger.valueOf(n); 
+
+      for(int j = 1; j < en[i].length; j++) {
+        long e = RANDOM.nextLong();
+        if (e < 0) e = -e;
+        final BigInteger E = BigInteger.valueOf(e); 
+        en[i][j] = new long[]{e, TWO.modPow(E, N).longValue()};
+      }
+    }
+    return en;
+  }
+
+  /** Compute $2^e \mod n$ for e > 0, n > 2 */
+  static long modBigInteger(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;
+
+    final BigInteger N = BigInteger.valueOf(n);
+    long r = 2;
+    for (mask >>= 1; mask > 0; mask >>= 1) {
+      if (r <= Modular.MAX_SQRT_LONG) {
+        r *= r;
+        if (r >= n) r %= n;
+      } else {
+        final BigInteger R = BigInteger.valueOf(r);
+        r = R.multiply(R).mod(N).longValue();
+      }
+
+      if ((e & mask) != 0) {
+        r <<= 1;
+        if (r >= n) r -= n;
+      }
+    }
+    return r;
+  }
+
+  static class Montgomery2 extends Montgomery {
+    /** Compute 2^y mod N for N odd. */
+    long mod2(final long y) {
+      long r0 = R - N; 
+      long r1 = r0 << 1;
+      if (r1 >= N) r1 -= N;
+      
+      for(long mask = Long.highestOneBit(y); mask > 0; mask >>>= 1) {
+        if ((mask & y) == 0) {
+          r1 = product.m(r0, r1);
+          r0 = product.m(r0, r0);
+        } else {
+          r0 = product.m(r0, r1);
+          r1 = product.m(r1, r1);
+        }
+      }
+      return product.m(r0, 1);
+    }
+  }
+  
+  static void modBenchmarks() {
+    final Timer t = new Timer(false);
+    t.tick("modBenchmarks()");
+
+    final long[][][] en = generateEN(10000, 10);
+    t.tick("generateEN");
+
+    for(int i = 0; i < en.length; i++) {
+      final long n = en[i][0][0];
+      for(int j = 1; j < en[i].length; j++) {
+        final long e = en[i][j][0];
+        final long answer = en[i][j][1];
+        final long s = Modular.mod(e, n);
+        if (s != answer)
+          assertEquals("e=" + e + ", n=" + n + ", answer=" + answer + " but s=" + s, answer,
s);
+      }
+    }
+    t.tick("Modular.mod");
+    
+    final Montgomery2 m2 = new Montgomery2();
+    for(int i = 0; i < en.length; i++) {
+      final long n = en[i][0][0];
+      m2.set(n);
+      for(int j = 1; j < en[i].length; j++) {
+        final long e = en[i][j][0];
+        final long answer = en[i][j][1];
+        final long s = m2.mod(e);
+        if (s != answer)
+          assertEquals("e=" + e + ", n=" + n + ", answer=" + answer + " but s=" + s, answer,
s);
+      }
+    }
+    t.tick("montgomery.mod");
+
+    for(int i = 0; i < en.length; i++) {
+      final long n = en[i][0][0];
+      m2.set(n);
+      for(int j = 1; j < en[i].length; j++) {
+        final long e = en[i][j][0];
+        final long answer = en[i][j][1];
+        final long s = m2.mod2(e);
+        if (s != answer)
+          assertEquals("e=" + e + ", n=" + n + ", answer=" + answer + " but s=" + s, answer,
s);
+      }
+    }
+    t.tick("montgomery.mod2");
+
+    for(int i = 0; i < en.length; i++) {
+      final long n = en[i][0][0];
+      final BigInteger N = BigInteger.valueOf(n); 
+      for(int j = 1; j < en[i].length; j++) {
+        final long e = en[i][j][0];
+        final long answer = en[i][j][1];
+        final long s = TWO.modPow(BigInteger.valueOf(e), N).longValue();
+        if (s != answer)
+          assertEquals("e=" + e + ", n=" + n + ", answer=" + answer + " but s=" + s, answer,
s);
+      }
+    }
+    t.tick("BigInteger.modPow(e, n)");
+  }
+
+  public static void main(String[] args) {
+    squareBenchmarks();
+    modBenchmarks();
+  }
+}
\ No newline at end of file

Added: hadoop/mapreduce/trunk/src/test/mapred/org/apache/hadoop/examples/pi/math/TestSummation.java
URL: http://svn.apache.org/viewvc/hadoop/mapreduce/trunk/src/test/mapred/org/apache/hadoop/examples/pi/math/TestSummation.java?rev=790015&view=auto
==============================================================================
--- hadoop/mapreduce/trunk/src/test/mapred/org/apache/hadoop/examples/pi/math/TestSummation.java
(added)
+++ hadoop/mapreduce/trunk/src/test/mapred/org/apache/hadoop/examples/pi/math/TestSummation.java
Wed Jul  1 01:35:55 2009
@@ -0,0 +1,147 @@
+/**
+ * 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.pi.math;
+
+import java.math.BigInteger;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+import java.util.Random;
+
+import org.apache.hadoop.examples.pi.Container;
+import org.apache.hadoop.examples.pi.Util;
+import org.apache.hadoop.examples.pi.Util.Timer;
+import org.apache.hadoop.examples.pi.math.TestModular.Montgomery2;
+
+public class TestSummation extends junit.framework.TestCase {
+  static final Random RANDOM = new Random();
+  static final BigInteger TWO = BigInteger.valueOf(2);
+
+  private static Summation2 newSummation(final long base, final long range, final long delta)
{
+    final ArithmeticProgression N = new ArithmeticProgression('n', base+3, delta, base+3+range);
+    final ArithmeticProgression E = new ArithmeticProgression('e', base+range, -delta, base);
+    return new Summation2(N, E);
+  }
+
+  private static void runTestSubtract(Summation sigma, List<Summation> diff) {
+//    Util.out.println("diff=" + diff);
+    List<Container<Summation>> tmp = new ArrayList<Container<Summation>>(diff.size());
+    for(Summation s : diff)
+      tmp.add(s);
+    final List<Summation> a = sigma.remainingTerms(tmp);
+//    Util.out.println("a   =" + a);
+
+    a.addAll(diff);
+    for(Summation s : a)
+      s.compute();
+
+    final List<Summation> combined = Util.combine(a);
+//    Util.out.println("combined=" + combined);
+    assertEquals(1, combined.size());
+    assertEquals(sigma, combined.get(0));
+  }
+
+  public void testSubtract() {
+    final Summation sigma = newSummation(3, 10000, 20);
+    final int size = 10;
+    final List<Summation> parts = Arrays.asList(sigma.partition(size));
+    Collections.sort(parts);
+
+    runTestSubtract(sigma, new ArrayList<Summation>());
+    runTestSubtract(sigma, parts);
+
+    for(int n = 1; n < size; n++) {
+      for(int j = 0; j < 10; j++) {
+        final List<Summation> diff = new ArrayList<Summation>(parts);
+        for(int i = 0; i < n; i++)
+          diff.remove(RANDOM.nextInt(diff.size()));
+///        Collections.sort(diff);
+        runTestSubtract(sigma, diff);
+      }
+    }
+  }
+  
+  static class Summation2 extends Summation {
+    Summation2(ArithmeticProgression N, ArithmeticProgression E) {
+      super(N, E);
+    }
+
+    
+    final Montgomery2 m2 = new Montgomery2();
+    double compute_montgomery2() {
+      long e = E.value;
+      long n = N.value;
+      double s = 0;
+      for(; e > E.limit; e += E.delta) {
+        m2.set(n);
+        s = Modular.addMod(s, m2.mod2(e)/(double)n);
+        n += N.delta;
+      }
+      return s;
+    }
+
+    double compute_modBigInteger() {
+      long e = E.value;
+      long n = N.value;
+      double s = 0;
+      for(; e > E.limit; e += E.delta) {
+        s = Modular.addMod(s, TestModular.modBigInteger(e, n)/(double)n);
+        n += N.delta;
+      }
+      return s;
+    }
+  
+    double compute_modPow() {
+      long e = E.value;
+      long n = N.value;
+      double s = 0;
+      for(; e > E.limit; e += E.delta) {
+        s = Modular.addMod(s, TWO.modPow(BigInteger.valueOf(e), BigInteger.valueOf(n)).doubleValue()/n);
+        n += N.delta;
+      }
+      return s;
+    }
+  }
+
+  private static void computeBenchmarks(final Summation2 sigma) {
+    final Timer t = new Timer(false);
+    t.tick("sigma=" + sigma);
+    final double value = sigma.compute();
+    t.tick("compute=" + value);
+    assertEquals(value, sigma.compute_modular());
+    t.tick("compute_modular");
+    assertEquals(value, sigma.compute_montgomery());
+    t.tick("compute_montgomery");
+    assertEquals(value, sigma.compute_montgomery2());
+    t.tick("compute_montgomery2");
+
+    assertEquals(value, sigma.compute_modBigInteger());
+    t.tick("compute_modBigInteger");
+    assertEquals(value, sigma.compute_modPow());
+    t.tick("compute_modPow");
+  }
+
+  /** Benchmarks */
+  public static void main(String[] args) {
+    final long delta = 1L << 4;
+    final long range = 1L << 20;
+    for(int i = 20; i < 40; i += 2) 
+      computeBenchmarks(newSummation(1L << i, range, delta));
+  }
+}



Mime
View raw message