きどたかのブログ

いつか誰かがこのブログからトラブルを解決しますように。

java.math.BigDecimalの最大桁数(理論値)

面倒臭いことを調べることになったJavaプログラマーに捧ぐ

 

すこし時間を割いて最大桁数を計算してみることにしました。

結論からいうと 2793926648桁くらいだと思う。

精度の限界は646443000桁くらいです。

無量大数が128桁です、と補足しておこう。

 

動かすことが出来るかは保証できない。

3GB与えても私はprecision()の結果を得られなかった。

 

 

では机上検証してみようか。

BigDecimal = BigInteger \times 10^{-scale}

 

この式を用いますが、これだけでは足りませんね。

BigIntegerの内容が必要です。

 

BigIntegerのいまの実装を見ると、数字はint配列で持っているようです。

BigIntegerは2の補数表現で数字をもっているそうです。

 

2の補数というのは先頭ビットが1なら負で、0なら正です。

intは4バイトの符号付き整数です。

また、Integer.SIZEにあるように、

2の補数のバイナリ形式に使用するのは32ビットです。

 

int配列は要素数がInteger.MAX_VALUEの配列を作れるはずです。

 MAX VALUE = 2^{31}-1 =2147483647

ここで気付いて欲しいのですが、

4バイトのintを2147483647個も持つ配列なんて確実にOOMです。

int配列だけで8GBのメモリが必要?

 

まあとりあえず32ビットが2147483647個持てるわけですね。

 2^5 \times (2^{31}-1) = 2^{36} -2^5=68719476704

このように68719476704ビット持てます。

符号ビットを除くと68719476703ビットということですね。

 

しかし、ここでひとつの懸念を提示しておこう。

BigIntegerのbitCount()はintを返すのだ。

つまり2147483647ビットまでしか持てないかもしれない。

bitCount()はintの数を返すわけではなく、

intで表しているビットを返すため、

ひとつのintで32ビットしか表せないことを考慮すると、

67108863.96875個のintが限界だ。

 

とりあえず大きいほうから計算してみよう。

目指すビットのイメージは以下の感じになると思います。

0111_11111111_11111111 .....  11111111_11111111 

これで表せる数字は・・・

 2^{68719476703}-1

 

ここからこの公式にあてはめたいと思います。 

log_a(x) = \frac{log_b(x)}{log_b(a)} 

 

log_{10}(2^{68719476703}-1) = \frac{log_2(2^{68719476703}-1)}{log_2(10)}

 

そして心が折れたので、近似値的な値を用いてざっくり計算すると、

68719476703を3.322で割って、

20686176009桁あたりだと思われる。 

 

ここまでがBigIntegerに関する話で、

BigDecimalのスケールで、2147483648桁上積みできるから、

22833659657桁ではないだろうか。

 

bitCount()がintを返すことを気にした検証

※検証結果はこちらの数値を採用してます。

 

さて、ここからは、小さいほうの計算をしてみよう。

ざっくりでいいでしょ?

2793926648桁あたりだとおもう。

2147483646を3.322で割って、646443000あたりを得て、

2147483648を上積みするとこうなる。

 

bitCount()の関係で、2147483647ビットまでしか持てないという前提で

プログラムを書いて検証をしてみた。

2147483647ビットを8ビットのbyteで表すと、

268435455.875個のbyteを使う。

268435456個のbyte配列を作ってみた。

実際には2147483648ビット用意したことになる。

byte top = 0x7F;
byte remain = -1;

byte a = new byte[268435456];
Arrays.fill(a, remain);
a[0] = top;
BigInteger bi = new BigInteger(a);
System.out.println(bi.bitCount());

結果

2147483647

先頭ビットが0なのでそこはカウントしないはずだから、

この結果は期待どおりのものだった。

 

先頭で書いてるバイトの定義が気になるだろう。 

01111111 を作るために0x7F

11111111 を作るために-1

先頭ビットは符号部なので正を表す0をおくためにこうしている。

 

それでは1バイトおおめにnew byte[268435457]ではどうなるか?

 -2147483641

コンストラクタは問題なく通過したけど見事に壊れました。

やはりこのあたりが限界っぽいですね。

内部でただしく2の補数表現でもっているのでしょうが、

このような影響がでてしまっている。

 

BigDecimalのprecision()も壊れないか考えたが、

646443000はintで表せられるのでよしとした。

 

カワイイは作れる 無量大数も作れる (オマケ)

無量大数は128桁、無量大数BigDecimalで余裕で計算できます。

スケールで上積みとかそういうケチなの無しでいけます。

 

128桁のBigDecimalをあらわすのに

BigIntegerがようするbitCountは424ビットほどでした。

int[53]くらいのint配列であらわせる。

メモリ的にも余裕があるのがわかるだろう。

 

またつまらぬものを調べてしまった。