JavaのBigIntegerを知る1

twitterを眺めていると、Javaの標準ライブラリぐらい読んだことあるんだろう？と言われている気がしたので、前から理解したいと思っていたBigIntegerのソースを見てみることにしました。

本来はデータ構造と四則演算までおさえて理解したというべきなのでしょうが、想像以上に時間がかかってしまったのでここではBigIntegerの多倍長整数としてのデータ構造のみに注目しました。 BigIntegerを使った四則演算に関しては次の記事にしたいと思います。

BigIntegerのデータ構造
文字列からのBigInteger生成
補足

環境

OS: Arch Linux (linux kernel: 4.8.13)
Java: openjdk version “1.8.0_121”

1. BigIntegerのデータ構造

BigIntegerとは…

Javaの標準ライブラリに存在する多倍長整数を扱うクラス
- 多倍長整数: 32bitや64bitでは表せられない巨大な整数を扱うための仕組み
Immutable
- ただしBigIntegerがそうというだけで、多倍長整数だからimmutableというわけではない
- 例えばCのライブラリGMPが提供する多倍長整数はmutableらしい
BigIntegerの持つfieldはmagとsignumのみ (ただしstatic finalのような数値としての表現上本質的ではないものを除けば)
- magはint配列型で、整数の絶対値を表現
  - \( 2^{32} \) を基数とし、big-endianで値を格納する
    - Javaのint型は仕様で32bitとされており、それに合わせているということのはず
    - mag = [3, 2, 1]であれば、それは \( 3 \times 2^{64} + 2 \times 2^{32} + 1 = 55340232229718589441 \) となる
- signumはint型で、正負を表現
  - 表現したい整数が正なら1, 負なら2, ゼロの場合0とする

上で書いたように、BigIntegerのデータ構造は実質的に

public class BigInteger extends Number implements Comparable<BigInteger> {
    // The signum of this BigInteger
    final int signum;
    //The magnitude of this BigInteger
    final int[] mag;
}

というようにとてもシンプルです。

big-endianはUTF-16とかネットワークとかでよく聞きますね。意味は同じで、この場合数値として上位のものが配列の先頭側(indexの小さい側)にくるということになります。

またぼーっとしていると例えば

BigInteger b3 = new BigInteger(Long.toString(0xffffffffL));

を生成してデバッガ等で確認したときにmag=[-1]という表記が見えてあれっと思うかもしれませんが、これはmagがint配列型で、Javaがプリミティブな整数型に2の補数表現を使用するためです。実際は(多倍長整数としては) \( 2^{32} - 1 \) を表す数になっています。

もう一つ細かいところですが、データ上BigIntegerと整数は一対一に対応付けられるように考えられています。例えば0を表現したい場合、mag=[0]は当然なのですが、このときsignum=0にします。signumが0になるのはこのときだけです。

同様の理由により、magの上位側の要素に0を許すといくらでも0の要素を加えられて一意にできないので、それは除かれるようになっています。 (例えば計算の結果、mag=[0, 0, 2, 1]になった場合、最終的には[2, 1]にされる)

2. 文字列からのBigInteger生成

BigIntegerがどのようなデータ構造を持つのかを理解したところで、今度は文字列からの生成時に行われる処理を追ってみます。具体的には以下のBigInteger(String val, int radix)コンストラクタを見ていきます。

public class BigInteger extends Number implements Comparable<BigInteger> {
    ...
    public BigInteger(String val, int radix) {
        int cursor = 0, numDigits;
        final int len = val.length();

        if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
            throw new NumberFormatException("Radix out of range");
        if (len == 0)
            throw new NumberFormatException("Zero length BigInteger");

        // Check for at most one leading sign
        int sign = 1;
        int index1 = val.lastIndexOf('-');
        int index2 = val.lastIndexOf('+');
        if (index1 >= 0) {
            if (index1 != 0 || index2 >= 0) {
                throw new NumberFormatException("Illegal embedded sign character");
            }
            sign = -1;
            cursor = 1;
        } else if (index2 >= 0) {
            if (index2 != 0) {
                throw new NumberFormatException("Illegal embedded sign character");
            }
            cursor = 1;
        }
        if (cursor == len)
            throw new NumberFormatException("Zero length BigInteger");

        // Skip leading zeros and compute number of digits in magnitude
        while (cursor < len &&
               Character.digit(val.charAt(cursor), radix) == 0) {
            cursor++;
        }

        if (cursor == len) {
            signum = 0;
            mag = ZERO.mag;
            return;
        }

        numDigits = len - cursor;
        signum = sign;

        // Pre-allocate array of expected size. May be too large but can
        // never be too small. Typically exact.
        long numBits = ((numDigits * bitsPerDigit[radix]) >>> 10) + 1;
        if (numBits + 31 >= (1L << 32)) {
            reportOverflow();
        }
        int numWords = (int) (numBits + 31) >>> 5;
        int[] magnitude = new int[numWords];

        // Process first (potentially short) digit group
        int firstGroupLen = numDigits % digitsPerInt[radix];
        if (firstGroupLen == 0)
            firstGroupLen = digitsPerInt[radix];
        String group = val.substring(cursor, cursor += firstGroupLen);
        magnitude[numWords - 1] = Integer.parseInt(group, radix);
        if (magnitude[numWords - 1] < 0)
            throw new NumberFormatException("Illegal digit");

        // Process remaining digit groups
        int superRadix = intRadix[radix];
        int groupVal = 0;
        while (cursor < len) {
            group = val.substring(cursor, cursor += digitsPerInt[radix]);
            groupVal = Integer.parseInt(group, radix);
            if (groupVal < 0)
                throw new NumberFormatException("Illegal digit");
            destructiveMulAdd(magnitude, superRadix, groupVal);
        }
        // Required for cases where the array was overallocated.
        mag = trustedStripLeadingZeroInts(magnitude);
        if (mag.length >= MAX_MAG_LENGTH) {
            checkRange();
        }
    }
    ...
}

