+/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 .io .IOException ; 21import java .util .ArrayList ; 22import java .util .Arrays ; 23import java .util .Collections ; 24import java .util .Iterator ; 25import java .util .List ; 26import java .util .Map ; 27import java .util .TreeMap ; 28import java .util .NoSuchElementException ; 29 30import org .apache .hadoop .examples .pi .Container ; 31import org .apache .hadoop .examples .pi .Util ; 32 33/** 34* Bellard's BBP-type Pi formula 35* 1/2^6 \sum_{n=0}^\infty (-1)^n/2^{10n} 36* (-2^5/(4n+1) -1/(4n+3) +2^8/(10n+1) -2^6/(10n+3) -2^2/(10n+5) 37* -2^2/(10n+7) +1/(10n+9)) 38* 39* References: 40* 41* [1] David H. Bailey, Peter B. Borwein and Simon Plouffe. On the Rapid 42* Computation of Various Polylogarithmic Constants. 43* Math. Comp., 66:903-913, 1996. 44* 45* [2] Fabrice Bellard. A new formula to compute the n'th binary digit of pi, 46* 1997. Available at http://fabrice.bellard.free.fr/pi . 47*/ 48public final class Bellard { 49/** Parameters for the sums */ 50public enum Parameter { 51// \sum_{k=0}^\infty (-1)^{k+1}( 2^{d-10k-1}/(4k+1) + 2^{d-10k-6}/(4k+3) ) 52P8_1 (false ,1 ,8 , -1 ), 53P8_3 (false ,3 ,8 , -6 ), 54P8_5 (P8_1 ), 55P8_7 (P8_3 ), 56 57/* 58* 2^d\sum_{k=0}^\infty (-1)^k( 2^{ 2-10k} / (10k + 1) 59* -2^{ -10k} / (10k + 3) 60* -2^{-4-10k} / (10k + 5) 61* -2^{-4-10k} / (10k + 7) 62* +2^{-6-10k} / (10k + 9) ) 63*/ 64P20_21 (true ,1 ,20 ,2 ), 65P20_3 (false ,3 ,20 ,0 ), 66P20_5 (false ,5 ,20 , -4 ), 67P20_7 (false ,7 ,20 , -4 ), 68P20_9 (true ,9 ,20 , -6 ), 69P20_11 (P20_21 ), 70P20_13 (P20_3 ), 71P20_15 (P20_5 ), 72P20_17 (P20_7 ), 73P20_19 (P20_9 ); 74 75final boolean isplus ; 76final long j ; 77final int deltaN ; 78final int deltaE ; 79final int offsetE ; 80 81private Parameter (boolean isplus ,long j ,int deltaN ,int offsetE ) { 82this .isplus =isplus ; 83this .j =j ; 84this .deltaN =deltaN ; 85this .deltaE = -20 ; 86this .offsetE =offsetE ; 87 } 88 89private Parameter (Parameter p ) { 90this .isplus = !p .isplus ; 91this .j =p .j + (p .deltaN >>1 ); 92this .deltaN =p .deltaN ; 93this .deltaE =p .deltaE ; 94this .offsetE =p .offsetE + (p .deltaE >>1 ); 95 } 96 97/** Get the Parameter represented by the String */ 98public static Parameter get (String s ) { 99s =s .trim (); 100if (s .charAt (0 ) =='P' ) 101s =s .substring (1 ); 102final String []parts =s .split ("\\D+" ); 103if (parts .length >=2 ) { 104final String name ="P" +parts [0 ] +"_" +parts [1 ]; 105for (Parameter p :values ()) 106if (p .name ().equals (name )) 107return p ; 108 } 109throw new IllegalArgumentException ("s=" +s 110 +", parts=" +Arrays .asList (parts )); 111 } 112 } 113 114/** The sums in the Bellard's formula */ 115public static class Sum implements Container <Summation >,Iterable <Summation > { 116private static final long ACCURACY_BIT =50 ; 117 118private final Parameter parameter ; 119private final Summation sigma ; 120private final Summation []parts ; 121private final Tail tail ; 122 123/** Constructor */ 124private <T extends Container <Summation >>Sum (long b ,Parameter p ,int nParts ,List <T >existing ) { 125if (b <0 ) 126throw new IllegalArgumentException ("b = " +b +" < 0" ); 127if (nParts <1 ) 128throw new IllegalArgumentException ("nParts = " +nParts +" < 1" ); 129final long i =p .j ==1 &&p .offsetE >=0 ?1 :0 ; 130final long e =b +i *p .deltaE +p .offsetE ; 131final long n =i *p .deltaN +p .j ; 132 133this .parameter =p ; 134this .sigma =new Summation (n ,p .deltaN ,e ,p .deltaE ,0 ); 135this .parts =partition (sigma ,nParts ,existing ); 136this .tail =new Tail (n ,e ); 137 } 138 139private static <T extends Container <Summation >>Summation []partition ( 140Summation sigma ,int nParts ,List <T >existing ) { 141final List <Summation >parts =new ArrayList <Summation >(); 142if (existing ==null ||existing .isEmpty ()) 143parts .addAll (Arrays .asList (sigma .partition (nParts ))); 144else { 145final long stepsPerPart =sigma .getSteps ()/nParts ; 146final List <Summation >remaining =sigma .remainingTerms (existing ); 147 148for (Summation s :remaining ) { 149final int n = (int )((s .getSteps () -1 )/stepsPerPart ) +1 ; 150parts .addAll (Arrays .asList (s .partition (n ))); 151 } 152 153for (Container <Summation >c :existing ) 154parts .add (c .getElement ()); 155Collections .sort (parts ); 156 } 157return parts .toArray (new Summation [parts .size ()]); 158 } 159 160/** {@inheritDoc} */ 161@ Override 162public String toString () { 163int n =0 ; 164for (Summation s :parts ) 165if (s .getValue () ==null ) 166n ++; 167return getClass ().getSimpleName () +"{" +parameter +": " +sigma 168 +", remaining=" +n +"}" ; 169 } 170 171/** Set the value of sigma */ 172public void setValue (Summation s ) { 173if (s .getValue () ==null ) 174throw new IllegalArgumentException ("s.getValue()" 175 +"\n sigma=" +sigma 176 +"\n s =" +s ); 177if (!s .contains (sigma ) || !sigma .contains (s )) 178throw new IllegalArgumentException ("!s.contains(sigma) || !sigma.contains(s)" 179 +"\n sigma=" +sigma 180 +"\n s =" +s ); 181sigma .setValue (s .getValue ()); 182 } 183 184/** get the value of sigma */ 185public double getValue () { 186if (sigma .getValue () ==null ) { 187double d =0 ; 188for (int i =0 ;i <parts .length ;i ++) 189d =Modular .addMod (d ,parts [i ].compute ()); 190sigma .setValue (d ); 191 } 192 193final double s =Modular .addMod (sigma .getValue (),tail .compute ()); 194return parameter .isplus ?s : -s ; 195 } 196 197/** {@inheritDoc} */ 198@ Override 199public Summation getElement () { 200if (sigma .getValue () ==null ) { 201int i =0 ; 202double d =0 ; 203for (;i <parts .length &&parts [i ].getValue () !=null ;i ++) 204d =Modular .addMod (d ,parts [i ].getValue ()); 205if (i ==parts .length ) 206sigma .setValue (d ); 207 } 208return sigma ; 209 } 210 211/** The sum tail */ 212private class Tail { 213private long n ; 214private long e ; 215 216private Tail (long n ,long e ) { 217this .n =n ; 218this .e =e ; 219 } 220 221private double compute () { 222if (e >0 ) { 223final long edelta = -sigma .E .delta ; 224long q =e /edelta ; 225long r =e %edelta ; 226if (r ==0 ) { 227e =0 ; 228n +=q *sigma .N .delta ; 229 }else { 230e =edelta -r ; 231n += (q +1 )*sigma .N .delta ; 232 } 233 }else if (e <0 ) 234e = -e ; 235 236double s =0 ; 237for (;;e -=sigma .E .delta ) { 238if (e >ACCURACY_BIT || (1L << (ACCURACY_BIT -e )) <n ) 239return s ; 240 241s +=1.0 / (n <<e ); 242if (s >=1 )s --; 243n +=sigma .N .delta ; 244 } 245 } 246 } 247 248/** {@inheritDoc} */ 249@ Override 250public Iterator <Summation >iterator () { 251return new Iterator <Summation >() { 252private int i =0 ; 253 254/** {@inheritDoc} */ 255@ Override 256public boolean hasNext () {return i <parts .length ;} 257/** {@inheritDoc} */ 258@ Override 259public Summation next ()throws NoSuchElementException { 260if (hasNext ()) { 261return parts [i ++]; 262 }else { 263throw new NoSuchElementException ("Sum's iterator does not have next!" ); 264 } 265 } 266/** Unsupported */ 267@ Override 268public void remove () {throw new UnsupportedOperationException ();} 269 }; 270 } 271 } 272 273/** Get the sums for the Bellard formula. */ 274public static <T extends Container <Summation >>Map <Parameter ,Sum >getSums ( 275long b ,int partsPerSum ,Map <Parameter ,List <T >>existing ) { 276final Map <Parameter ,Sum >sums =new TreeMap <Parameter ,Sum >(); 277for (Parameter p :Parameter .values ()) { 278final Sum s =new Sum (b ,p ,partsPerSum ,existing .get (p )); 279Util .out .println ("put " +s ); 280sums .put (p ,s ); 281 } 282return sums ; 283 } 284 285/** Compute bits of Pi from the results. */ 286public static <T extends Container <Summation >>double computePi ( 287final long b ,Map <Parameter ,T >results ) { 288if (results .size () !=Parameter .values ().length ) 289throw new IllegalArgumentException ("m.size() != Parameter.values().length" 290 +", m.size()=" +results .size () 291 +"\n m=" +results ); 292 293double pi =0 ; 294for (Parameter p :Parameter .values ()) { 295final Summation sigma =results .get (p ).getElement (); 296final Sum s =new Sum (b ,p ,1 ,null ); 297s .setValue (sigma ); 298pi =Modular .addMod (pi ,s .getValue ()); 299 } 300return pi ; 301 } 302 303/** Compute bits of Pi in the local machine. */ 304public static double computePi (final long b ) { 305double pi =0 ; 306for (Parameter p :Parameter .values ()) 307pi =Modular .addMod (pi ,new Sum (b ,p ,1 ,null ).getValue ()); 308return pi ; 309 } 310 311/** Estimate the number of terms. */ 312public static long bit2terms (long b ) { 313return 7 *(b /10 ); 314 } 315 316private static void computePi (Util .Timer t ,long b ) { 317t .tick (Util .pi2string (computePi (b ),bit2terms (b ))); 318 } 319 320/** main */ 321public static void main (String []args )throws IOException { 322final Util .Timer t =new Util .Timer (false ); 323 324computePi (t ,0 ); 325computePi (t ,1 ); 326computePi (t ,2 ); 327computePi (t ,3 ); 328computePi (t ,4 ); 329 330Util .printBitSkipped (1008 ); 331computePi (t ,1008 ); 332computePi (t ,1012 ); 333 334long b =10 ; 335for (int i =0 ;i <7 ;i ++) { 336Util .printBitSkipped (b ); 337computePi (t ,b -4 ); 338computePi (t ,b ); 339computePi (t ,b +4 ); 340b *=10 ; 341 } 342 } 343}