5.5 Große Zahlen
 
Die feste Länge der primitiven Datentypen int, long für Ganzzahlwerte und float, double für Fließkommawerte reicht für diverse numerische Berechnungen nicht aus. Besonders wünschenswert sind beliebig große Zahlen in der Kryptographie und präzise Auflösungen in der Finanzmathematik. Für solche Anwendungen gibt es im math-Paket zwei Klassen: BigInteger für Ganzzahlen und BigDecimal für Gleitkommazahlen.
5.5.1 Die Klasse BigInteger
 
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 primitiven Typen hinaus und bieten des Weiteren viele der statischen Funktionen der Math-Klasse. Zu den Erweiterungen gehören modulare Arithmetik, Bestimmung des größten gemeinsamen Teilers (ggT), Pseudo-Primzahltests, 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, weil 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 Big–Integer-Objekten mit unterschiedlicher Bitlänge wird der kleinere dem größeren durch Replikation (Wiederholung) des Vorzeichen-Bit angepasst. Über spezielle Bitoperatoren können einzelne Bit gesetzt werden. Wie bei der Klasse BitSet lassen sich durch die »unendliche« Größe Bit setzen, auch wenn die Zahl nicht so viele Bit benötigt. Durch die Bitoperationen 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 Bytefeld 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 Pseudo-Primzahlen sind. Bei den Konstruktoren mit String-Parametern wird im Fehlerfall eine NumberFormatException ausgeworfen.
class java.math. BigInteger
extends Number
implements Comparable<BigInteger>
|
|
BigInteger( String val )
Erzeugt ein BigInteger aus einem Ziffern-String mit einem optionalen Vorzeichen. |
|
BigInteger( String val, int radix )
Ein String mit einem optionalen Vorzeichen wird 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 beziehungsweise a–z als zusätzliche »Ziffern« verwendet. |
|
BigInteger( byte[] val )
Ein Bytefeld mit einer Zweierkomplement-Repräsentation einer BigInteger-Zahl im Big-Endian(Array-Element mit Index 0, enthält die niederwertigsten Bit)-Format initialisiert das neue BigInteger-Objekt. |
|
BigInteger( int signum, byte[] magnitude )
Erzeugt aus einem Big-Endian-Betrag- beziehungsweise einer Vorzeichen-Repräsentation ein BigInteger-Objekt. signum gibt das Vorzeichen an und kann mit –1 (negative Zahlen), 0 (Null) und 1 (positive Zahlen) belegt werden. |
|
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 um keine Primzahl. Intern wird die private Funktion isProbablePrime() benutzt, um festzustellen, ob es sich um eine Primzahl handelt. Je größer certainty (und je unwahrscheinlicher ein Fehlurteil) ist, desto länger braucht die Funktion. |
|
BigInteger( int numbits, Random rnd )
Liefert eine Zufallszahl aus dem Wertebereich 0 bis 2^numBits – 1. Alle Werte sind gleich wahrscheinlich. |
|
static BigInteger valueOf( long val )
Fabrikfunktion, die aus einem long ein BigInteger konstruiert. |
Beispiel Gegeben sei eine Zeichenkette, die eine Binärfolge aus Nullen und Einsen kodiert. Dann lässt sich ein Objekt der Klasse BigInteger nutzen, um diese Zeichenkette in ein Byte-Array zu konvertieren:
String s = "11011101 10101010 0010101 00010101".replace( " ", "" );
byte[] bs = new BigInteger( s, 2 ).toByteArray(); // [158,261,69,69]
for ( byte b : bs )
System.out.println( Integer.toBinaryString(b & 0xff) );
Die Schleife erzeugt die vier Ausgaben 1101110, 11010101, 10101 und 10101.
|
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 also die folgenden Zeilen gleichwertig:
BigInteger bi = BigInteger.valueOf( 123456789 );
BigInteger bi = new BigInteger( "" + 123456789 );
Neben den Konstruktoren und dem valueOf() gibt es drei Konstanten für die Werte 0, 1 und 10.
class java.math. BigInteger
extends Number
implements Comparable<BigInteger>
|
|
static final BigInteger ZERO |
|
static final BigInteger ONE |
|
static final BigInteger TEN |
5.5.2 Funktionen von BigInteger
 
