Galileo Computing <openbook>
Galileo Computing - Programming the Net
Galileo Computing - Programming the Net


Java ist auch eine Insel von Christian Ullenboom
Programmieren für die Java 2-Plattform in der Version 1.4
Buch: Java ist auch eine Insel - Zum Katalog
gp Kapitel 5 Mathematisches
  gp 5.1 Arithmetik in Java
    gp 5.1.1 Soll eine Division durch Null zur Übersetzungszeit erkannt werden?
  gp 5.2 Die Funktionen der Math-Klasse
    gp 5.2.1 Attribute
    gp 5.2.2 Winkelfunktionen (trigonometrische Funktionen und Arkusfunktionen)
    gp 5.2.3 Runden von Werten
    gp 5.2.4 Exponentialfunktionen
    gp 5.2.5 Division
    gp 5.2.6 Absolutwerte und Maximum, Minimum
    gp 5.2.7 Zufallszahlen
  gp 5.3 Mathe bitte strikt
    gp 5.3.1 Strikt Fließkomma mit strictfp
    gp 5.3.2 Die Klassen Math und StrictMath
  gp 5.4 Die Random-Klasse
  gp 5.5 Große Zahlen
    gp 5.5.1 Die Klasse BigInteger
    gp 5.5.2 Ganz lange Fakultäten
  gp 5.6 Probleme mit Java und der Mathematik
  gp 5.7 Das Java-Matrix-Paket Jama

Kapitel 5 Mathematisches

Vieles hätte ich verstanden, wenn man es mir nicht erklärt hätte.
– Stanislaw Jerzy Lec


Galileo Computing

5.1 Arithmetik in Java  downtop

Zahlen mit Komma nennen sich Gleitkomma-, Fließkomma-, Fließpunkt- oder Bruchzahlen. Der Begriff »Gleitkommazahl« kommt daher, dass die Zahl durch das Gleiten (Verschieben) des Dezimalpunkts als Produkt aus einer Zahl und einer Potenz der Zahl 10 dargestellt wird (also 1,23 = 123 * 10-2  ).

Java unterstützt für Fließkommazahlen die Typen float und double, die sich nach der Spezifikation IEEE 754 richten. Ein float hat die Länge von 32 Bit und ein double die Länge von 64 Bit. Die Rechenoperationen sind ebenso im IEEE Standard »Binary and Floating-Point Arithmetic« definiert. Neben den unterschiedlichen Größen für double und float definiert das IEEE aber noch positive und negative Zahlen sowie auch eine positive oder negative Null, positives und negatives Unendlich (engl. infinity) und mehrere Zahlen, die eigentlich gar keine sind. Es handelt sich hierbei um NaN, die Abkürzung für Not-A-Number. Sie werden als Fehlerindikator für das Ergebnis von undefinierten Rechenoperationen benutzt, etwa 0/0. NaN ist als Konstante (public static final [float/double] NaN = 0.0f / 0.0f) in den Klassen Double und Float eingefügt.

Außer für den Wert NaN ist auf allen Fließkommazahlen eine totale Ordnung definiert, das heißt, sie lassen sich von der kleinsten Zahl bis zur größten aufzählen. Am Rande steht die negative Unendlichkeit, dann die negativen Zahlen, negative Null, positive Null, positive Zahlen und positives Unendlich. Die positive Null (+0.0) und die negative Null (-0.0) werden nicht unterschieden und sind gleich (0.0==-0.0). So ist auch 0.0 > -0.0 falsch. Dennoch gibt es einen kleinen Unterschied, den wir durch die Rechnung 1.0/-0.0 und 1.0/0.0 leicht sehen. Denn durch den Grenzwert geht das Ergebnis einmal gegen negativ unendlich und einmal gegen positiv unendlich.

Bleibt nur noch die einzige unsortierte Zahl NaN. Alle numerischen Vergleiche <, <=, >, >= mit NaN liefern false. Der Vergleich mit == ist false, wenn einer der Operatoren NaN ist. != verhält sich umgekehrt, ist also true, wenn einer der Operatoren NaN ist.

Die Frage nach dem 0.0/0.0 und 0.0^0.0

Wie wir wissen, ist 0.0/0.0 ein glattes NaN. Im Unterschied zu den Ganzzahlwerten bekommen wir hier allerdings keine Exception, denn dafür ist extra die Spezialzahl NaNNaN eingeführt worden. Interessant ist die Frage, was denn (long)(double)(0.0/0.0) ergibt. Die Sprachdefinition sagt hier in §5.1.3, dass die Konvertierung eines Fließkommawerts NaN ein int 0 oder long 0 ergibt. Leider gab es in den ersten Versionen der JVM einen Fehler, sodass Long.MAX_VALUE anstelle von 0.0 produziert wurde. Dieser Fehler ist aber inzwischen behoben.