まずざっと流れの概要をまとめると以下のような処理になっています。

正負の判断 -> signumの決定
頭の0埋めの除去
与えられた数値の表現に必要なワード数の決定 -> mag配列の長さ決定
mag設定

1と2は大して難しいことはしていないと思いますので、3と4を詳細に見ていきます。

mag配列の長さ決定

処理の中でmag配列の長さを決定しているのは以下の部分です。

// Pre-allocate array of expected size. May be too large but can
// never be too small. Typically exact.
long numBits = ((numDigits * bitsPerDigit[radix]) >>> 10) + 1;
if (numBits + 31 >= (1L << 32)) {
    reportOverflow();
}
int numWords = (int) (numBits + 31) >>> 5;
int[] magnitude = new int[numWords];

ここではnumDigits, numBits, numWordsという変数が使用されています。これらはそれぞれ別の観点から与えられた数値を捉えたものだといえます。

numDigits
- 表現したい数値が指定の基数(radix引数)で何桁になるのか
- 0埋めとかがなければ単純にval.lengthでよい
numBits
- 表現したい数値がbit列として何桁になるのか
  - 基数とnumDigitsから求めることができる
- 実際のプログラムではbitsPerDigitという配列に \( \log{(radix)} / \log{2} \times 1024 \) の計算結果を事前に用意し、それを使用している
numWords
- 表現したい数値に必要なmagの大きさはいくつか
- numBitsをintデータ型bit数分の32で割って計算する

多倍長整数の話だけでなく基数変換に関する内容も入ってくるので慣れていないと混乱するかもしれません。その場合は基数が10固定になっているBigInteger(char[] val, int sign, int len)コンストラクタを見るほうがわかりやすいと思います。

ここで多倍長整数として考えたいことは表現したい数値をbit列として表すと何桁になり、mag配列で考えるとどのくらいの長さが必要になるのかということだけです。そして最終的にnumWordsがmag配列の長さになります。

numBitsの計算に関してですが、一般的にある自然数Nを表すのにm進数が必要な桁数は \( \log_m{(N+1}) = \log{(N+1)} / \log{m} \) です。例えば15を表すには2進数で4桁あればよく、16では4.087…, つまり5桁必要になります。これを応用して考えるとn進数1桁を表すのにm進数が必要とする桁数は \( \log_m{n} = \log{n} / \log{m} \) とできます。

またここではbitsPerDigitで予め1024をかけておき、numBitsの計算で右シフト10回を適用するという操作をしているのですが、これは恐らく整数値の計算を行い、かつなるべく最低限のbit数が求まるようにしているんじゃないかなと思います。

mag設定

magの設定ですが、流れとしては以下の感じです。

入力された文字列を先頭からk文字読む (kは基数によって決まる自然数)
標準ライブラリの関数で読んだ文字列をint型に変換する
magの各要素に桁上げ処理を行う
2で計算したintをmagの末尾に加える
入力文字列がまだ残っていればk+1を先頭にして1に戻る

// Process first (potentially short) digit group
int firstGroupLen = numDigits % digitsPerInt[radix];
if (firstGroupLen == 0)
    firstGroupLen = digitsPerInt[radix];
String group = val.substring(cursor, cursor += firstGroupLen);
magnitude[numWords - 1] = Integer.parseInt(group, radix);
if (magnitude[numWords - 1] < 0)
    throw new NumberFormatException("Illegal digit");

