倍長整数クラスの実装.

Java 的なプログラミングの考え方を駆け足で紹介する意図を込めて, 倍長整数クラスを実装してみよう. int=整数, long=長整数と来れば, long long=倍長整数ということで, LongLong クラスである.

入門用のテーマとしては少し重いかも知れないが, 今更 Java 入門…と思っている人に余り退屈な思いをさせたくないので, まあ妥当な線ではないだろうか.

説明の都合上, コードには行番号を付与しているが, もちろん実際のプログラムにはない. 以下に順に並べていくコード片をかき集め, 行番号部分を削除して「LongLong.java」という名前でファイルに保存し, javac コマンドでコンパイルすれば実際に試すことができるだろう. ただし main メソッドなどのドライバは別途必要である.

注意:本テキストは, 実戦的な解説に重きを置いており, 実際の言語仕様に沿った説明とは若干食い違っている箇所がある. 教科書で勉強していくと様々な疑問が湧いてくると思われるが, 些細な疑問を放っておかずにどうにかして確かめるのがクリエイシス流儀である.

クラス:LongLong.

最初の行のパッケージ宣言は, これから定義するクラスのカテゴライズを行うための宣言である. このクラスのように org.creasys.numeric というパッケージであれば, 冒頭で説明した LongLong.java ファイルを, どこか適当に定めたソースコード置き場のルートからの相対パスで「org/creasys/numeric」ディレクトリの下にこの LongLong.java を配置するのが Java の一般的なスタイルである. 別にこの流儀に従う必要はないが, eclipse を初め, 多くのツールはこの流儀に沿っているため, 独自の流儀を押し通せば間違いなく損をする.

3~5 行目は import 宣言である. 自身が属するパッケージと java.lang パッケージは import 宣言をしなくても最初から「見える」が, 他のパッケージの場合は, そこに所属するクラス等を参照する際, いちいちパッケージ名をくっつけるか, または import 宣言を行って以降はパッケージ名を省略するか, どちらかとなる. 普通のプログラマは, この宣言をあまり気にしておらず, eclipse 等のツールの自動 import 生成に任せている.

7~13 行目は, クラスのドキュメンテーションコメントである. 詳細は Javadoc のマニュアル等を参照されたい.

14 行目はクラスの宣言で, extends はスーパクラスの指定, implements は実装するインタフェースの指定となる.

Comparable, Cloneable, Serializable などは, Java 言語の習得に必須の基本的なインタフェースである. 注意深くリファレンスマニュアルを読むべきである.

また, extends 指定が一切ないクラスの場合「extends Object」が省略されているとみなされる. Object はあらゆる Java のクラスのルーツとなるクラスであるため, その理解も必須中の必須である. これを理解していないプログラマは Java プログラムを書く資格がない. リファレンスマニュアルで最初に読むべきは Object の頁である.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
package org.creasys.numeric;

import java.io.Serializable;
import java.util.Random;
import org.creasys.util.Pair;

/**
 * 倍長整数クラス.
 * <p>
 * long 値を 2 個連結し, <code>2 * {@link Long#SIZE}</code> ビットの整数として扱うクラス.
 *
 * @author tt &lt;tanimoto@creasys.org&gt;
 */
public class LongLong extends Number implements Comparable<LongLong>, Cloneable, Serializable {

クラスフィールド群.

クラスフィールドとは、プログラムの開始から終了までの期間に渡って実体が一つだけ存在する変数のことである.

Java 言語は OOPL でありながら, boolean, char, byte, short, int, float, double だけは「オブジェクト」ではなく, プリミティブと呼ばれる型である. クラスフィールドとして, プリミティブ型のフィールドをクラスフィールドとして, しかも final 指定し, 単純な式で初期化すると「定数」として扱われる.

これ以外のケースで final はあまり深い意味を持っておらず, 単なる再代入禁止の変数となる.

16
17
18
19
20
21
22
23
24
25
    /** 倍長整数のビット幅. */
    public static final int SIZE = 2 * Long.SIZE;

    /** 単精度浮動小数点数で表した基数 (<code>2<sup>{@link #SIZE}</sup></code>). */
    private static final float BASE_F = Math.scalb(1.0F, Long.SIZE);
    /** 倍精度浮動小数点数で表した基数 (<code>2<sup>{@link #SIZE}</sup></code>). */
    private static final double BASE_D = Math.scalb(1.0, Long.SIZE);

