5.5 Große Zahlen 

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 in der Kryptographie. 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 BigInteger-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

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 (neg. Zahlen), 0 (Null) und 1 (pos. 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 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 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 ) );
  }
}

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