+/EE360P
distributed systems
git clone https://git.julia.blue/+/EE360P
07ca65d
master
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. */ 30public final ArithmeticProgression N ; 31/** Variable e in the summation. */ 32public final ArithmeticProgression E ; 33private Double value =null ; 34 35/** Constructor */ 36public Summation (ArithmeticProgression N ,ArithmeticProgression E ) { 37if (N .getSteps () !=E .getSteps ()) { 38throw new IllegalArgumentException ("N.getSteps() != E.getSteps()," 39 +"\n N.getSteps()=" +N .getSteps () +", N=" +N 40 +"\n E.getSteps()=" +E .getSteps () +", E=" +E ); 41 } 42this .N =N ; 43this .E =E ; 44 } 45 46/** Constructor */ 47Summation (long valueN ,long deltaN , 48long valueE ,long deltaE ,long limitE ) { 49this (valueN ,deltaN ,valueN -deltaN *((valueE -limitE )/deltaE ), 50valueE ,deltaE ,limitE ); 51 } 52 53/** Constructor */ 54Summation (long valueN ,long deltaN ,long limitN , 55long valueE ,long deltaE ,long limitE ) { 56this (new ArithmeticProgression ('n' ,valueN ,deltaN ,limitN ), 57new ArithmeticProgression ('e' ,valueE ,deltaE ,limitE )); 58 } 59 60/** {@inheritDoc} */ 61@ Override 62public Summation getElement () {return this ;} 63 64/** Return the number of steps of this summation */ 65long getSteps () {return E .getSteps ();} 66 67/** Return the value of this summation */ 68public Double getValue () {return value ;} 69/** Set the value of this summation */ 70public void setValue (double v ) {this .value =v ;} 71 72/** {@inheritDoc} */ 73@ Override 74public String toString () { 75return "[" +N +"; " +E + (value ==null ?"]" :"]value=" +Double .doubleToLongBits (value )); 76 } 77 78/** {@inheritDoc} */ 79@ Override 80public boolean equals (Object obj ) { 81if (obj ==this ) 82return true ; 83if (obj !=null &&obj instanceof Summation ) { 84final Summation that = (Summation )obj ; 85return this .N .equals (that .N ) &&this .E .equals (that .E ); 86 } 87throw new IllegalArgumentException (obj ==null ?"obj == null" : 88"obj.getClass()=" +obj .getClass ()); 89 } 90 91/** Not supported */ 92@ Override 93public int hashCode () { 94throw new UnsupportedOperationException (); 95 } 96 97/** Covert a String to a Summation. */ 98public static Summation valueOf (final String s ) { 99int i =1 ; 100int j =s .indexOf ("; " ,i ); 101if (j <0 ) 102throw new IllegalArgumentException ("i=" +i +", j=" +j +" < 0, s=" +s ); 103final ArithmeticProgression N =ArithmeticProgression .valueOf (s .substring (i ,j )); 104 105i =j +2 ; 106j =s .indexOf ("]" ,i ); 107if (j <0 ) 108throw new IllegalArgumentException ("i=" +i +", j=" +j +" < 0, s=" +s ); 109final ArithmeticProgression E =ArithmeticProgression .valueOf (s .substring (i ,j )); 110 111final Summation sigma =new Summation (N ,E ); 112i =j +1 ; 113if (s .length () >i ) { 114final String value =Util .parseStringVariable ("value" ,s .substring (i )); 115sigma .setValue (value .indexOf ('.' ) <0 ? 116Double .longBitsToDouble (Long .parseLong (value )): 117Double .parseDouble (value )); 118 } 119return sigma ; 120 } 121 122/** Compute the value of the summation. */ 123public double compute () { 124if (value ==null ) 125value =N .limit <=MAX_MODULAR ?compute_modular ():compute_montgomery (); 126return value ; 127 } 128 129private static final long MAX_MODULAR =1L <<32 ; 130/** Compute the value using {@link Modular#mod(long, long)}. */ 131double compute_modular () { 132long e =E .value ; 133long n =N .value ; 134double s =0 ; 135for (;e >E .limit ;e +=E .delta ) { 136s =Modular .addMod (s ,Modular .mod (e ,n )/(double )n ); 137n +=N .delta ; 138 } 139return s ; 140 } 141 142final Montgomery montgomery =new Montgomery (); 143/** Compute the value using {@link Montgomery#mod(long)}. */ 144double compute_montgomery () { 145long e =E .value ; 146long n =N .value ; 147double s =0 ; 148for (;e >E .limit ;e +=E .delta ) { 149s =Modular .addMod (s ,montgomery .set (n ).mod (e )/(double )n ); 150n +=N .delta ; 151 } 152return s ; 153 } 154 155/** {@inheritDoc} */ 156@ Override 157public int compareTo (Summation that ) { 158final int de =this .E .compareTo (that .E ); 159if (de !=0 )return de ; 160return this .N .compareTo (that .N ); 161 } 162 163/** {@inheritDoc} */ 164@ Override 165public Summation combine (Summation that ) { 166if (this .N .delta !=that .N .delta ||this .E .delta !=that .E .delta ) 167throw new IllegalArgumentException ( 168"this.N.delta != that.N.delta || this.E.delta != that.E.delta" 169 +",\n this=" +this 170 +",\n that=" +that ); 171if (this .E .limit ==that .E .value &&this .N .limit ==that .N .value ) { 172final double v =Modular .addMod (this .value ,that .value ); 173final Summation s =new Summation ( 174new ArithmeticProgression (N .symbol ,N .value ,N .delta ,that .N .limit ), 175new ArithmeticProgression (E .symbol ,E .value ,E .delta ,that .E .limit )); 176s .setValue (v ); 177return s ; 178 } 179return null ; 180 } 181 182/** Find the remaining terms. */ 183public <T extends Container <Summation >>List <Summation >remainingTerms (List <T >sorted ) { 184final List <Summation >results =new ArrayList <Summation >(); 185Summation remaining =this ; 186 187if (sorted !=null ) 188for (Container <Summation >c :sorted ) { 189final Summation sigma =c .getElement (); 190if (!remaining .contains (sigma )) 191throw new IllegalArgumentException ("!remaining.contains(s)," 192 +"\n remaining = " +remaining 193 +"\n s = " +sigma 194 +"\n this = " +this 195 +"\n sorted = " +sorted ); 196 197final Summation s =new Summation (sigma .N .limit ,N .delta ,remaining .N .limit , 198sigma .E .limit ,E .delta ,remaining .E .limit ); 199if (s .getSteps () >0 ) 200results .add (s ); 201remaining =new Summation (remaining .N .value ,N .delta ,sigma .N .value , 202remaining .E .value ,E .delta ,sigma .E .value ); 203 } 204 205if (remaining .getSteps () >0 ) 206results .add (remaining ); 207 208return results ; 209 } 210 211/** Does this contains that? */ 212public boolean contains (Summation that ) { 213return this .N .contains (that .N ) &&this .E .contains (that .E ); 214 } 215 216/** Partition the summation. */ 217public Summation []partition (final int nParts ) { 218final Summation []parts =new Summation [nParts ]; 219final long steps = (E .limit -E .value )/E .delta +1 ; 220 221long prevN =N .value ; 222long prevE =E .value ; 223 224for (int i =1 ;i <parts .length ;i ++) { 225final long k = (i *steps )/parts .length ; 226 227final long currN =N .skip (k ); 228final long currE =E .skip (k ); 229parts [i -1 ] =new Summation ( 230new ArithmeticProgression (N .symbol ,prevN ,N .delta ,currN ), 231new ArithmeticProgression (E .symbol ,prevE ,E .delta ,currE )); 232 233prevN =currN ; 234prevE =currE ; 235 } 236 237parts [parts .length -1 ] =new Summation ( 238new ArithmeticProgression (N .symbol ,prevN ,N .delta ,N .limit ), 239new ArithmeticProgression (E .symbol ,prevE ,E .delta ,E .limit )); 240return parts ; 241 } 242}