+/EE360P

distributed systems

git clone https://git.julia.blue/+/EE360P

vijaygarg1init07ca65d

master
7.9 KiB242 linesraw
1/**
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements.  See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership.  The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License.  You may obtain a copy of the License at
9 *
10 *     http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18package org.apache.hadoop.examples.pi.math;
19
20import java.util.ArrayList;
21import java.util.List;
22
23import org.apache.hadoop.examples.pi.Combinable;
24import org.apache.hadoop.examples.pi.Container;
25import org.apache.hadoop.examples.pi.Util;
26
27/** Represent the summation \sum \frac{2^e \mod n}{n}. */
28public class Summation implements Container<Summation>, Combinable<Summation> {
29  /** Variable n in the summation. */
30  public final ArithmeticProgression N;
31  /** Variable e in the summation. */
32  public final ArithmeticProgression E;
33  private Double value = null;
34
35  /** Constructor */
36  public Summation(ArithmeticProgression N, ArithmeticProgression E) {
37    if (N.getSteps() != E.getSteps()) {
38      throw new IllegalArgumentException("N.getSteps() != E.getSteps(),"
39          + "\n  N.getSteps()=" + N.getSteps() + ", N=" + N
40          + "\n  E.getSteps()=" + E.getSteps() + ", E=" + E);
41    }
42    this.N = N;
43    this.E = E;
44  }
45
46  /** Constructor */
47  Summation(long valueN, long deltaN, 
48            long valueE, long deltaE, long limitE) {
49    this(valueN, deltaN, valueN - deltaN*((valueE - limitE)/deltaE),
50         valueE, deltaE, limitE);
51  }
52
53  /** Constructor */
54  Summation(long valueN, long deltaN, long limitN, 
55            long valueE, long deltaE, long limitE) {
56    this(new ArithmeticProgression('n', valueN, deltaN, limitN),
57         new ArithmeticProgression('e', valueE, deltaE, limitE));
58  }
59
60  /** {@inheritDoc} */
61  @Override
62  public Summation getElement() {return this;}
63
64  /** Return the number of steps of this summation */
65  long getSteps() {return E.getSteps();}
66  
67  /** Return the value of this summation */
68  public Double getValue() {return value;}
69  /** Set the value of this summation */
70  public void setValue(double v) {this.value = v;}
71
72  /** {@inheritDoc} */
73  @Override
74  public String toString() {
75    return "[" + N + "; " + E + (value == null? "]": "]value=" + Double.doubleToLongBits(value)); 
76  }
77
78  /** {@inheritDoc} */
79  @Override
80  public boolean equals(Object obj) {
81    if (obj == this)
82      return true;
83    if (obj != null && obj instanceof Summation) {
84      final Summation that = (Summation)obj;
85      return this.N.equals(that.N) && this.E.equals(that.E);
86    }
87    throw new IllegalArgumentException(obj == null? "obj == null":
88      "obj.getClass()=" + obj.getClass());
89  }
90
91  /** Not supported */
92  @Override
93  public int hashCode() {
94    throw new UnsupportedOperationException();
95  }
96
97  /** Covert a String to a Summation. */
98  public static Summation valueOf(final String s) {
99    int i = 1;
100    int j = s.indexOf("; ", i);
101    if (j < 0)
102      throw new IllegalArgumentException("i=" + i + ", j=" + j + " < 0, s=" + s);
103    final ArithmeticProgression N = ArithmeticProgression.valueOf(s.substring(i, j));
104
105    i = j + 2;
106    j = s.indexOf("]", i);
107    if (j < 0)
108      throw new IllegalArgumentException("i=" + i + ", j=" + j + " < 0, s=" + s);
109    final ArithmeticProgression E = ArithmeticProgression.valueOf(s.substring(i, j));
110
111    final Summation sigma = new Summation(N, E);
112    i = j + 1;
113    if (s.length() > i) {
114      final String value = Util.parseStringVariable("value", s.substring(i));
115      sigma.setValue(value.indexOf('.') < 0?
116          Double.longBitsToDouble(Long.parseLong(value)):
117          Double.parseDouble(value));
118    }
119    return sigma;
120  }
121
122  /** Compute the value of the summation. */
123  public double compute() {
124    if (value == null)
125      value = N.limit <= MAX_MODULAR? compute_modular(): compute_montgomery();
126    return value;
127  }
128
129  private static final long MAX_MODULAR = 1L << 32;
130  /** Compute the value using {@link Modular#mod(long, long)}. */
131  double compute_modular() {
132    long e = E.value;
133    long n = N.value;
134    double s = 0;
135    for(; e > E.limit; e += E.delta) {
136      s = Modular.addMod(s, Modular.mod(e, n)/(double)n);
137      n += N.delta;
138    }
139    return s;
140  }
141
142  final Montgomery montgomery = new Montgomery();
143  /** Compute the value using {@link Montgomery#mod(long)}. */
144  double compute_montgomery() {
145    long e = E.value;
146    long n = N.value;
147    double s = 0;
148    for(; e > E.limit; e += E.delta) {
149      s = Modular.addMod(s, montgomery.set(n).mod(e)/(double)n);
150      n += N.delta;
151    }
152    return s;
153  }
154
155  /** {@inheritDoc} */
156  @Override
157  public int compareTo(Summation that) {
158    final int de = this.E.compareTo(that.E);
159    if (de != 0) return de;
160    return this.N.compareTo(that.N);
161  }
162
163  /** {@inheritDoc} */
164  @Override
165  public Summation combine(Summation that) {
166    if (this.N.delta != that.N.delta || this.E.delta != that.E.delta) 
167      throw new IllegalArgumentException(
168          "this.N.delta != that.N.delta || this.E.delta != that.E.delta"
169          + ",\n  this=" + this
170          + ",\n  that=" + that);
171    if (this.E.limit == that.E.value && this.N.limit == that.N.value) {
172      final double v = Modular.addMod(this.value, that.value);
173      final Summation s = new Summation(
174          new ArithmeticProgression(N.symbol, N.value, N.delta, that.N.limit),
175          new ArithmeticProgression(E.symbol, E.value, E.delta, that.E.limit));
176      s.setValue(v);
177      return s;
178    }
179    return null;
180  }
181
182  /** Find the remaining terms. */
183  public <T extends Container<Summation>> List<Summation> remainingTerms(List<T> sorted) {
184    final List<Summation> results = new ArrayList<Summation>();
185    Summation remaining = this;
186
187    if (sorted != null)
188      for(Container<Summation> c : sorted) {
189        final Summation sigma = c.getElement();
190        if (!remaining.contains(sigma))
191          throw new IllegalArgumentException("!remaining.contains(s),"
192              + "\n  remaining = " + remaining
193              + "\n  s         = " + sigma          
194              + "\n  this      = " + this
195              + "\n  sorted    = " + sorted);
196
197        final Summation s = new Summation(sigma.N.limit, N.delta, remaining.N.limit,
198                                          sigma.E.limit, E.delta, remaining.E.limit);
199        if (s.getSteps() > 0)
200          results.add(s);
201        remaining = new Summation(remaining.N.value, N.delta, sigma.N.value,
202                                  remaining.E.value, E.delta, sigma.E.value);
203      }
204
205    if (remaining.getSteps() > 0)
206      results.add(remaining);
207  
208    return results;
209  }
210
211  /** Does this contains that? */
212  public boolean contains(Summation that) {
213    return this.N.contains(that.N) && this.E.contains(that.E);    
214  }
215
216  /** Partition the summation. */
217  public Summation[] partition(final int nParts) {
218    final Summation[] parts = new Summation[nParts];
219    final long steps = (E.limit - E.value)/E.delta + 1;
220
221    long prevN = N.value;
222    long prevE = E.value;
223
224    for(int i = 1; i < parts.length; i++) {
225      final long k = (i * steps)/parts.length;
226
227      final long currN = N.skip(k);
228      final long currE = E.skip(k);
229      parts[i - 1] = new Summation(
230          new ArithmeticProgression(N.symbol, prevN, N.delta, currN),
231          new ArithmeticProgression(E.symbol, prevE, E.delta, currE));
232
233      prevN = currN;
234      prevE = currE;
235    }
236
237    parts[parts.length - 1] = new Summation(
238        new ArithmeticProgression(N.symbol, prevN, N.delta, N.limit),
239        new ArithmeticProgression(E.symbol, prevE, E.delta, E.limit));
240    return parts;
241  }
242}