Eine weitere spannende Frage ist das Ergebnis von 0.00.0  . Um allgemeine Potenzen zu berechnen, wird die statische Funktion Math.pow(double a, double b) eingesetzt. Wir erinnern uns aus der Schulzeit daran, dass wir die Quadratwurzel einer Zahl ziehen, wenn der Exponent b genau 1/2 ist. Doch jetzt wollen wir wissen, was denn gilt, wenn a=b=0 gilt. §20.11.13 der Sprachdefinition fordert, dass das Ergebnis immer 1.0 ist, wenn der Exponent b -0.0 oder 0.0 ist. Es kommt also in diesem Fall überhaupt nicht auf die Basis a an. In einigen Algebra-Büchern wird 0^0 als undefiniert behandelt. Es ergibt aber durchaus Sinn, 0^0 als 1 zu definieren, da es andernfalls viele Sonderbehandlungen für 0 geben müsste. Hier schreiben die Autoren R. Graham, D. Knuth, O. Patashnik des Buchs Concrete Mathematics ():

»Some textbooks leave the quantity 0^0 undefined, because the functions x^0 and 0^x have different limiting values when x decreases to 0. But this is a mistake. We must define x^0 = 1 for all x, if the binomial theorem is to be valid when x=0, y=0, and/or x=-y. The theorem is too important to be arbitrarily restricted! By contrast, the function 0^x is quite unimportant.«


Galileo Computing

5.1.1 Soll eine Division durch Null zur Übersetzungszeit erkannt werden?  downtop

Ein interessantes Phänomen in Java, das von Compilern ganz unterschiedlich behandelt wird, ist die Division durch Null. Die erste Frage ist, ob die Division zur Laufzeit erkannt und gemeldet werden soll oder nicht. Die zweite ist, wie sich der Compiler verhalten soll, wenn eine Division durch Null erkannt wird, und diese aber zu einem Stück Code gehört, das nie ausgeführt wird.

Listing 5.1   DivNull.java
class DivNull
{
int a = 1 / 0;

int b = false ? 1 / 0 : 5;

boolean b1 = false && 1 / 0 == 1;

boolean b2 = true || 1 / 0 == 1;
}

Der Compiler von Sun, javac, meldet keinen Fehler. Der Jikes-Compiler allerdings meldet in allen Fällen eine

Attempt to divide by zero.

Die Sprachspezifikation von Java äußert sich zwar mehr oder weniger präzise, welche Ausdrücke konstant ausgewertet werden können, jedoch nicht, was bei illegalen Ausdrücken geschehen soll. Denn bis auf die Zuweisung an die Variable a würde das Programm korrekt ausgeführt werden können. Sprich: Der Compiler beschwert sich über Programmkonstrukte, die zur Laufzeit keine Probleme bereiten würden.


Galileo Computing

5.2 Die Funktionen der Math-Klasse  downtop


Galileo Computing

5.2.1 Attribute  downtop

Die Math-Klasse besitzt zwei statische Attribute:


gp  static final double E
Die Eulersche Zahl e=2,718...
gp  static final double PI
Die Kreiszahl pi =3,14159...

Konstanten aus JavaScript

JavaScript definiert noch einige weitere Konstanten, die in Java zurzeit nicht zur Verfügung stehen und die Programmierer selber definieren müssen. Das sind LN2 (natürliche Logarithmus von 2 mit dem ungefähren Wert 0,693), LN10 (natürliche Logarithmus von 10, ca. 2,302), LOG2E (Logarithmus von 2, ca. 1,442), LOG10E (Logarithmus von 10, ca. 0,434), SQRT1_2 (Quadratwurzel aus 0,5, ca. 0,707), SQRT2 (Quadratwurzel aus 2, ca. 1,414).


Galileo Computing

5.2.2 Winkelfunktionen (trigonometrische Funktionen und Arkusfunktionen)  downtop

Die Math-Klasse stellt einigen Winkelfunktionen und ihre Umkehrungen zur Verfügung. Im Gegensatz zur Schulmathematik werden die Winkel für sin(), cos(), tan() im Bogenmaß (2*p entspricht einem Vollkreis) und nicht im Gradmaß (360 Grad entspricht einem Vollkreis) übergeben.

gp  static double sin( double x )
Liefert den Sinus von x.
gp  static double cos( double x )
Liefert den Cosinus von x.
gp  static double tan( double x )
Liefert den Tangens von x.

Die Arcus-Funktionen sind die Umkehrfunktionen zu den trigonometrischen Funktionen. Der Parameter ist kein Winkel, sondern zum Beispiel bei asin() der Sinuswert zwischen –1 und 1. Das Ergebnis ist dann ein Winkel im Bogenmaß, etwa zwischen -p/2 und p/2:

gp  static double asin( double x )
Liefert den Arcus-Sinus von x, wobei -p/2 <= x <= p/2.
gp  static double acos( double x )
Liefert den Arcus-Cosinus von x, wobei 0 <= x <= p.
gp  static double atan( double x )
Liefert den Arcus-Tangens von x, wobei -p/2 <= x <= p/2.
gp  static atan2( double x, double y )
Liefert von der Konvertierung von Rechteckkoordinaten in Polarkoordinaten den Winkel theta, also eine Komponente des Polarkoordinaten-Tupels. Die Vorzeichen der Parameter x und y werden berücksichtigt, und der freie Schenkel des Winkels befindet sich im richtigen Quadranten.

