【Java】数値の桁数を調べる（べき乗の桁数・べき乗のべき乗の桁を調べる）

2016/07/17 Sun [edit]

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

■10で割っていく方法
■文字列に変換する方法
■べき乗（x^k）の桁数を調べる
■べき乗のべき乗（x^{y^z}）の桁数を求める
■２つのべき乗のべき乗（x^{y^z}, a^{b^c}）の大きさを比較する
■任意精度を使う

■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));

　負の値のとき、マイナス記号 '-' を除外してカウントしているが、負の割り算は言語によって仕様が違うので、他の言語に移植するときは注意しよう(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));

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

■文字列に変換する方法

　「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());

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

■べき乗（x^k）の桁数を調べる

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

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

【問】2³⁰は何桁の数字か。log₁₀2 = 0.3010 を用いて調べよ。

【解】
log₁₀2 = 0.3010 だから、2 = 10^0.3010　　[指数への変換：log_ap = q　⇔　p = a^q]
2³⁰ = (10^0.3010)³⁰
　　= 10^0.3010×30　　[指数法則：(a^p)^q = a^p×q]
　　= 10^9.03
よって、10⁹ ＜ 2³⁰ ＜ 10¹⁰
したがって、2³⁰ は 10桁の数字である。　　[10⁹ = 1,000,000,000 (頭 1 と 0 が 9 個で 10桁)]

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

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

2³⁰ = 10^0.3010×30 = 10^{log₁₀2×30}

(2 を x、30乗を k と置くと)
x^k = 10^{log₁₀x × k}　　…　①　（←以降、この式を公式のように扱う）

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

●べき乗（x^k）の桁数を 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)することがあるので、使う際にはあらかじめ確認しておいた方が良いだろう。

■べき乗のべき乗（x^{y^z}）の桁数を求める

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

(x^{y^z} の指数部分 y^z を log10 を使って変換すると [①を参照])
y^z = 10^{log₁₀y × z}

(x^{y^z} の指数部分 y^z を k と置き、同じように変換すると [①を参照])
x^{y^z} = x^k = 10^{log₁₀x × k}

(k を元に戻すと)
x^{y^z} = x^k = 10^{log₁₀x × 10^{log₁₀y × z}}

(桁数は指数部分のことだから)
桁数 = floor(log₁₀x × 10^{log₁₀y × z}) + 1

●べき乗のべき乗（x^{y^z}）の桁数を 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

■２つのべき乗のべき乗（x^{y^z}, a^{b^c}）の大きさを比較する

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

(桁数を表す指数部分を抜き出すと)
y^z = log₁₀x × 10^{log₁₀y × z}

log₁₀x = m と置き、今までと同じように[①を参照] 10^q に変形すると、m = 10^log₁₀m ［m¹ = 10^{log₁₀m × 1}］

(m を元に戻すと)
10^log₁₀m = 10^{log₁₀(log₁₀x)} (= log₁₀x)

(y^zの式に代入して)
y^z = 10^{log₁₀(log₁₀x)} × 10^{log₁₀y × z} = 10^{log₁₀(log₁₀x) + log₁₀y × z}　[指数法則：a^p×a^q = a^p+q]

(x^{y^z}の式に戻すと)
x^{y^z} = 10^{10^{log₁₀(log₁₀x) + zlog₁₀y}}

(つまり、一番上の指数だけを比較すれば大小関係がわかる)
log₁₀(log₁₀x) + zlog₁₀y

●べき乗のべき乗（x^{y^z}）の比較をする

/**<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() を３回以上入れ子にすると負の値となってしまうので、上手く行かないようだ。式としては以下のようになる。

w^{x^{y^z}} = 10^{10^{10^{log₁₀(log₁₀(log₁₀w)) + log₁₀(log₁₀x) + zlog₁₀y}}}

(一番上の指数だけを抜き出せば)
log₁₀(log₁₀(log₁₀w)) + log₁₀(log₁₀x) + zlog₁₀y

　式は無理矢理なので、正しい書き方とかは勘弁して欲しい(笑)。級数（数列の和）っぽく書けばもっとカッコイイのかも知れないが、この書き方なら高校数学の範疇なので理解できるハズだ（無理矢理感は別として）。でもまぁ、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

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