FC2ブログ
ヽ|∵|ゝ(Fantom) の 開発blog? ホーム »べき乗
このページの記事一覧

【Java】数値の桁数を調べる(べき乗の桁数・べき乗のべき乗の桁を調べる)  


 数値の桁数を知りたいシーンはわりと良くあるもので、調べてみると「10で割っていく方法」や「文字列に変換する方法」「対数を使う方法」「配列にあらかじめ各桁の最大(9999のような)を入れておいて比較する方法」などあるようだが、実行速度は言語によってまちまちのようなので、簡単なアルゴリズムを色々知っておいても損はないだろうと試してみた。




■10で割っていく方法

 まずは一番オーソドックスな方法(?)でやってみよう。これは以前書いた「基数変換のアルゴリズム」と同じと言っても良い。基数変換では具体的な桁の値をリストで返しているが、それをカウントに変えるだけだ。故に基数変換の戻値のリストのサイズ(List.size())でも同じとなる。まずは基数変換のコードの一部を抜き出して少しばかり改造してみよう。

●10で割って桁数をカウントする
/**<h1>整数の桁数を求める</h1>
* <p>0 となるまで、10 で割り続ける方法。</p>
* @param value : 調べる値
* @return<b>int</b> : 桁数 (負の値は '-' を除いた桁数)
*/
public static final int length(long value) {
int cnt = 0;
do {
cnt++;
value /= 10;
} while (value != 0);
return cnt;
}


//メインでは...
int n = 1234; //4
//int n = -4321; //4
//int n = 0; //1
System.out.println(length(n));

4

 負の値のとき、マイナス記号 '-' を除外してカウントしているが、負の割り算は言語によって仕様が違うので、他の言語に移植するときは注意しよう(Ruby などは上手くいかない)。心配なら関数のはじめに絶対値(Math.abs())などで正の値にしておくと良い(Java では無くても良い)。調べる値が 0 のとき、1 桁としたいので、すぐにインクリメントしているが、while に書きなおしたいときは、はじめからカウントを 1 にしておけば良いだろう。上記の例は基数変換のコードをもとにしているが、以下のように while でシンプルに書くこともできる。

●上記の例を while に書きなおしたもの
/**<h1>整数の桁数を求める</h1>
* <p>0 となるまで、10 で割り続ける方法。</p>
* @param value : 調べる値
* @return<b>int</b> : 桁数 (負の値は '-' を除いた桁数)
*/
public static final int length(long value) {
int cnt = 1; //0 にも対応
while ((value /= 10) != 0) {
cnt++;
}
return cnt;
}


//メインでは...
int n = 1234; //4
//int n = -4321; //4
//int n = 0; //1
System.out.println(length(n));

4

 内容は全く同じで、実行速度も変わらないので、好みの書き方で選べば良い。




■文字列に変換する方法

 「10で割る方法」と同じようによく使われるのは、「文字列に変換する方法」だ。ただし、Java の場合は文字列変換は負荷が高いので、実行速度は遅くなる。しかし、Ruby をはじめ、PHP や Perl のようなスクリプト言語は文字列変換のスピードは非常に速いので、むしろ「10で割る方法」の方が遅いらしい。参考までに色々な言語でやっているページを載せておくが、私が実際に Ruby で試したところ、「loop do~break if~」の代わりに「while」に書きなおしたら、ここまでの差は出なかった(それでも文字列変換の方がわずかに速い)。他の言語から移植するときのためにも、この手のやり方には慣れておいた方が良いだろう。

(参考)
整数の桁数を求める方法

●文字列に変換し、長さを取得する
//int n = 1234;     //4
int n = -4321; //4
//int n = 0; //1

System.out.println(String.valueOf(Math.abs(n)).length());

4

 なお、値が正の数だけとわかっていれば、Math.abs() は必要ない。