Hyperbolikus Funktionen bietet Java nicht an. In C(++) bietet die Math-Bibliothek sinh(), tanh() und cosh().

Zur Umwandlung eines Winkels von Gradmaß in Bogenmaß und umgekehrt existieren zwei Funktionen:

gp  static double toRadians( double angdeg )
Grad- in Bogenmaß umwandeln.
gp  static double toDegrees( double angrad )
Winkel von Bogen- in Gradmaß umwandeln.

Galileo Computing

5.2.3 Runden von Werten  downtop

Bei der Rundung von Werten können in Java die Methoden verwendet werden: ceil(), floor(), round() und rint().

ceil()

Die Methode dient zum Aufrunden und liefert die nächst höhere Ganzzahl, wenn die Zahl nicht schon eine ganze Zahl ist.

Beispiel ceil(1.1) ergibt den Wert 2. ceil(-1.1) liefert den Wert -1.

floor()

Die Funktion rundet ab. Die Methode ähnelt der ceil()-Methode. Im Gegensatz aber zu dieser Methode wird hier die nächst niedrigere Ganzzahl zurückgegeben. Die Arbeitsweise lässt sich man Besten an einem Beispiel ablesen:

System.out.println(Math.floor(-99.1)); 
   // -100.0
System.out.println(Math.floor(-99)); // -99.0
System.out.println(Math.floor(-.01)); // -1.0
System.out.println(Math.floor(0.1)); // 0.0
System.out.println(Math.floor(99)); // 99

Ganze Zahlen werden nicht verändert.

round() und rint()

Die Funktion round() rundet auf die nächste Ganzzahl vom Typ long (kaufmännische Rundung). Ganze Zahlen werden nicht aufgerundet. rint() ist vergleichbar mit round(), nur liefert es ein double (wie floor() und ceil() auch). rint() ist im Gegensatz zu round() gerecht, was bedeutet, dass bei 0.5 auf die benachbarte gerade Zahl gerundet wird, das heißt es wird in 50 % der Fälle auf- und in 50 % der Fälle abgerundet. Wir können round() zur Typumwandlung einsetzen, als Gegenstück zu (long) d, und d ist ein double, welches immer abrundet. Ein Beispiel zu round():

System.out.println( Math.round(1.01) 
);   //  1
System.out.println( Math.round(-2.1) ); // -2
System.out.println( Math.round(30) ); // 30
Beispiel Die round()-Funktion ist in Java ausprogrammiert. Auf dem Parameter wird 0.5 addiert und der floor()-Methode übergeben.

public static int round(float a) 
{
return (int)floor(a + 0.5f);
}
Beispiel Die rint()-Funktion lässt sich auch einsetzen, wenn Zahlen auf zwei Nachkommastellen gerundet werden sollen. Ist d vom Typ double, so ergibt der Ausdruck Math.rint(d*100.0)/100.0 die gerundete Zahl.

Listing 5.2   Round2Scales.java
class Round2Scales
{
public static double roundScale2( double d )
{
return Math.rint( d * 100 ) / 100.;
}

public static void main( String args[] )
{
System.out.println( roundScale2(+1.341 ) ); // 1.34
System.out.println( roundScale2(-1.341 ) ); // -1.34
System.out.println( roundScale2(+1.345 ) ); // 1.34
System.out.println( roundScale2(-1.345 ) ); // -1.34
System.out.println( roundScale2(+1.347 ) ); // 1.35
System.out.println( roundScale2(-1.347 ) ); // -1.35
}
}

Arbeiten wir anstatt mit rint() mit round() wird die Zahl 1.345 nicht auf 1.34, sondern auf 1.35 gerundet.


Galileo Computing

5.2.4 Exponentialfunktionen  downtop

gp  static double exp( double x )
Liefert den Exponentialwert von x zur Basis e, also e^x.
gp  static double log( double x )
Liefert den natürlichen Logarithmus ln(x).
gp  sqrt static double sqrt( double x )
Liefert die Quadratwurzel von x. sqrt steht für square root.
gp  static double pow( double x, double y )
Liefert den Wert der Potenz x^y.

Galileo Computing

5.2.5 Division  downtop

gp  static double IEEEremainder( double Dividend, double Divisor )
Liefert den Rest der Division von Dividend und Divisor (Modulo-Operator), so wie es IEEE 754-Standard vorschreibt.
Listing 5.3   IEEEremainder.java
public class IEEEremainder
{
public static void main( String args[] )
{
double a = 44.0;
double b = 2.2;

System.out.println(
a % b );
System.out.println(
Math.IEEEremainder( a, b ) );
}
}

Der Unterschied ist deutlich.

2.1999999999999966
-3.552713678800501E-15

Das erste Ergebnis ist mit der mathematischen Ungenauigkeit fast 2.2, aber etwas kleiner, sodass der Algorithmus nicht noch einmal 2.2 abziehen konnte. Die Methode IEEEremainder() liefert ein Ergebnis nahe Null, was korrekt ist, denn 44.0 lässt sich ohne Rest durch 2.2 teilen.


