桁数は Math.log10(x).floor + 1 でいいのか


この記事は Ruby を前提とするが，多くの言語で似たようなことが言えると思う。

# 何の話？

正の整数 `x` が 10 進法で何桁になるか，を求めるやり方はいくつもある。
そのうちの一つが

```r
Math.log10(x).floor + 1
```

なのだが，本当にこれで正しい答えが得られるのだろうか，という話。
数学が苦手でも，Ruby をあまり知らなくても分かるよう，なるべく丁寧に見ていく。

しかし，結論だけを知りたい方は [それでいいのか？](#%E3%81%9D%E3%82%8C%E3%81%A7%E3%81%84%E3%81%84%E3%81%AE%E3%81%8B) の節にどうぞ。

# 桁数を求めるいろいろなやり方

この節では，ローカル変数 `x` に正の整数が代入されているとする。
Ruby はメモリーなどの条件が許せばどんな大きな整数も扱うことができる。

## 文字列化

Ruby の整数（Integer クラス）には，N 進法で表した数字列を生成する [Integer#to_s](https://docs.ruby-lang.org/ja/2.7.0/method/Integer/i/inspect.html) というメソッドがある。

引数を省略すると，10 進法の数字列が得られる。

```rb
p (36 + 72).to_s # => "108"
```

一方，String クラスには，長さ（文字数）を数える [String#length](https://docs.ruby-lang.org/ja/2.7.0/method/String/i/length.html) というメソッドがある。

```rb
p "Ruby".length # => 4
```

これを組み合わせれば

```rb
x.to_s.length
```

で桁数が得られる。
極めて簡単だ。

しかし，ちょっとした不安がよぎる。桁数が知りたいだけなのに，10 万桁の整数に対し長さ 10 万の巨大文字列を作るのは，もしかして遅いのでは？
実はかなり高速なのだが，その話は置いておこう。

## 桁ごとの数の配列を得る

Ruby には，非負整数（0 以上の整数）を N 進法で表したときの各桁の数を並べた配列を返す [Integer#digits](https://docs.ruby-lang.org/ja/2.7.0/method/Integer/i/digits.html) というメソッドがある。

引数を省略すると 10 進法となる。

```rb
p 1234.digits # => [4, 3, 2, 1]
```

下の位から順に並べるので，見た目の順序は逆転している。

これと，配列の長さを返す [Array#length](https://docs.ruby-lang.org/ja/2.7.0/method/Array/i/length.html) を使えば

```rb
x.digits.length
```

で桁数が得られる。

私なぞは，素人考えで「なんとなく文字列より整数のほうが処理が速そうだから，`x.to_s.length` より速いんでは？」と思ってしまったが，そんなことはなかった。そりゃそうか。巨大な配列が作られるわけだしね。

## そして Math.log10(x).floor + 1

他にもやり方はあるが，本題の

```rb
Math.log10(x).floor + 1
```

に行こう。なぜこれで `x` の桁数が得られるのか？

[Math.log10](https://docs.ruby-lang.org/ja/2.7.0/method/Math/m/log10.html) は，与えられた引数の常用対数の値を返すメソッド。

常用対数関数

```math
y = \log_{10}x
```

は 10 を<ruby>底<rt>てい</ruby>とする指数関数

```math
x = 10^y
```

の逆関数だったね。
この指数関数は，$y$ が整数のときは意味が分かりやすいけれど，任意の実数に対しても定義されている。

$y$ が 0 以上の整数のときを見てみよう

| $y = \log_{10}x$ | $x = 10^y$ |
|--:|--:|
| $0$ | $1$ |
| $1$ | $10$ |
| $2$ | $100$ |
| $3$ | $1000$ |
| $4$ | $10000$ |

これを見れば，$y$ が 0 以上の整数のときは，$y + 1$ つまり $\log_{10}(x) + 1$ が桁数になることが分かる。

しかし，$y$ が整数になる $x$ は限られている。もっと一般の正の整数 $x$ についてはどうなるだろう？

ためしに，$x = 999$ を考えてみる。これは $1000$ よりちょっと小さい。
対数関数は単調増加（$x$ が増えれば $y$ も増える）なので，$\log_{10}999$ は $3$ よりも**ちょっと小さい**はずだ。
したがって，**切り捨て**で整数化すれば，$2$ が得られる。


切り捨てに<ruby>床<rt>ゆか</ruby>関数というものを使おう。これは，半端を数直線の左（負の無限大）に向かって切り捨てる。
今の場合，負数は出てこないから「小数部の切り捨て」と考えても差し支えない[^fl]。

[^fl]: 負数の場合，`-1.1.floor` は `-2` であって，小数部を切り捨てた `-1` ではないことに注意。

さて，数学記号では，床関数を $\lfloor a \rfloor$ のように書くらしいが，以上の考察から，$x$ が $100$ 以上 $999$ 以下であるとき，

```math
\lfloor \log_{10}x \rfloor
```

は全て $2$ であることが分かる。
つまり，こんなふうになるんである。

| $x$ | $\lfloor \log_{10}x \rfloor$ |
|--:|--:|
| $1$〜$9$ | $0$ |
| $10$〜$99$ | $1$ |
| $100$〜$999$ | $2$ |
| $1000$〜$9999$ | $3$ |
| $10000$〜$99999$ | $4$ |

だから 1 を足した $\lfloor \log_{10}x \rfloor + 1$ で桁数が得られるというわけだ。数学的には，ね。

# それでいいのか？

やっと核心に。

$\lfloor \log_{10}x \rfloor + 1$ を Ruby のコードで書けば

```rb
Math.log10(x).floor + 1
```

となるわけだが，一抹の不安がよぎる。それがこの記事の主旨であった。

というのは，`Math.log10` は Float クラスの浮動小数点演算だ。浮動小数点演算にはふつう誤差が伴う。
微妙な誤差に起因して結果の桁が狂うことはありえないのか？

どう考えればいいのだろう？

正の整数 `x` を 1，2，3，… と順に見ていって，桁が変わるのはどこか。それは，もちろん 9→10 とか 99→100 とか 999→1000 といったところだよね。
浮動小数点数演算の誤差によって誤った結果が出るとすれば，この境目のあたりだろう。
10000000 のようなのが誤って一つ少ない桁にされたり，9999999999 のようなのが誤って一つ多い桁にされたり，といったことがありそう。
このうち，1000000 のような数はもともと $10^k$ の形なので，誤差が出にくい気がする。
ならば，9 が並ぶ数で実験してみようではないか。

はい，こんなコードを書きました。

```rb
1.upto(100) do |k|
  puts "%3d %3d" % [k, Math.log10(10 ** k - 1).floor + 1]
end
```

$k$ を 1 から 100 まで変えて，$10^k - 1$（つまり 9 を $k$ 個並べた数）の桁を計算させる。これを $k$ と並べて表示させる。数学的には一致するハズなので，同じ数が並んでいるかどうかを見る。

結果は以下の通り

```
  1   1
  2   2
  3   3
  4   4
  5   5
  6   6
  7   7
  8   8
  9   9
 10  10
 11  11
 12  12
 13  13
 14  14
 15  16
 16  17
 17  18
 18  19
 19  20
 20  21
 21  22
 22  23
 23  24
 24  25
 25  26
 26  27
 27  28
 28  29
 29  30
 30  31
 31  32
 32  33
 33  34
 34  35
 35  36
 36  37
 37  38
 38  39
 39  40
 40  41
 41  42
 42  43
 43  44
 44  45
 45  46
 46  47
 47  48
 48  49
 49  50
 50  51
 51  52
 52  53
 53  54
 54  55
 55  56
 56  57
 57  58
 58  59
 59  60
 60  61
 61  62
 62  63
 63  64
 64  65
 65  66
 66  67
 67  68
 68  69
 69  70
 70  71
 71  72
 72  73
 73  74
 74  75
 75  76
 76  77
 77  78
 78  79
 79  80
 80  81
 81  82
 82  83
 83  84
 84  85
 85  86
 86  87
 87  88
 88  89
 89  90
 90  91
 91  92
 92  93
 93  94
 94  95
 95  96
 96  97
 97  98
 98  99
 99 100
100 101
```

途中からずれている。抜粋するとココ。

```
 14  14
 15  16
```

$10^{14} - 1$ までは正しく計算できているが，$10^{15} - 1$ では案の定，正しい答えより一つ大きい数になってしまっている。


ここでふと思い当たることがあった。「浮動小数点数の精度は 10 進にして 15 桁程度」という話。
Ruby の [Float](https://docs.ruby-lang.org/ja/latest/class/Float.html) は実は環境依存なので，精度は一概に言えないのだが，非常に多くの環境で IEEE 754 の「倍精度」というものが使われるらしい。これの場合，精度は 10 進で 15 桁くらいになるとのこと。

だから，9 を 15 個並べた整数で `Math.log10(x).floor + 1` の結果が正しい桁数にならなかった，というのはいかにもありそうな話なわけだ。

## 結論

小さな整数に対しては `Math.log10(x).floor + 1` でよいが，大きな整数では誤差が生じる。