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 Methoden 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-Bits angepasst. Über spezielle Bitoperatoren 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 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( byte val[] ) 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.

BigInteger( int signum, byte magnitude[] ) Erzeugt aus einer Big-Endian-Betrag- beziehungsweise 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 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.

BigInteger( int numbits, Random rnd ) Liefert eine Zufallszahl aus dem Wertebereich 0 bis 2^numBits - 1. Alle Werte sind gleich wahrscheinlich.

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.

String s = "1101110110101010001010100010101";
byte b[] = new BigInteger(s, 2).toByteArray();
for ( int i = 0; i < b.length; i++ )
  System.out.println( Integer.toBinaryString(b[i]&0xff) );

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 );       // (1)
BigInteger bi = new BigInteger( ""+123456789 );        // (2)

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

static final BigInteger ZERO Der Wert berechnet sich aus der Anweisung new BigInteger(new byte[0], 0).

static final BigInteger ONE Der Wert wird mit valueOf(1) berechnet.

Obwohl es intern noch eine Konstante TWO gibt, ist diese privat, von außen besteht also keine Möglichkeit, auf sie zuzugreifen.

5.5.2 Funktionen von BigInteger

Die Klasse bietet Funktionen, für die es sonst ein Operatorzeichen geben würde, und gleichzeitig auch Methoden zur Manipulation einzelner Bits.

class java.math.BigInteger
extends Number
implements Comparable

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.

int bitCount() Zählt die Anzahl gesetzter Bits der Zahl, die im Zweier-Komplement vorliegt.

int bitLength() Liefert die Anzahl der Bits, die nötig sind, 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/gekippten/gesetztem n-ten Bit.

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.

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).

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 gcd( BigInteger val ) Liefert den größten gemeinsamen Teiler vom aktuellen Objekt und val.

int getLowestSetBit() Liefert die Position eines Bits, welches in der Repräsentation der Zahl am weitesten rechts gesetzt ist.

boolean isProbablePrime( int certainty ) Ist das BigInteger-Objekt mit der Wahrscheinlichkeit certainty eine Primzahl?

BigInteger max( BigInteger val )

BigInteger min( BigInteger val ) Liefert das größere/kleinere der BigInteger-Objekte als Rückgabe.

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 Bits negiert hat.

BigInteger pow( int exponent ) Bildet this^exponent.

static BigInteger probablePrime( int bitLength, Random rnd ) Liefert eine Zufallszahl.

BigInteger shiftLeft( int n ) BigInteger shiftRight( int n ) Schiebt die Bits um n Stellen nach links/rechts.

int signum() Liefert das Vorzeichen des BigInteger-Objekts.

boolean testBit( int n ) true, wenn das Bit n gesetzt ist.

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.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 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.¹

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 ) );
  }
}

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