Galileo Computing

5.2.6 Absolutwerte und Maximum, Minimum  downtop

Die abs()-Funktionen liefert den Betrag des Parameters (mathematische Betragsfunktion: y = |x|). Sollte ein negativer Wert als Parameter übergeben werden, so wird dieser in einen positiven Wert umgewandelt. Dabei ist das Ergebnis vom selben Typ wie der Parameter.

gp  static int abs( int x )
gp  static long abs( long x )
gp  static float abs( float x )
gp  static double abs( double x )

Die max()-Funktionen liefern den größeren der übergebenen Werte. Die min()-Funktionen liefern den kleineren von zwei Werten als Rückgabewert. Das Ergebnis ist vom selben Typ wie die Parameter.

gp  static int max( int x, int y )
gp  static long max( long x, long y )
gp  static float max( float x, float y )
gp  static double max( double x, double y )
gp  static int min( int x, int y )
gp  static long min( long x, long y )
gp  static float min( float x, float y )
gp  static double min( double x, double y )

Galileo Computing

5.2.7 Zufallszahlen  downtop

Zufallszahlen zwischen 0 und 1 liefert die Methode math.random(). Möchten wir Werte in einem anderen Wertebereich, so ist es eine einfache Lösung, die Zufallszahlen von Math.random()durch Multiplikation auf den gewünschten Wertebereich auszudehnen und per Addition geeignet zu verschieben. Um ganzzahlige Zufallszahlen zwischen u und o (einschließlich) zu erhalten, berechnen wir u + Math.floor(Math.random() * (o-u+1)). Eine weitere einfache Lösung ist, den Modulo-Operator einzusetzen.


Galileo Computing

5.3 Mathe bitte strikt  downtop

Bei der Berechnung mit Fließkommazahlen schreibt die Definition des IEEE 754-Standard vor, wie numerische Berechnungen durchgeführt werden. Damit soll die CPU für float und double mit 32 bzw. 64 Bit rechnen. In der Wirklichkeit rechnet jedoch so gut wie kein mathematischer Prozessor mit diesen Größen, außer vielleicht AMD mit ihrer 3Dnow!-Technologie. Auf der PC-Seite kommen Intel und AMD mit internen Rechengenauigkeiten von 80 Bit, also 10 Bytes, zum Zuge. Dieses Dilemma betrifft aber nur 80x86 und anderer CISC-Prozessoren. Bei RISC sind 32 Bit und 64 Bit das Übliche. Die 80-Bit-Lösung bringt in Java zwei Nachteile mit sich:

gp  Diese Genauigkeit kann bisher von Java nicht genutzt werden.
gp  Wegen der starren IEE 754-Spezifikation kann der Prozessor weniger Optimierungen durchführen, weil er sich immer eng an die Norm halten muss. Das kostet Zeit. Andernfalls könnten aber die mathematischen Ergebnisse auf unterschiedlichen Maschinen anders aussehen.

Galileo Computing

5.3.1 Strikt Fließkomma mit strictfp  downtop

Damit zum einen die Vorgaben der Norm erfüllt und zum anderen die Geschwindigkeit gewährleistet werden können, lässt sich vor Klassen- und Methoden der Modifizierer strictfp setzen, damit Operationen strikt nach der IEEE-Norm vorgehen. Ohne dieses Schlüsselwort (wie es also für unsere meisten Programme der Fall ist) wird eine interne Optimierung vorgenommen. Nach außen bleiben die Datentypen 32 Bit und 64 Bit lang, das heißt, bei den Konstanten in double und float ändert sich nichts. Zwischenergebnisse bei Fließkommaberechnungen werden aber eventuell mit höherer Genauigkeit berechnet.


Galileo Computing

5.3.2 Die Klassen Math und StrictMath  downtop

Die Umsetzung der Striktheit in der Math-Klasse wird durch zwei Klassen erreicht: Math und StrictMath. An der Klassendeklarationen für StrictMath lässt sich ablesen, dass alle Methoden sich an die IEEE-Norm halten.

public final strictfp 
class StrictMath {
// ...
}

Die Implementierung ist bisher für Math und StrictMath die gleiche. Alle Methoden mit Berechnungen werden an StrictMath weitergeleitet.

public final strictfp class Math
{
public static double
tan(double a) {
return
StrictMath.tan(a);
// default impl. delegates to StrictMath
}
// ...
}

Galileo Computing

5.4 Die Random-Klasse  downtop

Neben der Zufallsfunktion Math.random() in der Klasse Math, gibt es einen flexibleren Generator für Zufallszahlen im Util-Paket. Dies ist die Klasse Random, die aber im Gegensatz zu Math.random(), keine statischen Methoden besitzt. Die statische Funktion aus der Klasse Math nutzt intern jedoch auch ein Random-Objekt.