■べき乗(xk)の桁数を調べる

 次に、普通に計算したらオーバーフローするような「べき乗の値の桁を調べる方法」をやってみよう。それは(常用)対数関数Math.log10())を使う方法だ。ちなみにこの方法で int や long の桁数を調べることもできるが、log() は負荷が高い関数なので、「10で割る方法」の方がよほど速い。なので、整数型では求められない値など、使い分けが必要になるだろう。

 まずは簡単に対数関数の使い方をおさらいしてみよう。といっても高校の数学の教科書そのままの内容だ(笑)。また対数関数指数関数は裏返しの関数なので、ついでにおさらいしておくとなお良い。以下の問題の解き方を丸暗記してしまえば、わりと簡単に理解できるハズだ。

【問】230は何桁の数字か。log102 = 0.3010 を用いて調べよ。

【解】
log102 = 0.3010 だから、2 = 100.3010  [指数への変換:logap = q ⇔ p = aq]
230 = (100.3010)30
  = 100.3010×30  [指数法則:(ap)q = ap×q]
  = 109.03
よって、109 < 230 < 1010
したがって、230 は 10桁の数字である。  [109 = 1,000,000,000 (頭 1 と 0 が 9 個で 10桁)]


 さて、上の解法を理解したら、いよいよ本題のべき乗(xk)の桁数を求めてみよう。例で使ってるのは底が10である常用対数の使い方であるが、それは言い換えればある数値 n を 10q に置き換える関数であり、桁を表していると言える。つまり、ここでは具体的な値ではなく、桁数を求めたいわけだから、10 の指数部分 q を求めれば良いわけである。

 上の例を用いれば桁数は 230 = 109.03 の 9.03 部分のことで、これは log102×30 であり、この値の小数部分を切り捨て、1 を足したものである(頭 1 と 0 が 9 個で 10桁)。この 2 を x、30乗を k と置けば、以下のようになっているとわかるだろう。

230 = 100.3010×30 = 10log102×30

(2 を x、30乗を k と置くと)
xk = 10log10x × k  … ① (←以降、この式を公式のように扱う)

(桁数は指数部分のことだから)
桁数 = floor(log10x × k) + 1

●べき乗(xk)の桁数を log10() により求める
/**<h1>x<sup>n</sup> の桁数を求める</h1>
* <p>log10() により求める。底が負のときは NaN となるので注意。</p>
* @param x : 底 (> 0)
* @param k : べき指数 (>= 0)
* @return<b>double</b> : 桁数
*/
public static final double powLength(final double x, final double k) {
return Math.floor(Math.log10(x) * k) + 1;
}


//メインでは...
int x = 2, k = 30; //10.0
//int x = 123456789, k = 99999; //809144.0
System.out.println(powLength(x, k));

10.0

 log() の引数は負の値だと NaN が返される注意しよう。必要ならエラーを投げるのも良い。引数の値によっては非常に大きな桁数になるので double のまま返しているが、値の範囲がわかっていれば整数型にキャストするのも良いだろう。Java の場合、long は 19桁の値、double は指数表現を含めて 309桁の値まで表せるが、べき乗はあっという間にオーバーフロー(Infinity)することがあるので、使う際にはあらかじめ確認しておいた方が良いだろう。




■べき乗のべき乗(xyz)の桁数を求める

 次に更にべき乗をかけた「べき乗のべき乗」の桁を調べてみよう。考え方は「べき乗(xk)の桁数を調べる」をそのままで、少しばかり拡張したものになる。その式を考えてみよう。

(xyz の指数部分 yz を log10 を使って変換すると [①を参照])
yz = 10log10y × z

(xyz の指数部分 yz を k と置き、同じように変換すると [①を参照])
xyz = xk = 10log10x × k

(k を元に戻すと)
xyz = xk = 10log10x × 10log10y × z

(桁数は指数部分のことだから)
桁数 = floor(log10x × 10log10y × z) + 1

