Programmieren mit Harald R. Haberstroh

π kann mit Hilfe der folgenden Formel von Strömer (1986) berechnet werden:

^π / ₄ = 44 · arctan ¹/₅₇ + 7 · arctan ¹/₂₃₉ - 12 · arctan ¹/₆₈₂ + 24 · arctan ¹/₁₂₉₄₃

Der Arcustangens wird mit der folgenden Reihenentwicklung

arctan(x) = x - ^x3/₃ + ^x5/₅ - ^x7/₇ + ...

berechnet.

Folgendes Java-Programm verwendet die Klasse BigDecimal zur Berechnung von π. Es soll mittels Threads parallelisiert werden.

import java.math.*;
/**
 * @author Hans Joachim Pflug, RZ, RWTH Aachen
 *
 * Berechnet PI auf eine beliebige Anzahl von Stellen genau
 */
public class Pi {
    private int dec;                  //Anzahl der Dezimalstellen
    private BigDecimal pi = new BigDecimal(0);  //Ergebnis  
    private MathContext m;            //Zur Bestimmung der Laenge der Brueche
    private static final BigDecimal one = new BigDecimal(1);
    private static final BigDecimal four = new BigDecimal(4);
    private BigDecimal r57;           // 1/57
    private BigDecimal r239;          // 1/239
    private BigDecimal r682;          // 1/682
    private BigDecimal r12943;        // 1/12943

    /**
     * Erzeugt ein Objekt mit PI auf die angegebene Stellenzahl genau
     * @param dec Die Stellenzahl, auf die PI berechnet werden soll.
     */
    public Pi(int dec) {
        this.dec = dec;
        m = new MathContext(dec + 5);  //5 als Reserve

        r57 = one.divide(new BigDecimal(57), m);
        r239 = one.divide(new BigDecimal(239), m);
        r682 = one.divide(new BigDecimal(682), m);
        r12943 = one.divide(new BigDecimal(12943), m);

        calculate();
    }

    /**
     * Berechnet den Wert von PI nach der Formel von Stoermer (1896):
     * pi/4 = 44 * arctan(1/57) + 7 * arctan(1/239) - 12 * arctan(1/682) 
     *      + 24 * arctan(1/12943)
     */
    private void calculate() {
        BigDecimal sum1 = arctan(r57).multiply(new BigDecimal(44), m);
        BigDecimal sum2 = arctan(r239).multiply(new BigDecimal(7), m);
        sum1 = sum1.add(sum2, m);
        sum2 = arctan(r682).multiply(new BigDecimal(12), m);
        sum1 = sum1.subtract(sum2, m);
        sum2 = arctan(r12943).multiply(new BigDecimal(24), m);
        sum1 = sum1.add(sum2, m);
        pi = sum1.multiply(four, m);
    }

    /**
     * Berechnet den Arcustangens einer BigDecimal-Zahl.
     * Benutzt die Reihe:
     * arctan(x) = x - x^3/3 + x^5/5 - x^7/7 + ...
     * @param arg Eingabewert
     * @return arctan(arg)
     */
    private BigDecimal arctan(BigDecimal arg) {
        BigDecimal result = new BigDecimal(0);
        BigDecimal z;
        //Abschätzung der Anzahl der Iterationen
        //Nach der Formel  n = - d / log10(x)
        // n: Anzahl der Iterationen
        // d: Anzahl der Stellen fuer Genauigkeit
        // x: Argument des Arcustangens
        //Zwei Stellen Genauigkeit zur Sicherheit
        int iter = (int) -((dec + 2)/ Math.log10(arg.doubleValue()));  

        //Reihenentwicklung
        for (int i = 0; i < iter; i++) {
            int pow = 2 * i + 1;
            z = arg.pow(pow, m).divide(new BigDecimal(pow), m);

            if (i % 2 == 1) {
                z = z.negate();
            }
            result = result.add(z, m);    
        } 
        return result;
    }

    /**
     * Gibt PI formatiert in 100er Bloecken zurueck
     */
    public String toString() {
        String piS = pi.toString();
        StringBuffer b = new StringBuffer();
        b.append("3.1");
        for (int i = 1; i < dec; i++) {
            if (i % 100 == 0) {
                b.append("\n  ");
            } else if (i % 10 == 0) {
                b.append(" ");
            }
            b.append(piS.charAt(i + 2));
        }
        return b.toString();
    }

    public static void main(String args[]) {  
        Pi p = new Pi(1000);
        System.out.println(p);
    }
}

Wieviele Threads sind hier sinnvoll?

Vergleich zwischen serieller und paralleler Berechnung:

Zeitmessungen unter Linux auf einem Intel(R) Core(TM) i3-2100 CPU @ 3.10GHz (Quadcore) (Intel(R) Core(TM) i3 CPU 560 @ 3.33GHz) mit 8GB RAM. Daneben wurden eclipse und chrome verwendet.

Stellen	sequentiell	4 Threads
1000	4,395s	2,530s
2000	35,814s	19,260s
3000	126,145s	65,693s
4000	321,916s	163,393s
5000	626,394s	323,876s
6000	1132,480s	568,905s
7000	1800,781s	912,360s
8000	2753,654s	1462,561s
9000	3941,230s	2134,741s
10000	5527,330s	2878,974s

Bei der JVM kann man nicht bestimmen, ob und wie die Threads auf die CPUs (Kerne) aufgeteilt werden sollen. Die JVM und das Betriebssystem bestimmen, wie die Threads auf CPU-Kerne abgebildet werden. Das ist natürlich auch von der allgemeinen Systemlast abhängig.

Die Messungen zeigen, dass sich die Rechenzeit bei 4 Threads halbiert. Die CPU trägt zwar im Namen "Quadcore", tatsächlich ist es aber nur ein Dualcore mit vier Threads (siehe Link oben). Das bedeutet bei dieser Anwendung, dass nur zwei Threads echt parallel laufen können (weiter geteilt mit den anderen Prozessen, die auf dem System laufen).

Labels: algorithmen, Aufgabe, Java, POS1-3

# Eingestellt von Harald R. Haberstroh @ 22:45