Skandium Tutorial

Tutorial: Pi Decimals Computation

For a grasp of the basic concepts in Algorithmic Skeletons you should first read the programming model section.

This tutorial shows how to compute Pi with up to a specified number of decimals using the Skandium Library.

Any program using Skandium Library should follow these steps.

Identify the skeleton patterns and their nesting for the application.

In this tutorial we will use the Map skeleton. Our strategy will be to divide the number of decimals into intervals which can be computed independently.
Fill the skeleton patterns with the application's muscle codes.

For Map this corresponds to three types of muscles: Split, Execute, and Merge.
Define which will be the Types used to move data from one muscle to the next.

For this example we create an Interval type used to input the start and end positions. For the result of the computation we will use a standard Java type BigDecimal to represent the computed Pi.
Input the data and wait for the results.

Which corresponds to the main's thread execution.

Main Execution

Four steps are required to use the library. Step 1 is to initialize a new Skeleton pattern with the provided muscle codes and data types (presented later). Then step 2 inputs the actual data into the Skandium Library, the number of threads used is the the default number of cores, and shared among multiple invocations. In the example we only input one interval to compute, but it is possible to input several data, each generating its own Future object which will hold the result of the computation. Step 3 shows that the computation is asynchronous, while it takes place the main thread can perform other activities. Finally in step 4 we either return the computation's result or block until it is available.

// 1. Define the skeleton program structure
Skeleton<Interval, BigDecimal> bbp = new Map<Interval, BigDecimal>(
	//number of parts to divide by
	new SplitInterval(Runtime.getRuntime().availableProcessors()*2), 
	new PiComputer(),
	new MergeResults());

// 2. Input parameters
Future<BigDecimal> future = bbp.input(new Interval(0, 3000));

// 3. Do something else...
// ...

// 4. Block for the results
BigDecimal pi = future.get();
System.out.println(pi);

Data Types: Interval & BigDecimal

The data types are the object which will be used to transfer the computation between the Muscle codes. They can be either new types defined by the programmer or existing types. In this example we use one of each.

The first one is the input type of the application, an Interval which hold the start and end positions of the decimals to compute.

public class Interval {
	
    int start; //The initial decimal position
    int end;   //The final decimal position

    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

For the result (Pi) we use the BigDecimal type class which is part of Java, and capable of holding an arbitrary number of decimal values.

java.math.BigDecimal

Split: SplitInterval

A Split muscle is responsible of transforming a single data element into a list of elements. While in this example the single element's type is the same as the list's elements type, they may be different.

A split muscle is identified with the Split<P,R> interface which requires the implementation of the public R[] split(P[]); method.

In this example we divide the Interval into a predefined number of parts. The result is a list of non overlapping intervals which represent the original interval. This implementation is stateless, and therefore does not require the synchronized keyword, as stated in the programming model section.

This implementation is stateless, and therefore does not require the synchronized keyword, as stated in the programming model section.

public class SplitInterval implements Split<Interval,Interval> {

	int numParts; //The number of sub intervals to create from an Interval
	
	public SplitInterval(int numParts){
		this.numParts=numParts;
	}
	
	@Override
	public Interval[] split(Interval param) throws Exception {
		
		int size = (param.end - param.start)/numParts;
		Interval[] result = new Interval[numParts];
		
		for(int i=0; i

		Execute: PiComputer
		An Execute muscle is responsible for transforming a data element into another element, in other words, performing the computation.

		In this example we show how the Bailey-Borwein-Plouffe formula is used to compute the decimals of Pi for a given Interval.

		Note that this algorithm is not optimal as BigDecimal operations become slower when more precision is used. Hence, a better implementation should compute the hexadecimal values of Pi with primitive types. Let us know if you want to provide such implementation.

		This implementation is stateless, and therefore does not require the synchronized keyword, as stated in the programming model section.
		public class PiComputer implements Execute<Interval, BigDecimal>{
	
    private static final int ROUND_MODE = BigDecimal.ROUND_HALF_EVEN;
    private BigDecimal ZERO             = new BigDecimal("0");
    private BigDecimal ONE              = new BigDecimal("1");
    private BigDecimal OPPOSITE_ONE     = new BigDecimal("-1");
    private BigDecimal OPPOSITE_TWO     = new BigDecimal("-2");
    private BigDecimal FOUR             = new BigDecimal("4");
    private BigDecimal FIVE             = new BigDecimal("5");
    private BigDecimal SIX              = new BigDecimal("6");
    private BigDecimal EIGHT            = new BigDecimal("8");
    private BigInteger SIXTEEN          = new BigInteger("16");
    
    @Override
    public BigDecimal execute(Interval interval) {

	//scale trick to hold enough precision
	int scale = (int) Math.floor(interval.end*1.2);
	BigDecimal bd = ZERO.setScale(scale);
		
    	BigDecimal ONE            = this.ONE.setScale(scale);
    	BigDecimal OPPOSITE_ONE   = this.OPPOSITE_ONE.setScale(scale);
    	BigDecimal OPPOSITE_TWO   = this.OPPOSITE_TWO.setScale(scale);
    	BigDecimal FOUR           = this.FOUR.setScale(scale);
    	BigDecimal FIVE           = this.FIVE.setScale(scale);
    	BigDecimal SIX            = this.SIX.setScale(scale);
    	BigDecimal EIGHT          = this.EIGHT.setScale(scale);

        
        // BBP formula for the given interval
        for (int k = interval.start; k <= interval.end; k++) {
            bd = bd.add(f(k, interval.end, 
                          EIGHT, ONE, FOUR, FIVE, SIX, OPPOSITE_TWO, OPPOSITE_ONE));
        }
        
        return bd;
    }

    private BigDecimal f(int k, int scale, 
    	  BigDecimal EIGHT, BigDecimal ONE, BigDecimal FOUR, BigDecimal FIVE, 
	  BigDecimal SIX, BigDecimal OPPOSITE_TWO, BigDecimal OPPOSITE_ONE) {
    	
        BigDecimal K       =  new BigDecimal(k);
        BigDecimal EIGHT_K =  EIGHT.multiply(K);
        BigDecimal FIRST   =  ONE.divide(new BigDecimal(SIXTEEN.pow(k)), ROUND_MODE);
        BigDecimal SECOND  =  FOUR.divide(EIGHT_K.add(ONE), ROUND_MODE);
        BigDecimal THIRD   =  OPPOSITE_TWO.divide(EIGHT_K.add(FOUR), ROUND_MODE);
        BigDecimal FOURTH  =  OPPOSITE_ONE.divide(EIGHT_K.add(FIVE), ROUND_MODE);
        BigDecimal FIFTH   =  OPPOSITE_ONE.divide(EIGHT_K.add(SIX), ROUND_MODE);

        return FIRST.multiply(SECOND.add(THIRD.add(FOURTH.add(FIFTH))));
    }

}


		Merge: MergeResults
		A Merge muscle is responsible for reducing a list of elements into a single one. While the input and output types may differ in this example they have the same (BigDecimal). In this example we simply add the BigDecimal results to yield a single results.

		A merge muscle is identified bu the Merge interface, which requires the implementation of public R merge(P[]);
		This implementation is stateless, and therefore does not require the synchronized keyword, as stated in the programming model section.
		public class MergeResults implements Merge<BigDecimal, BigDecimal>{

	@Override
	public BigDecimal merge(BigDecimal[] param) throws Exception {
		
		BigDecimal total = new BigDecimal(0);

		for (int i = 0; i < param.length; i++) {
			total = total.add(param[i]);
		}

        	return total;
	}
}

	Result: Pi for 3000+ decimals

For the curious these are a bunch of Pi decimals computed with the program.
Unverified after the second decimal though.

3.14159265358979323846264338327950288419716939937510582097494459230781640628620
8998628034825342117067982148086513282306647093844609550582231725359408128481117
4502841027019385211055596446229489549303819644288109756659334461284756482337867
8316527120190914564856692346034861045432664821339360726024914127372458700660631
5588174881520920962829254091715364367892590360011330530548820466521384146951941
5116094330572703657595919530921861173819326117931051185129279195828404095758342
7271158524554297359757237833565277224063195158856944786383436438521778284319561
6496099841457874741740482300613978224118875085610526863518559116005176379420611
7989072439979468056619974076130553856309073557819717209571292289138789176880246
8716624480023784199933930006850298542284132085445470353746893449533447472432811
7770540036283189165441087295240342319595512046854749487617032155606442006286152
2362170173040361042255887742755877736932817766371074126119101032141671368883497
9745923254188381764491235681566695058088329828825668836283514089390689098870439
8120154668644472362723384847359332611811934661195302678366595205891098060526974
8389467819678611656625178550559202128204449609493153985620358711100079511525027
3140335448558751597034960124407499983676541055374961316767588100495581004369483
1166810106031218105615867891021976926183053113875550978419266499987750322775634
7939822768406677023657553650997470959667933124409820449865919911316570723671824
2002996602993734414230335017364242947203116234205049443851054237739025868242066
0059842052469811997619904305042163748992086185818929019680806992756011754693069
3396390965645185211570675646930951394864278673555061961292105971215108210814688
9178246266083318572769064045766797855910236624714584146732265142478110202348638
5153027923721991020022089907843971629746416063285076537413380266355175357754093
2890344306986964765992664742642649180128503380572591235151738778050302857221824
0967608050225807978254096396753188909997881588790605135312589285708357835530045
1365056115023134866025471747226869456937820662690472981687179452809379262243044
9861326922191351229975953687641817206692194650588116013200749929311303050286742
3186099447612018237603869778774641305014901950383698455116140346253274698167002
9065811213427325505990629506042276381995673816012319398522430775052885655458226
1372662965851505489912966794591477649770726143574358905889642392265128619329100
5392744819622317777283589003778912353396065566171650887090010811509497268702829
1798930857628447835297672798289041674467070207333939307367087599839852616102145
4253942277622856296020903780648839001085457171821238717692859571087581331604686
5128859446653760775433831702702789617235266323773098636480930169978018435190405
6559286018320458063998464102395048519357597998934053865169143493534463923192703
9278721674199095515601848508994269368400861435100273863723505916808040186974674
8716799337130415882562537307740419761247652006460151139295725279880429447237262
0098171470913858681035085862149018229246747592850909485406504327074828567944942
2870134198105730568000736560682119804325542952412757610863818350839660281010225
2300943486869619936265604332774452892673220854365644554445238094475501939340087
6111093202332602672517875136001497867262994300565662887804284551615791103575290
6584186351844610147239754649507189942803824093683211430178560411084637595889908
3749468221048883192898047099749471752948849726837903858865952796557144245043631
3415688757733060586415590298530281900091261905269956569504135342076590550563631
0407311870887979834008177837220287921088907943031713525782864676061236389970133
5708326351995231558235018620522574018426454680527414835193607245886090652508992
1217642007451073874841339594562692152260852659118821971559997313962698710825554
2360082611014162877765424821236657304790367907387772073344558559083000036655031
2766696857825034049228516091123549299688525058443587711268775938788646489441544
3853176503225146150137280302288523008280842140697816407463637031331370104497929
3825243062235817672605110837401643914089395224236167972523736970271208442135959
3519548653197040867341148294636448717039986558782077843599565770002915457987425
5253704938355507282739829844192225838283538707925831047947354740976465102085315
2370921520877984351636039233199004682143708351266862216307352405047355369752263
3288376043175013201465090888666082374415664738373987357946296162349076935312713
1671957428473041975766943158232665347982403643713214203699537180239172471493678
0777289362564476995375253177333261727514124626866374343893080547706878545970950
2117665648998675920412127072658144914998900264981074563161873572023223595581613
5217328385693816442010469632680833376324845694292288279005368754336468455250584
3874865407321537714036340819779796767376692989654666636973262126764978413741137
7204708454604150263224939191932266877303363834969624787604095974696330542205157
7467195948577411916730936659469939882318252139639547038195072191709893526866999
4159728902918819558802206364119533107827995905662863870771474562298592461403742
5954284241456693582571864711488452978503798941452997383537184607627981455908558
1114654938291772133922734218078035712305538071925493820046056828687899450459937
4844946100395606626958893585346057086925114139578983921235707369711314622297505
8733655369942515975689513163352886707940629793744983457552835068638674558529111
1919100554808710125329981503303227309174513573774567782762767468824249670490381
2997566884933822555045064422063338901388374684926950954070291393207526557065029
0178370322125526082849717573981807916463562253642246874394016531506094436789860
7369369973031061879061488127421512353394207787274764797635322189145479232788723
5415859003828402440354573748888089502624558291861329550806411142525782153757944
7933487827595148646573157235553370848080423599887712654355917359222889810904745
0409510979884701640872584450093793578131371335806462691268958669286385849870870
9858709395985322239870656905159222445974037098079560724654540235441809927383668
0271259838870022074607816797879040823424291386675427074669297305564138282081024
6916752932925141125366129724182469903345486993227983378023707943949222349910841
8884184173182517086976413047492581374650245029838911716473266083439043296865290
1016478985076101968503244913327278981401145988717775866452182628627386038609712
4125436940653184959808763322772601150928006754718374731970125706651787878672476
4574340623399745334972035331231956037364928343533083375257691314111870843963392
3698869833059116797032599316343125740554310211201323271828730040288251553004902
9562742132607771510394388263087447253024987923401698214952980301579405714966368
9197826202564213385511951562437180078219824646625920898885204895465936283249979
1941735147716916057278729887520147790946348610341182277014378776066113888061595
4932488705229767750569428738199445744097254515979615837889674754912310136656355
5760708001073832734703588655861019382592132131013435767135685543442906793836109
5090831573077658980967876650963619223159580465806998376917180103086692885244718
2589956836090120242623449187526521200200317521197533555133312044165707669667062
9170474985953293882608389824131496198739275630473601865538333978696707298387101
3971229831847805641985441998884801601853393671073631417394795075778584990566947
4949071236109

Skandium Library

Sample navigation menu:

Presentation

Sections

Tutorial: Pi Decimals Computation

Main Execution

Data Types: Interval & BigDecimal

Split: SplitInterval

Execute: PiComputer

Merge: MergeResults

Result: Pi for 3000+ decimals