●べき乗のべき乗(xyz)の桁数を log10() により求める
/**<h1>x<sup>y<sup>z</sup></sup> (べき乗のべき乗)の桁数を求める</h1>
* <p>log10() により求める。底が負のときは NaN となるので注意。</p>
* @param x : 底 (> 0)
* @param y : べき指数1 (>= 0)
* @param z : べき指数2 (>= 0)
* @return<b>double</b> : 桁数 (オーバーフロー: Infinity に注意)
*/
public static final double powpowLength(final double x, final double y, final double z) {
final double p = Math.log10(y) * z; //y^z
final double q = Math.log10(x); //x^p
return Math.floor(q * Math.pow(10, p)) + 1;
}


//メインでは...
int x = 2, y = 3, z = 5; //74.0
//int x = 5, y = 6, z = 7; //195667.0
System.out.println(powpowLength(x, y, z));

74.0




■2つのべき乗のべき乗(xyz, abc)の大きさを比較する

 ここでは2つのべき乗のべき乗(xyz, abc)の大小関係を比較することを考えてみよう。もちろん前述した「べき乗のべき乗(xyz)の桁数を求める」で比較しても構わないが、なぜわざわざ比較だけをピックアップしたかというと、引数によっては「べき乗のべき乗」では桁数が非常に大きくなりオーバーフロー(Infinity)しかねないので、対数のまま利用した方が良いからだ。もう一度「べき乗のべき乗(xyz)の桁数を求める」のコードを見てみよう。桁数が大きくなる原因に「Math.pow(10, p)」という部分がある。ここを変形してオーバーフローを防ぐ方法を考えてみよう。

(桁数を表す指数部分を抜き出すと)
yz = log10x × 10log10y × z