// Process remaining digit groups
int superRadix = intRadix[radix];
int groupVal = 0;
while (cursor < len) {
    group = val.substring(cursor, cursor += digitsPerInt[radix]);
    groupVal = Integer.parseInt(group, radix);
    if (groupVal < 0)
        throw new NumberFormatException("Illegal digit");
    destructiveMulAdd(magnitude, superRadix, groupVal);

1の処理ではk文字読めない場合(kで割り切れない長さを持つ入力文字列に対する話)を考慮する必要があり、それが上記プログラムの前半に含まれています。ただ本質的な部分の話ではないので、ここでは入力文字列の長さがkの倍数だと仮定して話を単純にします。

1の決められた文字数kを決定するために、プログラムではdigitsPerInt配列を使用しています。 digitsPerIntには、indexを基数nとみなし、n進数m桁が表せる整数全てがJavaのint型に格納できるというmのうち最大のものが入るようになっています。言い換えれば、Integer.MAX_VALUE以下、または符号表現に使用される最上位bitを外した31bitで表現できる最大の数以下です (恐らくJavaの整数型として計算しやすくするため？ 2の補数表現の関係で最上位bitを使用すると一手間加えないと正しい計算ができなくなる)。

例えば2進数であれば \( 2^{31} - 1 \) より小さい数なので \( 2^{30} - 1 \) まで表せる30桁となり、digitsPerInt[2] = 30となっています。10進数では \( 2^{31} - 1 = 1073741824 \) より小さい数なので、 \( {10}^9 - 1 \) まで表せる9桁となり、digitsPerInt[10] = 9 となります。

3と4の処理はdestructiveMulAddという関数で行われています。

private static void destructiveMulAdd(int[] mag, final int radix, final int val) {
    final long radixL = radix & LONG_MASK;
    final long valL = val & LONG_MASK;
    long product = 0;
    long carry = 0;

    for (int i = 0; i < mag.length; i++) {
        product = (mag[mag.length-i-1] & LONG_MASK) * radixL + carry;
        mag[mag.length-i-1] = (int) product;
        carry = product >>> 32;
    }

    long sum = (mag[mag.length-1] & LONG_MASK) + valL;
    mag[mag.length-1] = (int) sum;
    carry = sum >>> 32;
    for (int i = 1; i < mag.length; i++) {
        sum = (mag[mag.length-i-1] & LONG_MASK) + carry;
        mag[mag.length-i-1] = (int) sum;
        carry = sum >>> 32;
    }
}

3の桁上げ処理ではすでにmagに入れているデータに対し基数と一度に読んでいる文字数で決まるある整数(radixL)をかけます。

具体例を挙げると、入力文字列が10進数で111111111222222222の場合、はじめに111111111を読み、次に222222222を読むのですが、このとき111111111が上位の桁だということを表現するために、最初に読んだ数字に対し10進数9桁分の数、つまり \( {10}^9 \) をかける、という感じになります。 2進数の場合は30文字ずつ読むことにしているので、 \( 2^{30} \) をかけることになります。

この値は実際のプログラム中ではintRadix配列に格納されています。

なおこのとき、計算結果がmagが内部的に使用している基数、つまり \( 2^{32} \) を超えてしまうことがあります。その場合は下位32bitに収まる範囲に、つまり計算結果をintでキャストしてmagのもとの要素にセットし直します。そして上位32bit分、つまり計算結果を右シフト32回した値(carry)をmagの一つ前の要素に加えます。

4の処理ではmagの末尾に新規の整数を加え、3と同じようにcarryの対応を行います。

個人的にはこの3,4まわりが少し難しかったのですが、それは一度に読む数字列の長さと、magの桁上がりの大きさに直接的な関係がないことにいまいちピンと来なかったからでした。どちらも効率や型の大きさ等を除けば、こうでないといけないという値はなく、一度に読む長さを変えるならそれに応じて桁上げの数を変えればよく、magの一つの要素に入れる数の大きさを変えるなら、それに応じてcarryの条件を変えるだけということですね。

この処理を入力文字列が読み終わるまで繰り返せば(データ構造としての)BigIntegerは完成です。

3. 補足

LONG_MASK
- int型として扱っている32 bitをlong型64 bitに変換するときに使用
- 数値として処理するのではなく、単純にbit列を拡張したいという場合に、(1)のように単純にlongへcastすると増加分のbitは1で埋められる
- (2)のようにLONG_MASKを使用して下位32 bitはそのままで、上位に0を32 bit付加している
  - (Long#toBinaryStringでは上位の0は表示されていないことに注意)

final long LONG_MASK = 0xffffffffL;
System.out.println("-2 as binary         : " + Integer.toBinaryString(a));
System.out.println("cast to long         : " + Long.toBinaryString((long) a));      // (1)
System.out.println("LONG_MASK as binary  : " + Long.toBinaryString(LONG_MASK));
System.out.println("cast to long and mask: " + Long.toBinaryString(a & LONG_MASK)); // (2)

-2 as binary         : 11111111111111111111111111111110
cast to long         : 1111111111111111111111111111111111111111111111111111111111111110
LONG_MASK as binary  : 11111111111111111111111111111111
cast to long and mask: 11111111111111111111111111111110

Summary

Javaで多倍長整数といえばBigInteger
様々な基数表現からBigIntegerを作成できるようになっており、ちゃんと読めば基数変換やビット演算の理解につながりそう

時間がなくてデータ構造としてのBigIntegerしか捉えられなかったので、次は四則演算の整理をしたいと思います。

参考

BigInteger (Javadoc)