Verwendungsbeispiel des ForkJoin Frameworks: Berechnung einer großen Fibonacci-Zahl

Thomas Darimont · 28. Februar 2012

Hallo,

inspiriert von der Aufgabe von Heinz Kabutz (http://weblogs.java.net/blog/kabutz/archive/2012/02/24/fibonacci-1000000000-challenge) habe ich mal ein kleines Beispiel zur parallelen Berechnung von großen Fibonacci-Zahlen (http://de.wikipedia.org/wiki/Fibonacci-Folge) mit dem "neuen" ForkJoin Framework in Java 7.

Leider ist mein Rechner (Core 2 Duo, QuadCore 2,4 GHz) nicht flott genug um die Fibonacci Zahl von f(1_000_000_000) innerhalb einer annehmbaren Zeit auszurechnen... (dauert > 3 Stunden).

Vielleicht lässt sich die Berechnung ja noch etwas tunen... immerhin für f(10_000_000) brauche ich in der paralellen Variante "nur" 53865 ms

Schaut mal hier:

Java:

package de.tutorials;

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Date;
import java.util.Formatter;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
import java.util.concurrent.TimeUnit;

public class FibFJ3 {



	public static void main(String[] args) throws Exception {
		int number = 

				//	1_000_000_000
						 10_000_000
				//				1_000_000
				//				100_000
				;
		
		printResultDetails("parallel", new Date(), demonstrateParallelComputationOfFibonacci(number));
		System.out.println("#############");
		printResultDetails("sequential", new Date(), demonstrateSequentialComputationOfFibonacci(number));
	}
	
	static class Env {
		private static final int SEQUENTIAL_THRESHOLD = 32; // fib 88 fits into into int-range

		ForkJoinPool pool;
		Map<Key, BigInteger> cache;
		
		public Env(int number) {
			cache = new ConcurrentHashMap<>(number / 2);
			pool = new ForkJoinPool(10 /*Runtime.getRuntime().availableProcessors()*2*/);
		}

	}

	private static BigInteger demonstrateParallelComputationOfFibonacci(int number) throws InterruptedException, ExecutionException {
		Env env = new Env(number);
		return env.pool.submit(new Fib(number, env)).get();
	}

	private static void printResultDetails(String computingMethod, Date startDate, BigInteger result) {
		System.out.println("Computing Method: " + computingMethod);
		System.out.println("Start: " + startDate);
		Date endDate = new Date();
		System.out.println("End: " + endDate + " took " + (endDate.getTime() - startDate.getTime()) + " ms");
		byte[] resultBytes = result.toByteArray();
		System.out.println("Bytes: " + resultBytes.length);

		int numBytes = Math.min(10, resultBytes.length);
		String firstBytesAsString = asHexString(Arrays.copyOf(resultBytes, numBytes));
		System.out.printf("First %s bytes: %s\n", numBytes, firstBytesAsString);
		String lastBytesAsString = asHexString(Arrays.copyOfRange(resultBytes, resultBytes.length - numBytes, resultBytes.length));
		System.out.printf("Last %s bytes: %s\n", numBytes, lastBytesAsString);
		System.out.println("Last 10 digits: " + result.mod(BigInteger.TEN.pow(numBytes)));
	}
	
	private static BigInteger demonstrateSequentialComputationOfFibonacci(int number) {
		BigInteger current = BigInteger.ONE;
		BigInteger previous = BigInteger.ZERO;
		BigInteger result = null;
		for (int j = 2; j <= number; j++) {
			result = current.add(previous);
			previous = current;
			current = result;
		}
		return result;
	}

	private static String asHexString(byte[] bytes) {
		Formatter formatter = new Formatter();
		for (byte b : bytes) {
			formatter.format("%02x", b);
		}
		return formatter.toString();
	}

	static class Fib extends RecursiveTask<BigInteger> {

		private final int number;

		private final Key key;

		private final Env env;

		public Fib(int number, Env env) {
			this.number = number;
			this.key = new Key(number);
			this.env = env;
		}

		protected BigInteger compute() {
			//Auslagern dieses Zweigs in computeDirectly() verlangsamt die Berechnung extrem!
			BigInteger result = null;
			if ((result = env.cache.get(key)) != null) {
				return result;
			} else if (number <= Env.SEQUENTIAL_THRESHOLD) {
				long current = 1;
				long previous = 0;
				long res = current;
				for (int j = 2; j <= number; j++) {
					res = current + previous;
					previous = current;
					current = res;
				}
				result = new BigInteger(""+res);
			} else {
			//Auslagern dieses Zweigs in computeParallel() verlangsamt die Berechnung extrem!
				
				//Zerlegeung der Berechnung der Fibonacci-Zahl in parallel berechenbare Einheiten
				// f(m+n) = f(n+1) * f(m) + f(n) * f(m-1)
				// Fibonacci Identity from Wikipedia
				// http://de.wikipedia.org/wiki/Fibonacci-Folge
				int n = number / 2;
				int m = number - n;

				Fib fib0 = new Fib(n + 1, env);
				Fib fib1 = new Fib(m, env);
				Fib fib2 = new Fib(n, env);
				Fib fib3 = new Fib(m - 1, env);
				FibMultiply mul0 = new FibMultiply(fib0, fib1);
				FibMultiply mul1 = new FibMultiply(fib2, fib3);

				invokeAll(mul0, mul1);
				
				result = mul0.getRawResult().add(mul1.getRawResult());
			}

			env.cache.put(key, result);

			return result;
		}

		@SuppressWarnings("serial")
		static class FibMultiply extends RecursiveTask<BigInteger> {
			
			private final Fib fib0;
			private final Fib fib1;

			public FibMultiply(Fib fib0, Fib fib1) {
				this.fib0 = fib0;
				this.fib1 = fib1;
			}

			@Override
			protected BigInteger compute() {
				invokeAll(fib0, fib1);
				return fib0.getRawResult().multiply(fib1.getRawResult());
			}
		}
	}

	static class Key{
		private final int key;

		public Key(int key) {
			this.key = key;
		}

		@Override
		public int hashCode() {
			return key;
		}

		@Override
		public boolean equals(Object that) {
			return ((Key) that).key == this.key;
		}
	}
}

Ausgabe:

Code:

Computing Method: parallel
Start: Tue Feb 28 20:58:42 CET 2012
End: Tue Feb 28 20:58:42 CET 2012 took 585 ms
Bytes: 86781
First 10 bytes: 01af55e1cb1fc03c5061
Last 10 bytes: 6315c506ab88705714bb
Last 10 digits: 8242546875
#############
Computing Method: sequential
Start: Tue Feb 28 20:58:43 CET 2012
End: Tue Feb 28 20:59:24 CET 2012 took 41568 ms
Bytes: 86781
First 10 bytes: 01af55e1cb1fc03c5061
Last 10 bytes: 6315c506ab88705714bb
Last 10 digits: 8242546875

Zur Überprüfung die Berechnung von Wolfram Alpha:
http://www.wolframalpha.com/input/?i=fib(1000000)+mod+10^10

Ergebnis (letzte 10 Stellen): 8242546875

Gruß Tom

genodeftest · 28. Februar 2012

Der Vergleich hinkt aber ein bisschen, weil die parallele Variante deutlich effizienter rechnet als die sequentielle…
Und das Beispiel zeigt mal wieder, dass BigInteger extrem ineffizient ist (siehe Kommentare zu dem verlinkten Artikel)

Thomas Darimont · 28. Februar 2012

Hallo,

das sollte ja kein Benchmark, sondern eher ein Beispiel zur möglichen Verwendung des ForkJoin-Frameworks sein

Gruß Tom

Verwendungsbeispiel des ForkJoin Frameworks: Berechnung einer großen Fibonacci-Zahl

Thomas Darimont

Erfahrenes Mitglied

genodeftest

Erfahrenes Mitglied

Thomas Darimont

Erfahrenes Mitglied

Neue Beiträge