log10x = m と置き、今までと同じように[①を参照] 10q に変形すると、m = 10log10m [m1 = 10log10m × 1

(m を元に戻すと)
10log10m = 10log10(log10x) (= log10x)

(yzの式に代入して)
yz = 10log10(log10x) × 10log10y × z = 10log10(log10x) + log10y × z [指数法則:ap×aq = ap+q]

(xyzの式に戻すと)
xyz = 1010log10(log10x) + zlog10y

(つまり、一番上の指数だけを比較すれば大小関係がわかる)
log10(log10x) + zlog10y

●べき乗のべき乗(xyz)の比較をする
/**<h1>x<sup>y<sup>z</sup></sup> (べき乗のべき乗) の log10() を返す</h1>
* <p>この値で比較すれば、大小関係がわかる。底が負のときは NaN となるので注意。</p>
* @param x : 底 (> 0)
* @param y : べき指数1 (>= 0)
* @param z : べき指数2 (>= 0)
* @return<b>double</b> : 底を10<sup>10</sup>に合わせた log10() を返す
*/
public static final double powpowLog10(final double x, final double y, final double z) {
final double p = Math.log10(y) * z; //y^z
final double q = Math.log10(Math.log10(x)); //10^q = log10 x
return p + q;
}

/**<h1>x<sup>y<sup>z</sup></sup> (べき乗のべき乗) 同士の大小の比較</h1>
* <p>比較の関係値を返す(-1, 0, 1 のみ)。差分ではない。</p>
* @param x1 : 底 a (> 0)
* @param y1 : べき指数1 a (>= 0)
* @param z1 : べき指数2 a (>= 0)
* @param x2 : 底 b (> 0)
* @param y2 : べき指数1 b (>= 0)
* @param z2 : べき指数2 b (>= 0)
* @return<b>int</b> : -1 : a < b / 1 : a > b / 0 : a == b
*/
public static final int powpowCompare(final double x1, final double y1, final double z1,
final double x2, final double y2, final double z2) {

final double a = powpowLog10(x1, y1, z1);
final double b = powpowLog10(x2, y2, z2);
if (a < b) {
return -1;
} else if (a > b) {
return 1;
} else {
return 0;
}
}


//メインでは...
int x1 = 123456, y1 = 9876543, z1 = 24356891; //Infinity
int x2 = 333333, y2 = 5555555, z2 = 22222222; //Infinity
System.out.println(powpowLength(x1, y1, z1));
System.out.println(powpowLog10(x1, y1, z1));
System.out.println(powpowLength(x2, y2, z2));
System.out.println(powpowLog10(x2, y2, z2));
System.out.println(powpowCompare(x1, y1, z1, x2, y2, z2));

Infinity
1.7036683127845693E8
Infinity
1.4988283149816477E8
1

 この方法で行けば、309桁(Double.MAX_VALUE = 1.7976931348623157E308) までは比較できる

 また、比較だけなら、Math.log10() の代わりに Math.log() を使っても良いが、値が大きくなる可能性があるので、Math.log10() を使った方が無難かも知れない(実行速度も変わらない)。もちろん引数が負の値のときは NaN となるので注意しよう。戻値は比較の関係値を返す -1, 0, 1 のみにしているが、必要なら (a - b) の差分を返すように改造しても良いだろう(ただし、型に注意。比較関数は大抵 int になっているので)。

 ちなみに同じように「べき乗のべき乗のべき乗」も考えられるが、log() を3回以上入れ子にすると負の値となってしまうので、上手く行かないようだ。式としては以下のようになる。

wxyz = 101010log10(log10(log10w)) + log10(log10x) + zlog10y

(一番上の指数だけを抜き出せば)
log10(log10(log10w)) + log10(log10x) + zlog10y

 式は無理矢理なので、正しい書き方とかは勘弁して欲しい(笑)。級数(数列の和)っぽく書けばもっとカッコイイのかも知れないが、この書き方なら高校数学の範疇なので理解できるハズだ(無理矢理感は別として)。でもまぁ、log() でもこれ以上は無理そうなので、他の方法を研究してみるのも面白いだろう。




■任意精度を使う

 最後に任意精度実数を使って桁を調べてみよう。考え方としては「文字列に変換する方法」と同じと思って良い。具体的な値を返すので、桁が大きくなるほど重くなるが、検算したいときには役に立つこともあるだろう(といっても100万桁ぐらいが限界でそれ以上はフリーズしたようになる)。なお、BigInteger を用いても構わないが、桁を調べるだけなら、文字列に変換する(toString())する必要はないので、整数部分の桁を返す BigDecimal.precision() を使った方が速い

●任意精度実数で具体的な値と桁数を調べる
int x = 2, y = 3, z = 5;
int a = (int)Math.pow(y, z);
BigDecimal b = new BigDecimal(x).pow(a);
System.out.println(b.toString());
System.out.println(b.precision());
System.out.println(powpowLength(x, y, z));

14134776518227074636666380005943348126619871175004951664972849610340958208
74
74.0

 上の例はべき乗のべき乗(235)と同じものだ。ただし、BigDecimal.pow() の引数は int 型にしか対応していない(と言っても、long でできたとして重すぎてフリーズしたようになると思うが)。具体的な値を知りたければ文字列化(toString())すれば良いが、桁が大きいときは負荷が高いので、あらかじめ値の範囲を調べた上で使った方が良いだろう。オンラインジャッジでの問題などでは、任意精度ではほとんどの場合タイムアウトすると思うので、桁数だけなら、前述の「powLength()」(べき乗の桁数)や「powpowLength()」(べき乗のべき乗の桁数)を使った方が速い。


(関連記事)
【Java】n進数変換(基数変換)・桁の分割をする
【Java】べき乗計算を高速化する(繰り返し二乗法)
【Java】任意精度整数(多倍長整数)で演算する


■参考になる書籍


スポンサーサイト

category: Java

thread: プログラミング

janre: コンピュータ

tag: 算術関数  べき乗  アルゴリズム 
tb: 0   cm: --

【Java】べき乗計算を高速化する(繰り返し二乗法)  


 どちらかというとプロコン用ライブラリという使い方になるかもしれないが、大量のべき乗計算が必要になったとき、高速に計算する方法を知っておけば、イザというとき役に立つかもしれない。

 今回紹介する方法は「繰り返し二乗法」という算法である。数学的に解説してもいいが、ググればたくさん出てくるので、理論はさておき、大雑把な方法論だけ覚えてしまおう(笑)。

●繰り返し二乗法によるべき乗計算
/**<h1>べき乗計算(繰り返し二乗法)</h1>
* <p>Math.pow() の約5倍速い。</p>
* @param x : 底
* @param n : べき指数
* @return<b>long</b> : x<sup>n</sup>
*/
public static final long pow(long x, long n) {
long sum = 1;
while (n > 0) {
if ((n & 1) == 1) { //ビットが立っていたら
sum *= x; //x^2^k1 * x^2^k2 * x^2^k3 * ・・・
}
x *= x; //((x^2)^2)^2・・・
n >>= 1;
}
return sum;
}


 簡単に解説すると、使うのは主に指数法則である。例えば、べき乗の計算をするとき、for ループなどで x を n 回かける場合、n の値が大きいほど計算時間がかかるので、指数法則を用いて、((x2)2)2 ・・・ のように2乗を繰り返して、計算回数を減らそうというアルゴリズムである。この場合オーダーは O(log n) となるので、大量の計算でも高速にできる。

 ではその2乗する n をどうやって分解したらいいかというと、2進法を使うのである。というのも2進数というのは元々それぞれのビットが、20=1、21=2、22=4、23=8、24=16、・・・ を表しているので、指数 n のビットを見れば、どの n = 2k をかければ良いのかわかるのである。言葉で説明すると難しく感じるので、具体的な数値を指数法則で分解したり、2進数と照らしあわせて見て欲しい。


 つまり指数 n のビットが立っているかを下位から判別していき、立っていたら x を 2k 乗した値をかけていくのである。これが x1 × x2 × x4 × x8 × x16 ・・・ となっていく。なんとなく数学的によくわからないと思ったら、以下の資料などを見てみると良いだろう。わかってしまえば、そう難しいものでもない。

(参考)
繰り返し二乗法
冪乗
繰り返し自乗法

 ちなみに実行速度は Math.pow()約5倍ほどの速度で計算できる

 また、値が long で計算されているが、指数の n 以外を double にしても良い。その場合は、17桁以降が丸められる感じになる(Math.pow() とは少し違う丸め値になる)。double にした場合、Math.pow()約3倍ほどの速さになるようだ。あと、負の値は考慮してないので、必要あれば例外処理などを加えても良いだろう。

 また、プロコンのような問題では大抵「1000000 の剰余で答えなさい」のようになっていると思うが(普通に計算したらオーバフローするため)、その方法も書いておく。剰余は「余りをとる」「mod をとる」「法とする」などと表記されることもある。

●繰り返し二乗法によるべき乗計算で剰余を返す版
/**<h1>べき乗計算&剰余(繰り返し二乗法)</h1>
* <p>Math.pow() の約5倍速い。</p>
* @param x : 底
* @param n : べき指数
* @param mod : 剰余
* @return<b>long</b> : x<sup>n</sup> % mod
*/
public static final long modPow(long x, long n, final long mod) {
long sum = 1;
while (n > 0) {
if ((n & 1) == 1) { //ビットが立っていたら
sum = sum * x % mod; //x^2^k1 * x^2^k2 * x^2^k3 * ・・・
}
x = x * x % mod; //((x^2)^2)^2 ・・・
n >>= 1;
}
return sum;
}

 long は 19桁なので、9桁×9桁=18桁 なら、1000000000 の剰余で計算すれば、下9桁でオーバフローすることはない。検算したければ、BigInteger.modPow() と照合してみれば良いだろう。上の関数は同じ値になる。ちなみに実行速度は BigInteger約25倍ほど速い


(関連記事)
【Java】1000000!のような巨大な階乗計算をする [任意精度整数(多倍長整数)]
【Java】任意精度整数(多倍長整数)で演算する
【Java】プリミティブ型での階乗計算
【Java】順列の数を求める
【Java】組み合わせの数を求める
【Java】パスカルの三角形を使って組み合わせを求める


■参考になる書籍


category: Java

thread: プログラミング

janre: コンピュータ

tag: 算術関数  べき乗  アルゴリズム 
tb: 0   cm: --


プロフィール

Social

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop