Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
2
Help us understand the problem. What is going on with this article?
@scivola

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

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

何の話?

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

Math.log10(x).floor + 1

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

しかし,結論だけを知りたい方は それでいいのか? の節にどうぞ。

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

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

文字列化

Ruby の整数(Integer クラス)には,N 進法で表した数字列を生成する Integer#to_s というメソッドがある。

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

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

一方,String クラスには,長さ(文字数)を数える String#length というメソッドがある。

p "Ruby".length # => 4

これを組み合わせれば

x.to_s.length

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

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

桁ごとの数の配列を得る

Ruby には,非負整数(0 以上の整数)を N 進法で表したときの各桁の数を並べた配列を返す Integer#digits というメソッドがある。

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

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

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

これと,配列の長さを返す Array#length を使えば

x.digits.length

で桁数が得られる。

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

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

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

Math.log10(x).floor + 1

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

Math.log10 は,与えられた引数の常用対数の値を返すメソッド。

常用対数関数

y = \log_{10}x

は 10 をていとする指数関数

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$ が得られる。

切り捨てにゆか関数というものを使おう。これは,半端を数直線の左(負の無限大)に向かって切り捨てる。
今の場合,負数は出てこないから「小数部の切り捨て」と考えても差し支えない1

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

\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 のコードで書けば

Math.log10(x).floor + 1

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

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

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

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

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

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 は実は環境依存なので,精度は一概に言えないのだが,非常に多くの環境で IEEE 754 の「倍精度」というものが使われるらしい。これの場合,精度は 10 進で 15 桁くらいになるとのこと。

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

結論

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


  1. 負数の場合,-1.1.floor-2 であって,小数部を切り捨てた -1 ではないことに注意。 

2
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
2
Help us understand the problem. What is going on with this article?