Startwert für jede Zufallszahl ist ein 48 Bit-Seed. Was Wort »Seed« stammt vom englischen Wort für Samen und deutet an, dass es bei der Generierung von Zufallszahlen wie bei Pflanzen einen Samen gibt, der zu Nachkommen führt. Aus diesem Startwert ermitteln sich anschließend die anderen Zahlen durch lineare Kongruenzen. (Dadurch sind die Zahlen nicht wirklich zufällig, sondern sie gehorchen einem mathematischen Verfahren.) Zunächst ist daher, bevor Zufallszahlen erzeugt werden, ein Exemplar der Klasse Random zu erstellen. Dieses Exemplar wird mit einem Zufallswert (Datentyp long) initialisiert, der dann für die weiteren Berechnungen verwendet wird. Dieser Startwert prägt die ganze Folge von erzeugten Zufallszahlen, obwohl nicht ersichtlich ist, wie die Folge sich verhält. Doch eines ist gewiss: Zwei mit gleichen Startwerten erzeugte Random-Objekte liefern auch dieselbe Folge von Zufallszahlen. Da einem meist nicht der passende Startwert für einen Zufallszahlen-Generator einfällt, ist der parameterlose Standard-Konstruktor wie folgt implementiert:

Random() {
this( System.currentTimeMillis() );
}

Der Konstruktor benutzt folglich die aktuelle Zeit als Startwert für die folgenden Zufallszahlen.

class java.util.Random
implements Serializable

gp  Random()
Erzeugt einen neuen Zufallszahlengenerator. Seed wird auf die aktuelle Zeit gesetzt.
gp  Random( long )
Erzeugt einen neuen Zufallszahlengenerator und benutzt den Parameter als Seed.
gp  setSeed( long )
Setzt den Seed neu. Der Generator verhält sich anschließend genau so, wie ein mit diesem Seed-Wert frisch erzeugter Generator.

Die Random-Klasse erzeugt Zufallszahlen für vier verschiedene Datentypen: int (32 Bit), long (64 Bit), double und float. Dafür stehen vier Funktionen zur Verfügung:

gp  int nextInt()
long nextLong()
Liefert die nächste Pseudo-Zufallszahl zwischen Integer.MIN_VALUE und Integer-MAX_VALUE bzw. Long.MIN_VALUE und Long.MAX_VALUE.
gp  float nextFloat()
double nextDouble()
Liefert die nächste Pseudo-Zufallszahl zwischen 0.0 und 1.0.
gp  int nextInt( int range )
Liefert eine int Pseudo-Zufallszahl im Bereich von 0 bis range.

Die Klasse Random verfügt über eine besondere Methode, mit der sich eine Reihe von Zufallszahlen erzeugen lassen. Dies ist die Funktion nextBytes(byte[]). Der Parameter ist ein Byte-Feld, und dieses wird komplett mit Zufallszahlen gefüllt:

gp  void nextBytes( byte[] )
Füllt das Feld mit Zufalls-Bytes auf. Zur Erzeugung wird die Funktion next() verwendet, die in Random implementiert ist, aber nicht sofort genutzt werden kann. Sie ist protected und kann somit nur von einer erbenden Klasse aufgerufen oder überschrieben werden.

Pseudozufallszahlen in der Normalverteilung

Über eine spezielle Funktion können wir Zufallszahlen erhalten, die einer Normalverteilung genügen: nextGaussian(). Diese Funktion arbeitet nach der Polar-Methode und erzeugt aus zwei unabhängigen Pseudo-Zufallszahlen zwei normalverteilte Zahlen. Der Mittelpunkt liegt bei 0 und die Standardabweichung ist 1. Die Zahlen, die von der Funktion nextGaussian() berechnet werden, sind double-Zahlen und häufig in der Nähe von 0. Größere Zahlen sind der Wahrscheinlichkeit nach seltener.

class java.util.Random
implements Serializable

gp  double nextGaussian()
Liefert die nächste Zufallszahl in einer Gaußschen Normalverteilung mit der Mitte 0.0 und der Standardabweichung 1.0.
Galileo Computing

5.5 Große Zahlen  downtop

Die feste Länge der primitiven Datentypen int, long für Ganzzahlwerte und float, double für Fließkommawerte reichen für diverse numerische Berechnungen nicht aus. Besonders wünschenswert sind größere Zahlen besonders in der Kryptografie. Für solche Anwendungen gibt es im math-Paket zwei Klassen: BigInteger für Ganzzahlen und BigDecimal für Gleitkommazahlen.


Galileo Computing

5.5.1 Die Klasse BigInteger  downtop

Mit der Klasse BigInteger ist es uns möglich, beliebig genaue Zahlen anzulegen, zu verwalten und damit zu rechnen. Die BigInteger-Objekte werden dabei immer so lang, wie die entsprechenden Ergebnisse Platz benötigen (engl. »infinite word size«). Die Berechnungsmöglichkeiten gehen dabei weit über die der primitven Typen hinaus und bieten des weiteren viele der statischen Methoden der Math-Klasse. Zu den Erweiterungen gehören modulare Arithmetik, Bestimmung des größten gemeinsamen Teilers (ggT), Pseudoprimzahl-Tests, Bitmanipulation und weiteres.