    /** 乱数発生器. {@link #random()} で使用する. */
    private static Random random = new Random();

インスタンスフィールド群.

インスタンスフィールドは, オブジェクト毎に実体化される変数である. 人クラスと言うものを考えたら, 名前属性はインスタンスフィールドであるべきである.

27
28
29
30
    /** 下位ワード. */
    private long lo;
    /** 上位ワード. */
    private long hi;

クラスメソッド:random.

ざっくりテスト用途に利用するため用意した. クラスメソッドは, 特定のインスタンスに紐づかない操作を表現するメソッドで, 利用する場合は, (このクラスの外からだと)

LongLong x = LongLong.random();

などと書く. import static 宣言によって, 単に「random()」でも呼び出すことができるようになるが, 混乱しがちなのでお勧めはしないし, 私自身 import static は利用しない主義である.

random メソッドの中に random.nextInt() と言うのが登場するが, こちらの random はフィールドの random を意味している. このように Java ではメソッド名とフィールド名が被っていても許される.

32
33
34
35
36
37
38
39
40
41
42
43
    /**
     * ランダムに生成した倍長整数を返す.
     *
     * @return 生成した倍長整数
     */
    public static LongLong random() {
        long xLo = random.nextInt() & 0xFFFFFFFFL;
        xLo |= random.nextInt() << 32;
        long xHi = random.nextInt() & 0xFFFFFFFFL;
        xHi |= random.nextInt() << 32;
        return new LongLong(xLo, xHi);
    }

コンストラクタ.

日本語では「構築子」. メソッドとは区別される. 名前をクラス名として, 戻り型を書かないとコンストラクタとなる. 名前をクラス名としても, 戻り型を書いてしまえば一般のメソッドとなってしまうので, 初心者は注意が必要. (今時は eclipse が警告を出すかも知れない.)

この倍長整数オブジェクトは, 不変オブジェクトとして設計しているので, コンストラクタで初期化した lo, hi フィールドは, オブジェクトが破棄されるまで別の値を再設定されることはない.

45
46
47
48
49
50
51
52
53
    /**
     * 長整数を値とする倍長整数を構築する.
     *
     * @param value 値
     */
    public LongLong(long value) {
        this.lo = value;
        this.hi = value >= 0 ? 0 : -1L;
    }

非公開コンストラクタ.

非公開なので, クラス外からは利用できないコンストラクタである.

55
56
57
58
59
60
61
62
63
64
    /**
     * 下位ワード, 上位ワードを指定して倍長整数を構築する.
     *
     * @param lo 下位ワード値
     * @param hi 上位ワード値
     */
    private LongLong(long lo, long hi) {
        this.lo = lo;
        this.hi = hi;
    }

以降は, 読めば理解できるのではないかと思うので, くどい解説はしない.

メソッド:add.

66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
    /**
     * この倍長整数と与えられた倍長整数の加算を行い, 結果を返す.
     * <p>
     * オーバフローは無視する.
     * <p>
     * 繰り上がり処理の方法はいくつかある.
     * <ol>
     * <li>符号なし整数型をサポートする C/C++ などの場合:<pre>
     *      uint32_t xLo = aLo + bLo;
     *      int32_t xHi = aHi + bHi;
     *      if (xLo &lt; aLo)
     *          ++xHi;</pre>
     * <li>使用しているワードより高精度の整数を利用:<pre>
     *      uint64_t t = (uint64_t) aLo + bLo;
     *      uint32_t xLo = (uint32_t) t;
     *      int32_t xHi = aHi + bHi + (int32_t) (t &gt;&gt; 32);</pre>
     * <li>ハードウェア的な発想:<pre>
     *      uint32_t xLo = aLo + bLo;
     *      int32_t xHi = aHi + bHi + ((aLo &amp; bLo | (aLo | bLo) &amp; ~xLo) &gt;&gt; 31);</pre>
     * </ol>
     * ここでは, 最後の方法をより素直な表現で実装している. 分岐が多いため, 実行効率は良くない.
     *
     * @param b 加数
     * @return 加算結果
     */
    public LongLong add(LongLong b) {
        long xLo = lo + b.lo;
        long xHi = hi + b.hi;
        if (lo < 0 && b.lo < 0 ||
                (lo < 0 || b.lo < 0) && xLo >= 0)
            // 下位ワードから繰り上がり.
            ++xHi;
        return new LongLong(xLo, xHi);
    }

メソッド:sub.

101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
    /**
     * 倍長整数同士の減算を行う.
     * <p>
     * オーバフローは無視する.
     *
     * @param b 減数
     * @return 減算結果
     */
    public LongLong sub(LongLong b) {
        long xLo = lo - b.lo;
        long xHi = hi - b.hi;
        if (lo >= 0 && b.lo < 0 ||
                (lo >= 0 || b.lo < 0) && xLo < 0)
            // 下位ワードへの貸し.
            --xHi;
        return new LongLong(xLo, xHi);
    }

メソッド:mul.

119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
    /**
     * この倍長整数と指定された倍長整数とで乗算を実行し, 結果を返す.
     *
     * <p>オーバフローは無視する.
     *
     * <p><b>アルゴリズム:</b>
     * <blockquote>{@code 積和処理:ワード×ワード+ワード→倍長ワード}</blockquote>
     * の計算をすべて符号なしで行うメソッドを利用する.
     *
     * <p>倍長ワードの被乗数と乗数をそれぞれ
     * <blockquote><code>a = a<sub>L</sub> + a<sub>H</sub> * BASE</code>,<br>
     * <code>b = b<sub>L</sub> + b<sub>H</sub> * BASE</code></blockquote>
     * とすると, 乗算結果 {@code x} は,
     * <blockquote><table>
     * <tr><td><code>x</code></td><td colspan="2"><code>= x<sub>L</sub> + x<sub>H</sub> *
     * BASE</code></td></tr>
     * <tr><td></td><td colspan="2"><code>= a * b</code></td></tr>
     * <tr><td></td><td><code>= a<sub>L</sub> * b<sub>L</sub></code></td><td><code>+ a<sub>H</sub> *
     * b<sub>L</sub> * BASE</code></td></tr>
     * <tr><td></td><td></td><td><code>+ a<sub>L</sub> * b<sub>H</sub> * BASE + a<sub>H</sub> *
     * b<sub>H</sub> * BASE<sup>2</sup></code></td></tr>
     * <caption></caption></table></blockquote>
     * となる. 各項を表にすると, 以下の通り.
     * <blockquote><table border="1">
     * <tr><td width="50%" colspan="2">a<sub>L</sub> * b<sub>L</sub></td><td width="25%">&nbsp;</td>
     * <td width="25%">&nbsp;</td></tr>
     * <tr><td width="25%">&nbsp;</td><td colspan="2">a<sub>H</sub> * b<sub>L</sub></td>
     * <td>&nbsp;</td></tr>
     * <tr><td>&nbsp;</td><td colspan="2">a<sub>L</sub> * b<sub>H</sub></td><td>&nbsp;</td></tr>
     * <tr><td>&nbsp;</td><td>&nbsp;</td><td colspan="2">a<sub>H</sub> * b<sub>H</sub></td></tr>
     * <tr><td>x<sub>L</sub></td><td>x<sub>H</sub></td><td>&nbsp;</td><td>&nbsp;</td></tr>
     * <caption></caption></table></blockquote>
     * このうち, 最後の <code>a<sub>H</sub> * b<sub>H</sub></code> の項は,
     * オーバフローを無視するので不要である. これをそのまま手順化すると以下のようになる.
     *
     * <blockquote><ul>
     * <li><code>t<sub>0L</sub>:t<sub>0H</sub> ← a<sub>L</sub> * b<sub>L</sub>,</code></li>
     * <li><code>x<sub>L</sub> ← t<sub>0L</sub>.</code></li>
     * <li><code>t<sub>1L</sub>:t<sub>1H</sub> ← a<sub>H</sub> * b<sub>L</sub> +
     * t<sub>0H</sub>.</code></li>
     * <li><code>x<sub>H</sub> ← t<sub>1L</sub>.</code></li>
     * <li><code>t<sub>2L</sub>:t<sub>2H</sub> ← a<sub>L</sub> * b<sub>H</sub> +
     * x<sub>H</sub>.</code></li>
     * <li><code>x<sub>H</sub> ← t<sub>1L</sub>.</code></li>
     * </ul></blockquote>
     * <p>
     * ワード同士の符号なし乗算結果の下位ワードのみを取り出すと, 符号付き乗算の結果と一致するため,
     * 特に符号の処理は必要ない.
     *
     * @param b 乗数
     * @return 乗算結果
     */
    public LongLong mul(LongLong b) {
        long xLo;
        long xHi;
        LongLong da;
        da = mulx(lo, b.lo, 0L, 0L);
        xLo = da.lo;
        da = mulx(hi, b.lo, da.hi, 0L);
        xHi = da.lo;
        da = mulx(lo, b.hi, 0L, xHi);
        xHi = da.lo;
        return new LongLong(xLo, xHi);
    }

メソッド:mulx.

184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
    /**
     * 符号なし長整数の積和処理を行う.
     * 正確には「長整数×長整数+長整数+長整数→倍長整数」を実行する.
     * <p>
     * オーバフローは発生しない. <code>B = 2<sup>Long.SIZE</sup></code>
     * とすると, 長整数の最大値は <code>U = B - 1</code> なので,
     *
     * <blockquote><table><tr><td><code>U * U + U + U</code></td>
     * <td><code>= (B - 1)<sup>2</sup> + 2 * (B - 1)</code></td></tr>
     * <tr><td></td><td><code>= B<sup>2</sup> - 1</code></td></tr>
     * <caption></caption></table></blockquote>
     * <p>
     * つまり, 最大でちょうど符号なし倍長整数の最大値となる.
     *
     * @param a 被乗数
     * @param b 乗数
     * @param c 加数1
     * @param d 加数2
     * @return 積和演算結果
     */
    private static LongLong mulx(long a, long b, long c, long d) {
        int x0 = (int)  c;
        int x1 = (int) (c >>> 32);
        int x2;
        int x3;
        long da;
        da = mulx((int)  a        , (int)  b        , (int)  d         , x0);
        x0 = (int) da;
        da = mulx((int) (a >>> 32), (int)  b        , (int) (da >>> 32), x1);
        x1 = (int) da;
        x2 = (int) (da >>> 32);
        da = mulx((int)  a        , (int) (b >>> 32), (int) (d  >>> 32), x1);
        x1 = (int) da;
        da = mulx((int) (a >>> 32), (int) (b >>> 32), (int) (da >>> 32), x2);
        x2 = (int) da;
        x3 = (int) (da >>> 32);
        return new LongLong(x0 & 0xFFFFFFFFL | (long) x1 << 32, x2 & 0xFFFFFFFFL | (long) x3 << 32);
    }