Die erste Kategorie von Funktionen bilden arithmetische Operationen nach, für die es sonst ein Operatorzeichen oder eine Funktion aus Math geben würde.
class java.math. BigInteger
extends Number
implements Comparable<BigInteger>
|
|
BigInteger abs()
Liefert den Absolutwert, ähnlich wie Math.abs() für primitive Datentypen. |
BigInteger add(BigInteger val), BigInteger and(BigInteger val),
BigInteger andNot( BigInteger val ),
BigInteger divide( BigInteger val ), BigInteger mod( BigInteger m ),
BigInteger multiply( BigInteger val ), BigInteger or( BigInteger val ),
BigInteger remainder( BigInteger val ),
BigInteger subtract( BigInteger val ), BigInteger xor( BigInteger val )
Bildet ein neues BigInteger-Objekt mit der Summe/Und-Verknüpfung/Und-Nicht-Verknüpfung/Division/Modulo/Produkt/Oder/Restwert/Differenz/Xor dieses Objekts und des anderen.
|
BigInteger[] divideAndRemainder( BigInteger val )
Liefert ein Feld mit zwei BigInteger-Objekten. Im Feld, dem Rückgabeobjekt, steht an der Stelle 0 (this / val) und an der Stelle 1 folgt (this % val). |
|
BigInteger modInverse( BigInteger m )
Bildet ein neues BigInteger, indem es vom aktuellen BigInteger 1 subtrahiert und es dann Modulo m nimmt. |
|
BigInteger modPow( BigInteger exponent, BigInteger m )
Nimmt den aktuellen BigInteger hoch exponent Modulo m. |
|
BigInteger negate()
Negiert das Objekt, liefert also ein neues BigInteger mit umgekehrtem Vorzeichen. |
|
BigInteger not()
Liefert ein neues BigInteger, das die Bit negiert hat. |
|
BigInteger pow( int exponent )
Bildet this^exponent. |
|
int signum()
Liefert das Vorzeichen des BigInteger-Objekts. |
Die nächste Kategorie von Methoden ist eng mit den Bit der Zahl verbunden.
|
int bitCount()
Zählt die Anzahl gesetzter Bit der Zahl, die im Zweier-Komplement vorliegt. |
|
int bitLength() |
|
Liefert die Anzahl der Bit, die nötig sind, um die Zahl im Zweier-Komplement ohne Vorzeichen-Bit darzustellen. |
|
|
BigInteger clearBit( int n ), BigInteger flipBit( int n ),
BigInteger setBit( int n )
Liefert ein neues BigInteger-Objekt mit gelöschtem/gekipptem/gesetztem n-ten Bit.
|
BigInteger shiftLeft( int n ), BigInteger shiftRight( int n )
Schiebt die Bit um n Stellen nach links/rechts. |
|
int getLowestSetBit()
Liefert die Position eines Bit, welches in der Repräsentation der Zahl am weitesten rechts gesetzt ist. |
|
boolean testBit( int n )
true, wenn das Bit n gesetzt ist. |
Folgende Funktionen sind besonders für kryptografische Verfahren interessant:
|
BigInteger gcd( BigInteger val )
Liefert den größten gemeinsamen Teiler vom aktuellen Objekt und val. |
|
boolean isProbablePrime( int certainty )
Ist das BigInteger-Objekt mit der Wahrscheinlichkeit certainty eine Primzahl? |
|
BigInteger nextProbablePrime()
Liefert die nächste Ganzzahl hinter dem aktuellen BigInteger, die wahrscheinlich eine Primzahl ist. |
|
static BigInteger probablePrime( int bitLength, Random rnd )
Liefert mit einer bestimmten Wahrscheinlichkeit eine Primzahl der Länge bitLength. |
Die letzte Gruppe bildet Vergleichs- und Konvertierungsfunktionen.
|
int compareTo( Object o ), int compareTo( BigInteger o )
Da die Klasse BigInteger die Schnittstelle java.lang.Comparable implementiert, lässt sich jedes BigInteger-Objekt mit einem anderen vergleichen. Die Methode mit dem Datentyp BigInteger ist natürlich nicht von Comparable vorgeschrieben, aber beide Funktionen sind identisch. |
|
double doubleValue(), float floatValue(), int intValue(), long longValue()
Konvertiert den BigInteger in ein double/float/int/long. Es handelt sich um implementierte Funktionen der abstrakten Oberklasse Number. |
|
boolean equals( Object x )
Vergleicht, ob x und das BigInteger-Objekt den gleichen Wert annehmen. |
|
BigInteger max( BigInteger val ), BigInteger min( BigInteger val )
Liefert das größere/kleinere der BigInteger-Objekte als Rückgabe. |
|
byte[] toByteArray()
Liefert ein Bytefeld mit dem BigInteger als Zweier-Komplement. |
|
String toString(), String toString( int radix )
Liefert die String-Repräsentation von diesem BigInteger zur Basis 10 und einer beliebigen Basis. |
|
static BigInteger valueOf( long val )
Erzeugt ein BigInteger, welches den Wert val annimmt. |
5.5.3 Ganz lange Fakultäten
 