Ein BigInteger-Objekt wird dabei intern wie der primitive Datentyp im Zweierkomplement dargestellt. Auch die weiteren Operationen entsprechen den Ganzzahl-Operationen der primitiven Datentypen, wie etwa die Division durch Null. Sie löst eine ArithmeticException aus. Da ein Überlauf nicht möglich ist, da intern der Speicher angepasst wird, muss ein Anwender gegebenenfalls einen eigenen Überlauftest in sein Programm einbauen, wenn er den Wertebereich beschränken will. Da die Größe des Datentyps bei Bedarf immer ausgedehnt wird, sind einige Operationen ebenfalls nicht übertragbar. So kann der Verschiebe-Operator >>> nicht übernommen werden, denn bei einer Rechtsverschiebung haben wir kein Vorzeichen-Bit im BigInteger. Auch bei logischen Operatoren muss eine Interpretation der Werte vorgenommen werden. Bei Operationen auf zwei BigInteger-Objekten mit unterschiedlicher Bit-Länge wird der kleinere dem größeren durch Replikation (Wiederholung) des Vorzeichen-Bits angepasst. Über spezielle Bit-Operatoren können einzelne Bits gesetzt werden. Wie bei der Klasse BitSet lassen sich durch die »unendliche« Größe Bits setzen, auch wenn die Zahl nicht so viele Bits benötigt. Durch die Bit-Operationen lässt sich das Vorzeichen einer Zahl nicht verändern; gegebenenfalls wird vor der Zahl ein neues Vorzeichen-Bit mit dem ursprünglichen Wert ergänzt.

BigInteger-Objekte erzeugen

Zur Erzeugung stehen uns verschiedene Konstruktoren zur Verfügung. Einen Standard-Konstruktor gibt es nicht. Neben Konstruktoren, die das Objekt mit Werten aus einem Byte-Feld oder String initialisieren, lässt sich auch ein Objekt mit einer zufälligen Belegung erzeugen. Die Klasse BigInteger bedient sich dabei der Klasse java.util.Random. Ebenso lassen sich BigInteger-Objekte erzeugen, die Pseudoprimzahlen sind. Bei den Konstruktoren mit String-Parametern wird im Fehlerfall eine NumberFormatException ausgeworfen.

class java.math.BigInteger
extends Number

gp  BigInteger( byte[] )
Ein Bytefeld mit einer Zweierkomplement-Repräsentation einer BigInteger-Zahl im Big-Endian-(Array-Element mit Index 0, enthält die niederwertigsten Bits) Format initialisiert das neue BigInteger-Objekt.
gp  BigInteger( int signum, byte magnitude[] )
Erzeugt aus einer Big-Endian Betrag- bzw. Vorzeichen-Repräsentation ein BigInteger-Objekt. signum gibt das Vorzeichen an und kann mit -1 (neg. Zahlen), 0 (Null) und 1 (pos. Zahlen) belegt werden.
gp  BigInteger( int bitLength, int certainty, Random rnd )
Erzeugt eine BigInteger-Zahl mit der Bitlänge bitLength (>1), bei der es sich mit gewisser Wahrscheinlichkeit um eine Primzahl handelt. Der Wert certainty bestimmt, wie wahrscheinlich ein Fehlurteil ist. Mit der Wahrscheinlichkeit 1/(2^certainty) handelt es sich bei der erzeugten Zahl fälschlicherweise doch nicht um eine Primzahl. Intern wird die private Funktion isProbablePrime()benutzt, um festzustellen, ob es sich um eine Primzahl handelt. Je größer certainty ist (je unwahrscheinlicher ein Fehlurteil ist), desto länger braucht die Funktion.
gp  BigInteger( int numbits, Random )
Liefert eine Zufallszahl aus dem Wertebereich 0 bis 2^numBits – 1. Alle Werte sind gleichwahrscheinlich.
gp  BigInteger( String )
Erzeugt ein BigInteger aus einem Ziffern-String mit einem optionalen Vorzeichen.
gp  BigInteger( String, int radix )
Ein String mit einem optionalen Vorzeichen wir zu einem BigInteger-Objekt übersetzt. Dabei wird die angegebene Basis radix verwendet, um die Zeichen des Strings als Ziffern zu interpretieren. Für radix > 10 werden die Buchstaben A-Z bzw. a-z als zusätzliche »Ziffern« verwendet.

Leider gibt es immer noch keinen Konstruktor, der auch long-Datentypen annimmt. Das ist seltsam, denn es gibt die statische Methode valueOf(), die BigInteger-Objekte erzeugt. Dies ist sehr verwirrend, denn viele Programmierer übersehen diese Funktion und gehen über ein String-Objekt. Besonders ärgerlich ist es dann, zu sehen, dass es einen privaten Konstruktor gibt, der mit einem long arbeitet. Genau diesen Konstruktor nutzt dann auch valueOf().

Im Endeffekt sind dann die folgenden Zeilen gleichwertig:

BigInteger bi = BigInteger.valueOf( 
123456789 );  // (1)
BigInteger bi = new BigInteger( ""+123456789 ); // (2)

Neben den Konstruktoren und dem valueOf() gibt es zwei Konstanten für die Werte 0 und 1.