    /**
     * 符号なし整数の積和演算「整数×整数+整数+整数→長整数」を行う.
     * <p>
     * オーバフローは発生しない. <code>B = 2<sup>{@link Integer#SIZE}</sup></code>
     * とすると, 符号なし整数の最大値は <code>U = B - 1</code> なので,
     *
     * <blockquote><table><tr><td><code>U * U + U + U</code></td>
     * <td><code>= (B - 1)<sup>2</sup> + 2 * (B - 1)</code></td></tr>
     * <tr><td></td><td><code>= B<sup>2</sup> - 1</code></td></tr>
     * <caption></caption></table></blockquote>
     * <p>
     * つまり, 最大でちょうど符号なし長整数の最大値となる.
     *
     * @param a 被乗数
     * @param b 乗数
     * @param c 加数1
     * @param d 加数2
     * @return 積和演算結果
     */
    private static long mulx(int a, int b, int c, int d) {
        return (a & 0xFFFFFFFFL) * (b & 0xFFFFFFFFL) + (c & 0xFFFFFFFFL) + (d & 0xFFFFFFFFL);
    }

メソッド:div.

246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
    /**
     * 倍長整数同士の除算を実行し, 結果を返す.
     *
     * @param b 除数
     * @return 除算結果
     */
    public LongLong div(LongLong b) {
        if (b.lo == 0 && b.hi == 0)
            throw new ArithmeticException();

        boolean negative = false;
        LongLong a = this;
        if (a.hi < 0) {
            negative = !negative;
            a = a.negate();
        }
        if (b.hi < 0) {
            negative = !negative;
            b = b.negate();
        }
        LongLong x = a.divUnsigned(b);
        if (negative)
            x = x.negate();
        return x;
    }

メソッド:divUnsigned.

272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
    /**
     * 符号なし倍長整数同士の除算を実行する.
     * <p>
     * 筆算の方式を 2 進法で行う. 被除数を倍ワードに拡張したものと商ワードを,
     * 1ビットずつ左にシフトしながら, 拡張被除数の上位ワードから除数が引ければ引き,
     * 商の最下位ビットを立てる. この操作を商のビット数回繰り返せばよい.
     * このメソッドでは利用していないが, この操作が終わったとき,
     * 拡張被除数の上位ワードには余が得られている.
     * <p>
     * ビット数分ループするので, 効率は良くないが, 単純かつ確実な方法である.
     * 少しだけ改良するとすれば,
     * 拡張被除数をシフトしていくとき下位ビットは使用しなくなっていくため,
     * この部分に商を入れてしまうと言うトリッキーな方法がよく使われる.
     * <p>
     * プロセッサによっては「倍ワード÷ワード→ワード(商)...ワード(余)」を実行する命令を持っているが,
     * その場合はこの命令を利用すると効率は格段に良くなる.
     *
     * @param b 除数
     * @return 除算結果
     */
    public LongLong divUnsigned(LongLong b) {
        LongLong l = this;
        LongLong h = new LongLong(0L, 0L);
        LongLong q = new LongLong(0L, 0L);

        for (int k = 0; k < SIZE; ++k) {
            // 拡張被除数を1ビット左シフト.
            h = h.shift(1, false);
            if (l.hi < 0)
                h = h.increment();
            l = l.shift(1, false);

            // 商をシフト.
            q = q.shift(1, false);

            // 拡張被除数の上位ワードから, 除数が引ければ引く.
            if (h.compareUnsigned(b) >= 0) {
                h = h.sub(b);

                // 引けた場合は, 商の最下位ビットを立てる.
                q = q.increment();
            }
        }
        return q;
    }

メソッド:negate.

318
319
320
321
322
323
324
325
326
327
328
329
330
331
    /**
     * 倍長整数の符号反転.
     * <p>
     * オーバフローは無視する.
     *
     * @return 符号反転結果
     */
    public LongLong negate() {
        long xLo;
        long xHi;
        xLo = -lo;
        xHi = xLo == 0 ? -hi : ~hi;
        return new LongLong(xLo, xHi);
    }

メソッド:increment.

333
334
335
336
337
338
339
340
341
342
343
344
    /**
     * 倍長整数の次の整数を返す.
     *
     * @return 次の整数
     */
    public LongLong increment() {
        long xLo = lo + 1;
        long xHi = hi;
        if (xLo == 0)
            ++xHi;
        return new LongLong(xLo, xHi);
    }

メソッド:shift.

346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
    /**
     * 倍長整数のシフト演算を行う.
     *
     * @param k シフトするビット数. 負の場合は右シフトを意味する.
     * @param arithmetic 真なら右シフトの場合に算術シフトを指定する. 左シフトの場合は意味を持たない
     * @return シフト演算結果
     */
    public LongLong shift(int k, boolean arithmetic) {
        LongLong result;
        if (k > 0)
            result = shiftLeft(k);
        else if (k < 0)
            // 落とし穴アリ.
            // k == Integer.MIN_VALUE だった場合 -k も負のまま.
            // shiftRight はシフト回数を符号なしとして扱っているので問題はない.
            result = shiftRight(-k, arithmetic);
        else
            result = this;
        return result;
    }

メソッド:shiftLeft.

367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
    /**
     * 倍長整数の左シフトを行う.
     *
     * @param k シフトするビット数. 符号なし数と見なす
     * @return シフト結果
     */
    private LongLong shiftLeft(int k) {
        long xHi;
        long xLo;
        if (0 <= k && k < Long.SIZE) {
            //                  +----------------+----------------+
            // シフト前         |      上位      |      下位      |
            //            +-----+----------+-----+----------+-----+
            // シフト後   |      上位      |      下位      | 000 |
            //            +----------------+-----+----------+-----+
            //                                   |   64-k   |  k  |
            xHi = hi << k | lo >>> (Long.SIZE - k);
            xLo = lo << k;
        } else if (Long.SIZE <= k && k < 2 * Long.SIZE) {
            //                   +----------------+----------------+
            // シフト前          |      上位      |      下位      |
            //            +------+---------+------+----------------+
            // シフト後   |      下位      | 000000000000000000000 |
            //            +----------------+------+----------------+
            //                             | k-64 |       64       |
            xHi = lo << (k - Long.SIZE);
            xLo = 0L;
        } else {
            xHi = 0L;
            xLo = 0L;
        }
        return new LongLong(xLo, xHi);
    }

メソッド:shiftRight.

401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
    /**
     * 倍長整数の右シフトを行う.
     *
     * @param k シフトするビット数. 符号なし数と見なす
     * @param arithmetic 算術シフトを示す
     * @return シフト結果
     */
    private LongLong shiftRight(int k, boolean arithmetic) {
        long xLo;
        long xHi;
        if (0 <= k && k < Long.SIZE) {
            xLo = lo >>> k | hi << (Long.SIZE - k);
            xHi = arithmetic ? hi >> k : hi >>> k;
        } else if (Long.SIZE <= k && k < 2 * Long.SIZE) {
            xLo = arithmetic ? hi >> (k - Long.SIZE) : hi >>> (k - Long.SIZE);
            xHi = arithmetic ? hi >> (Long.SIZE - 1) : 0L;
        } else {
            xLo = arithmetic ? hi >> (Long.SIZE - 1) : 0L;
            xHi = arithmetic ? hi >> (Long.SIZE - 1) : 0L;
        }
        return new LongLong(xLo, xHi);
    }

Comparableの実装.

424
//==== Comparable<LongLong>

メソッド:compareTo.

本メソッドは, インタフェース Comparable で宣言されているメソッドの実装となる. 「@Override」のような記述は annotation, 日本語では「注釈」などと呼ばれる. @Override は, メソッドを実装したりオーバライドしたりしていることを明示するのが目的で, これを書かないとツールが警告を発したりするし, 逆にオーバライドも実装もしていないメソッドに付けても怒られる.

ちなみに Java 5 以前はオーバライドだけに使用することになっていたが, Java 6 以降はインタフェースの実装にも書くようになったと言う, gdgd な経緯がある.

426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
    /**
     * この倍長整数と指定された倍長整数を自然比較する.
     *
     * @param o 比較対象の倍長整数
     */
    @Override
    public int compareTo(LongLong o) {
        int comparison;
        if (hi == o.hi) {
            if (lo == o.lo)
                // 上位ワードも下位ワードも等しい.
                comparison = 0;
            else
                // 上位ワードの符号とは無関係に下位ワード同士を符号なし数として比較する.
                if (lo < 0 && o.lo >= 0)
                    // 負 : 正.
                    comparison = +1;
                else if (lo >= 0 && o.lo < 0)
                    // 正 : 負.
                    comparison = -1;
                else
                    // 同符号.
                    comparison = lo - o.lo >= 0 ? +1 : -1;
        } else
            // 上位ワードが等しくない.
            // 上位ワード同士で比較する.
            comparison = hi >= o.hi ? +1 : -1;
        return comparison;
    }

メソッド:compareUnsigned.

456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
    public int compareUnsigned(LongLong o) {
        int comparison;
        if (hi == o.hi) {
            if (lo == o.lo)
                comparison = 0;
            else
                if (lo < 0 && o.lo >= 0)
                    comparison = +1;
                else if (lo >= 0 && o.lo < 0)
                    comparison = -1;
                else
                    comparison = lo - o.lo >= 0 ? +1 : -1;
        } else
            if (hi < 0 && o.hi >= 0)
                comparison = +1;
            else if (hi >= 0 && o.hi < 0)
                comparison = -1;
            else
                comparison = hi - o.hi >= 0 ? +1 : -1;
        return comparison;
    }

Numberの拡張.

478
//==== Number

メソッド:intValue.

480
481
482
483
484
485
486
487
488
    /**
     * この倍長整数の下位 32 ビットを返す.
     *
     * @return 下位 32 ビット
     */
    @Override
    public int intValue() {
        return (int) lo;
    }

メソッド:longValue.

490
491
492
493
494
495
496
497
498
    /**
     * この倍長整数の下位 64 ビットを返す.
     *
     * @return 下位 64 ビット
     */
    @Override
    public long longValue() {
        return lo;
    }

メソッド:floatValue.

500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
    /**
     * この倍長整数の値を単精度浮動小数点数として返す.
     *
     * <p><b>バグ入り注意.</b>
     *
     * @return 単精度浮動小数点数で表した値
     */
    public float floatValueNaive() {
        float x;
        if (lo >= 0)
            x = hi * BASE_F + lo;
        else
            x = hi * BASE_F + (lo + BASE_F);
        return x;
    }