Unser Beispielprogramm soll nun die Fakultät einer natürlichen Zahl berechnen. Die Zahl muss positiv sein.
Listing 5.3
Fakultaet.java
import java.math.*;
class Fakultaet
{
static BigInteger fak( 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( fak(100) );
}
}
Neben dieser iterativen Variante ist auch noch eine rekursive denkbar. Sie ist allerdings aus zwei Gründen nicht wirklich gut. Zuerst aufgrund 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 ist interessant zu beobachten, wie der Speicher bei dieser Implementierung aufgezehrt wird. Dabei ist es noch nicht einmal der Heap, der keine neuen Objekte mehr aufnehmen kann, sondern vielmehr der Stack.
public static BigInteger fak2 ( int i )
{
if ( i <= 1 )
return BigInteger.ONE;
BigInteger bi = BigInteger.valueOf( i );
return bi.multiply( fak2( i-1 ) );
}
5.5.4 Große Fließkommazahlen mit BigDecimal
 
Während sich BigInteger um die beliebig genauen Ganzzahlen kümmert, übernimmt BigDecimal die Fließkommazahlen. Der Konstruktor nimmt unterschiedliche Typen an, unter anderem double und String. Bei double muss aufgepasst werden, denn während bei
new BigDecimal( 1.00000000000000000000000000000000000000000000000000000001 )
das Literal auf den für double gültigen Bereich gebracht wird (1), ist präzise
new BigDecimal( "1.00000000000000000000000000000000000000000000000000000001" )
Mit den BigDecimal-Objekten lässt sich nun rechnen, wie von BigInteger bekannt. Einen Unterschied stellt jedoch die Methode divide() dar, die zusätzlich einen Rundungsmodus und optional auch eine Anzahl gültiger Nachkommastellen bekommen kann.
BigDecimal a = new BigDecimal( "10" );
BigDecimal b = new BigDecimal( "2" );
System.out.println( a.divide(b) ); // 5
Es ist kein Problem, wenn das Ergebnis eine Ganzzahl ist, oder das Ergebnis exakt ist.
System.out.println( new BigDecimal(1).divide(b) ); // 0.5
Wenn das Ergebnis aber nicht exakt ist, lässt sich divide() nicht einsetzen. Die Anweisung
new BigDecimal(1).divide( new BigDecimal(3) )
gibt den Fehler:
java.lang.ArithmeticException: Non-terminating decimal expansion; no exact representable decimal result.
An dieser Stelle kommen die Rundungs-Modi ROUND_UP, ROUND_DOWN, ROUND_CEILING, ROUND_FLOOR, ROUND_HALF_UP, ROUND_HALF_DOWN, ROUND_HALF_EVEN ins Spiel. ROUND_UNNECESSARY ist auch einer davon, darf aber nur dann verwendet werden, wenn die Division exakt ist.
System.out.println( c.divide(d, BigDecimal.ROUND_UP) ); // 1
System.out.println( c.divide(d, BigDecimal.ROUND_DOWN) ); // 0
Jetzt kann noch die Anzahl der Nachkommastellen bestimmt werden:
System.out.println( c.divide(d, 6, BigDecimal.ROUND_UP) ); // 0.333334
System.out.println( c.divide(d, 6, BigDecimal.ROUND_DOWN) ); // 0.333333
5.5.5 Komfortabel die Rechengenauigkeit setzen mit MathContext
 
Die Klasse java.math.MathContext wurde in Java 5 eingeführt, um für BigDecimal komfortabel die Rechengenauigkeit (nicht Nachkommastellen) und den Rundungsmodus setzen zu können. Vorher wurde diese Information, wie es das vorangehende Beispiel zeigte, den einzelnen Berechungsfunktionen mitgegeben. Jetzt kann dieses eine Objekt einfach an alle berechnenden Funktionen weitergegeben werden.
Die Eigenschaften werden mit den Konstruktoren gesetzt, denn MathContext-Objekte sind anschließend immutable.
class java.math. MathContext
implements Serializable
|
|
MathContext( int setPrecision )
Baut ein neues MathContext mit angegebener Präzision und dem Rundungsmodus HALF_UP. |
|
MathContext( int setPrecision, RoundingMode setRoundingMode )
Baut ein neues MathContext mit angegebener Präzision und einem vorgegebenen Rundungsmodus. |
|
MathContext( String val )
Baut ein neues MathContext aus einem String. Der Aufbau des String ist wie von toString() der Klasse, etwa »precision=34 roundingMode=HALF_EVEN«. |
Ein Konstruktor erlaubt den Rundungsmodus genau anzugeben, der als Aufzählung vom Typ RoundingMode definiert ist. Definierte Konstanten sind: CEILING, DOWN, FLOOR, HALF_DOWN, HALF_EVEN, HALF_UP, UNNECESSARY, UP.
Für die üblichen Fälle stehen vier vorgefertigte MathContex-Objekte als Konstanten der Klasse zur Verfügung: DECIMAL128, DECIMAL32, DECIMAL64 und UNLIMITED.
Nach dem Aufbau des MathContex-Objekts wird es im Konstruktor von BigDecimal übergeben.
class java.math. BigDecimal
extends Number
implements Comparable<BigInteger>
|
|
BigDecimal( BigInteger unscaledVal, int scale, MathContext mc ) |
|
BigDecimal( BigInteger val, MathContext mc ) |
|
BigDecimal( char[] in, int offset, int len, MathContext mc ) |
|
BigDecimal( char[] in, MathContext mc ) |
|
BigDecimal( double val, MathContext mc ) |
|
BigDecimal( int val, MathContext mc ) |
|
BigDecimal( long val, MathContext mc ) |
|
BigDecimal( String val, MathContext mc ) |
Auch bei jeder Berechungsfunktion lässt sich nun das MathContext-Objekt übergeben:
|
BigDecimal abs( MathContext mc) |
|
BigDecimal add( BigDecimal augend, MathContext mc ) |
|
BigDecimal divide( BigDecimal divisor, MathContext mc ) |
|
BigDecimal divideToIntegralValue( BigDecimal divisor, MathContext mc ) |
|
BigDecimal plus( MathContext mc ) |
|
BigDecimal pow( int n, MathContext mc ) |
|
BigDecimal remainder( BigDecimal divisor, MathContext mc ) |
|
BigDecimal round( MathContext mc ) |
|
BigDecimal subtract( BigDecimal subtrahend, MathContext mc ) |
|