gp  static final BigInteger ZERO
Der Wert berechnet sich aus der Anweisung new BigInteger(new byte[0], 0).
gp  static final BigInteger ONE
Der Wert wird mit valueOf(1) berechnet.

Obwohl es intern noch eine Konstante TWO gibt, ist diese privat und von außen nicht zugreifbar.


Galileo Computing

5.5.2 Ganz lange Fakultäten  downtop

Unser Beispielprogramm soll nun die Fakultät einer natürlichen Zahl berechnen. Die Zahl muss positiv sein.

Listing 5.4   Fakultaet.java
import java.math.*;

class Fakultaet
{
static BigInteger fakultät( int n )
{
BigInteger big = BigInteger.ONE;

if ( n == 0 || n == 1 )
return big;

if ( n > 1 )
for ( int i = 1; i <= n; i++ )
big = big.multiply( BigInteger.valueOf(i) );

return big;
}

static public void main( String args[] )
{
System.out.println( fakultät(100) );
}
}

Neben dieser iterativen Variante ist auch noch eine rekursive denkbar. Sie ist allerdings aus zwei Gründen nicht wirklich gut. Zuerst auf Grund des hohen Speicherplatzbedarfs. Für die Berechnung von n! müssen n Objekte erzeugt werden. Im Gegensatz zur iterativen Funktion müssen diese jedoch alle im Speicher gehalten werden, bis die Rekursion aufgelöst wird. Dadurch ergibt sich die zweite Schwäche, die längere Laufzeit. Aus akademischen Gründen soll die Methode hier allerdings aufgeführt werden. Es wäre interessant, einmal zu beobachten, wie der Speicher bei dieser Implementierung aufgezehrt wird.

public static BigInteger fakultät_rek( 
int i )
{
if ( i <= 1 )
return BigInteger.ONE;
else
{
BigInteger bi = BigInteger.valueOf(i);
return bi.multiply(
fakultät_rek( i-1 ) );
}
}

Galileo Computing

5.6 Probleme mit Java und der Mathematik  downtop