    /**
     * この倍長整数の値を単精度浮動小数点数として返す.
     *
     * <p>数学的には <code>(符号付き)上位ワード * 2<sup>64</sup> + (符号なし)下位ワード</code>
     * を返せばよいが, そのまま実装すると精度が悪い.
     *
     * @return 単精度浮動小数点数で表した値
     */
    @Override
    public float floatValue() {
        LongLong abs = hi >= 0 ? this : negate();
        float x = abs.lo >= 0
                ? abs.hi * BASE_F + abs.lo
                : abs.hi * BASE_F + (abs.lo + BASE_F);
        if (hi < 0)
            x = -x;
        return x;
    }

メソッド:doubleValue.

535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
    /**
     * この倍長整数の値を倍精度浮動小数点数として返す.
     *
     * @return 倍精度浮動小数点数で表した値
     */
    @Override
    public double doubleValue() {
        LongLong abs = hi >= 0 ? this : negate();
        double x = abs.lo >= 0
                ? abs.hi * BASE_D + abs.lo
                : abs.hi * BASE_D + abs.lo + BASE_D;
        if (hi < 0)
            x = -x;
        return x;
    }

Objectの拡張.

551
//==== Object

メソッド:clone.

このメソッドをサラリと実装できるようになると, そろそろ Java の脱初心者と言うことになる. (ホントか)

super.clone() は, 結局最終的には Object.clone() に行きつくことになっているので Object の仕様を見ること. また Cloneable の仕様にも一応目を通すと良いが, Cloneable は単なるマーカインタフェースであると言う驚愕の事実は知っておくべき.

553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
    /**
     * この倍長整数の複製を返す.
     * <p>
     * 例として実装しているが, そもそもこの倍長整数オブジェクトは不変であるため, 複製の必要はない.
     *
     * @return 複製
     */
    @Override
    public LongLong clone() {
        try {
            return (LongLong) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
    }

メソッド:equals.

569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
    /**
     * この倍長整数と他のオブジェクトが等しいかどうかを示す.
     * <p>
     * 倍長整数が他のオブジェクトと等しいのは, 他のオブジェクトが倍長整数のインスタンスであり,
     * かつその下位ワードおよび上位ワードがそれぞれこの倍長整数の下位ワード,
     * 上位ワードと等しい場合に限る.
     *
     * @param o 比較対象の参照オブジェクト
     * @return この倍長整数が o 引数と等しい場合は {@code true}, それ以外の場合は {@code false}
     */
    @Override
    public boolean equals(Object o) {
        boolean equality;
        if (o instanceof LongLong) {
            LongLong that = (LongLong) o;
            equality = lo == that.lo && hi == that.hi;
        } else {
            equality = false;
        }
        return equality;
    }

メソッド:hashCode.

591
592
593
594
595
596
597
598
599
600
601
602
    /**
     * この倍長整数のハッシュコード値を返す.
     *
     * @return この倍長整数のハッシュコード値
     */
    @Override
    public int hashCode() {
        int code;
        code = (int) lo ^ (int)(lo >>> 32);
        code ^= (int) hi ^ (int)(hi >>> 32);
        return code;
    }

ゴミ.

以下は、実験中のメソッド.

もうちょっとマシな除算のアルゴリズムを実装しようとしていたが, 間に合いそうにないので諦めた. いつか改良したいが, そもそも Java でこういう処理を書くのは苦痛以外の何ものでもない...

604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
//==== 実験的メソッド.

    public static long divModUnsigned(long num, int den) {
        for (int k = 0; k < 32; ++k) {
            boolean carry = num < 0;
            num <<= 1;
            if (carry || (num >>> 32) >= (den & 0xFFFFFFFFL)) {
                num -= (long) den << 32;
                ++num;
            }
        }
        return num;
    }

    public Pair<LongLong, LongLong> divModUnsigned(LongLong numH, LongLong den) {
        LongLong numL = this;
        for (int k = 0; k < SIZE; ++k) {
            boolean carry = numH.hi < 0;
            numH = numH.shiftLeft(1);
            if (numL.hi < 0)
                numH = numH.increment();
            numL = numL.shiftLeft(1);
            if (carry || numH.compareUnsigned(den) >= 0) {
                numH = numH.sub(den);
                numL = numL.increment();
            }
        }
        return Pair.of(numL, numH);
    }
}