Die mathematische Grundausstattung der mitgelieferten Java Standard-Bibliothek ist sehr mager und wird von Mathematikern häufig als Negativpunkt aufgeführt. Für Sprachen wie FORTRAN ist Numerik eine der wichtigsten Anwendungen, und sie wird heute noch bei der Lösung numerischer Probleme auf parallelen Maschinen angewendet. Da in FORTRAN viele Bibliotheken existieren, wäre der Kostenaufwand sehr hoch, diese unter einer anderen Programmiersprache neu zu entwickeln, sodass es kostengünstiger ist, einen FORTRAN-Experten einzustellen, als das Paket neu entwickeln zu lassen. Zudem ist FORTRAN zwar durch die Regeln sehr komplex geworden (fast 1000 Regeln, für Compilerbauer eine Qual), doch die Anweisungen sind sehr einfach. Daher lassen sich FORTRAN-Programme sehr einfach parallelisieren, was bei Programmiersprachen mit reicherer Ausdrucksfähigkeit nicht so einfach ist. Daher wird auch Java FORTRAN nicht die Show stehlen können. Dennoch bleibt der Wunsch der Anwendungsentwickler, auch Javas Fähigkeiten für Berechnungen nutzen zu können. Hier stellen sich zwei Probleme: einmal beim Design der Sprache und einmal aufgrund fehlender Bibliotheken. Während sich das zweite Problem mit der Zeit aus dem Weg räumen ließe, ist eine Änderung der Sprachdefinition deutlich schwieriger. Dies ist nicht technisch gemeint. Auf kurz oder lang wird hier vermutlich etwas geschehen und einige Vorschläge für Sprachveränderungen liegen bereits vor. Auf der Web-Seite von James Gosling (http://java.sun.com/people/jag/FP.html) findet der interessierte Leser mehr. Eines der Probleme dreht sich um NaN. Ein durchschnittlicher Prozessor besitzt eine Vielzahl verschiedener NaN-Darstellungen, die in Java einfach auf einen einzigen NaN-Wert abgebildet werden. Das hilft natürlich nicht weiter, wenn sich am Ende einer Berechnung herausstellt, dass irgendwo ein NaN-Wert aufgetreten ist, der keine Rückschlüsse auf den ursprünglichen Berechnungsfehler erlaubt. Abhilfe dafür ist in Arbeit.


Galileo Computing

5.7 Das Java-Matrix-Paket Jama  toptop

Als zweiten Schwachpunkt haben wir ausgemacht, dass leistungsstarke Bibliotheken für Java fehlen. Inwieweit diese in die Standard-Bibliothek integriert sein müssen, bliebe dabei noch zu diskutieren, jedenfalls sind die Klassen BigInteger und BigDecimal nicht besonders viel. (Obwohl zur Ehrenrettung gesagt werden muss, dass bei FORTRAN auch fast alles in externen, zum Teil recht teuren, kommerziellen Bibliotheken steht.) Über Universitäten und Firmen sind allerdings eine Vielzahl von Speziallösungen verfügbar, die dieses Loch stopfen. Auch bei der 3D-API von Sun ist ein Matrix-Paket dabei, welches aber nur die einfachsten Matrixoperationen berechnet, darunter etwa die Grundoperationen mit Matrizen. Da aber Matrixoperationen auch für viele Wirtschafts- und Wissenschaftsbereiche wichtig sind, soll an dieser Stelle das Paket Jama vorgestellt werden, das es mit Matrizen aufnimmt. Das Paket ist eine Entwicklung von MathWorks und dem National Institute of Standards and Technology (NIST) und liegt als freie Referenzimplementierung vor, die Sun später als Standard-Bibliothek anbieten soll. Zusätzlich zu der Matrix-Klasse als Teil von Jama haben das NIST und die Universität von Maryland das Paket Jampack als alternativen Ansatz für Matrixberechnung entwickelt, um das es hier aber nicht gehen soll.

Die Jama-Bibliothek (http://math.nist.gov/javanumerics/jama) besteht im Wesentlichen aus sechs Klassen: Matrix, CholeskyDecomposition, LUDecomposition, QRDecomposition, SingularValueDecomposition und EigenvalueDecomposition. Es ist schön zu sehen, dass auch deutsche Wörter hin und wieder Eingang in wissenschaftliche englische Begriffe finden. Die Matrix-Klasse bietet neben grundlegenden Matrixoperationen, die sich auch in der 3D-API befinden, zusätzliche Methoden zur Lösung linearer Gleichungssysteme, zur Determinantenberechnung und zur Berechnung der Inversen einer Matrix an. Die übrigen Klassen erlauben eine Cholesky-Zerlegung, eine LU- und QR-Zerlegung und die Berechnung der Eigenwerte. Als Einschränkung rechnet Jama bisher nur mit reellen Zahlen, es ist jedoch eine Erweiterung auf komplexe Matrix-Elemente geplant. Hier sind sich die Entwickler jedoch bei der Realisierung noch nicht sicher, da saubere Objektorientierung und Effizienz Hand in Hand gehen sollen. Intern ist die Implementierung mit zweidimensionalen Feldern gelöst. Diese Form führt jedoch zu einem großen Speicherproblem bei dünn besiedelten Matrizen. Ebenso wird auch bei Dreiecksmatrizen keine besondere Implementierung verwendet. All dieses bedenken aber die Entwickler und wollen es in späteren Versionen nachliefern. Nun ja, die letzte Änderung der Webseite war der 23. Juni 1999 (Stand Ende 2001) ...

Um die Leistungen von Jama noch einmal zusammenzufassen, hier eine Liste der Funktionen:

gp  Objektmanipulation
Elemente der Matrix setzen und auslesen, Matrizen kopieren
gp  Elementare Operationen
Addition, Subtraktion, Multiplikation, Multiplikation mit einem Skalar, elementweise Multiplikation, elementweise Division, unäres Minus, Transponierung, Norm
gp  Zerlegungen
Cholesky, LU, QR, SVD, symmetrischer und nichtsymmetrischer Eigenwert
gp  Lösen von Gleichungssystemen
Lösung nichtsingulärer Gleichungen, kleinste Quadrate
gp  Sonstiges
Determinante, Rang, Inverses, Pseudoinverses
Beispiel Lösen eines einfachen linearen Gleichungssystems

Die folgenden Zeilen berechnen die Lösung der Gleichung Ax = b bei einem zufällig erzeugten b.

double m[][] = {
{ 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 }
};

Matrix A, b, x ;

A = new Matrix( m );
b = Matrix.random( 3,1 );
x = A.solve( b );

Matrix residual = A.times(x).minus(b);
double rnorm = residual.normInf();

Das Ergebnis lässt sich mit toString() ermitteln. normInf() berechnet die Unendlich-Norm, die das größte Element der Matrix bezeichnet.


 






1    Dass diese Frage besonders in den siebziger Jahren interessant war, zeigen schon die Aufsätze von H. E. Vaughan, The expression ’0^0’, Mathematics Teacher 63 (1970), und von Louis M. Rotando & Henry Korn, The Indeterminate Form 0^0, Mathematics Magazine, Vol. 50, No. 1 (January 1977). Auch L. J. Paige, A note on indeterminate forms, American Mathematical Monthly, 61 (1954), 189-190, scheint hier interessante Einblicke zu geben.

2    Donald E. Knuth (DEK), The Art of Computer Programming (ACP), 2 Buch, Kapitel 3.2.1.

3    G. E. P. Muller, M. E. Muller und G. Marsaglia beschreiben sie in ACP, Kapitel 3.4.1.

4    Einige Systeme produzieren ab fakultaet_rek (7750) einen java.lang.StackOverflowError, andere erst ab 43200.

  

Java 2




Copyright © Galileo Press GmbH 2002
Für Ihren privaten Gebrauch dürfen Sie die Online-Version natürlich ausdrucken. Ansonsten unterliegt das <openbook> denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.


[Galileo Computing]

Galileo Press GmbH, Gartenstraße 24, 53229 Bonn, fon: 0228.42150.0, fax 0228.42150.77, info@galileo-press.de