Excel の限界

こんにちは世界。工学系VTuber の足立千鳥です。
今日は計算機（パソコン）が数値をどう扱っているのか、についてチラッとお話します。

最近、構造生物Vtuber の生命燐ちゃんが夜中にゼミを開いています。あたしは化学がわからないので「へぇ～」と思いながら聞いているのですが、今日は

「Excel で組み合わせを計算したんだけど、1000個よりたくさんから選ぶ組み合わせを計算しようとしたら数が大きすぎてできなかった」

という話題が出ました。この理由なら説明できそうなので頑張ってみます。

この先のお話を短くまとめると、
・Excel の１マスは64ビットの倍精度浮動小数点数で、最大値は10の308乗くらい
・階乗の大きさを見積もるスターリングの公式を使うと、1030個から515個を選ぶ組み合わせが 10の308乗くらいの値になる
・それ以上の大きさの組み合わせを求めようとすると Excel の限界を超えちゃうのでエラーになる
です。

難しそうですか？

大丈夫です！10の308乗（１のうしろに０が308個並ぶ）なんて数値はほとんどの人は滅多に使わないので「ふ～ん」と斜め読みしましょう！

パソコンの中の数値

皆さんはパソコンがどうやって数値を記憶しているかご存知ですか？

「知ってるよ、二進数でしょ」

そうです！
10 は 2,
11111111 は 255,
10000000000 は 1024,
ってやつです！

でもこれ全部「整数」ですよね？ Excel は 0.2 とか 3.14 みたいな 実数が使えますよね。あの Excel の１マスの中で実数はどうやって表現されているのでしょうか？

次のような数値の表示方法を見たことがありますか？

1230000 と書けばいいものをわざわざ 123かける10の4乗 と表示しています。有効数字というものを習ったことがある方はピンと来たかもしれません。実はパソコンはこの表示法を使って実数を表しています。この方法で 0.00123 という数値はどう表せるでしょうか？

  123×10の－5乗 ですね。では －4.56 は？

－456かける10の－2乗 ですね。

何が言いたかったのかというと、「正と負の整数」と「"数値A" かける 10の "数値B" 乗という表示方法」が使えれば、実数が表現できるということです。パソコンはこれを二進数でやっています。

「負の数はどうやって表すの？」という疑問は当然ありますよね。これは「２の補数」という便利なものを使うのですが説明が長くなってしまうので、マイナスの棒を表す１ビットがあれば原理的には表せそうだよね、と簡単に考えてもらえると助かります。

本題に入ると、Excel の１マスは 64ビットを使って数値を記憶しています。上の例の123や456, 数値Aと言っていた部分は「仮数部」といい52ビット、10の肩に乗っていた4や－2, 数値Bと言っていた部分は「指数部」 といい11ビット、それに正負を表す符号の1ビット、で全64ビットです。C言語でいう double型、倍精度浮動小数点数と呼ばれるこの数値の表現方法のルールは IEEE754 という規格で定められています。

「仮数部」は「有効数字の細かさ」に対応していて、10進数で言えば1.000...～9.999...（ほぼ10）にあたる、1.000...～1.999...（ほぼ2）を表現しているので、実は数値の大きさ（桁）にはたいして関係していません。桁は指数部が表現しています。11ビットなので最大値は 2^(2^10) = 2^1024 です（このハット ^ という記号は肩の上に数値が乗ること、つまりべき乗を表しています）。常用対数をとると 1024 log_10 (2) ≒ 1024*0.301 ≒ 308 で、10の308乗くらいです。一応 Wikipedia を見てみると倍精度浮動小数点数の最大値は 1.7976931348623157×10^308 とのことです。この最大値を超える値は Excel のマスに入れられないということです。見出しの画像がそれで、#NUM! というエラーが出ています。

とても大きな組み合わせの数を見積もる

では、 n個から k個を選ぶ組み合わせ、の nを大きくしていったときにいつ10^308 を超えてしまうのか調べてみましょう。ここで Excel を使ってもいいですが、せっかくなので予想を立ててからにします。

n個の中から k個を選ぶ組み合わせの数、は次のような表式でしたね。

真ん中の nCk と書いている人が多いかと思いますが、一番左の括弧で書く表式もよく使われています。

さて、組み合わせには階乗が使われていますね。階乗 n! は n を大きくしていくと凄い勢いで大きくなっていきます。こいつがいるので n が1000超えたあたりで 10^308 を超えちゃうんでしょうね。

n! の n が大きい時、階乗のおおよその大きさを与えてくれる近似式があります。次の「スターリングの公式」というものです。

桁だけ見たいので常用対数をとります。

右辺は絶対値が大きい順で項を並べました。

次に、この n 未満ならどんな（n以下の）k に対しても組み合わせの数が計算できるよ（もしくは、ある k をとるとこの n 以上のときは組み合わせの数が計算できない）、ということを示すために、組み合わせの数を最も大きくする k について桁を調べて、308をはじめて超える n を見つけましょう。

組み合わせの数が最も大きくなるのは、 k が n の半分くらいのときですね。なので k = n/2 のときの nCk を考えます。n/2 が 割り切れなかったら k が整数じゃなくて気持ち悪い～という方は床関数や天井関数を使ってください。

常用対数をとって桁を見ることにしましょう。

これの右辺にスターリングの公式を使ってやれば、桁数がわかります。長くなるので式は省略しますが、計算結果は、
n = 1028 のとき 307.855
n = 1029 のとき 308.156
n = 1030 のとき 308.456
ということで、n = 1030 あたりで組み合わせの計算結果は Excel の１マスの限界を超えてしまいそうです。

組み合わせがエラーになってしまうのは n = いくつのときでしょうか？実際に Excel で COMBIN という関数を使って確かめてみます。

確かにこのあたりは 10の308乗くらいになり、そして n = 1030 でとうとう #NUM! のエラーが出ました。

締め

パソコンの数値表現、大きな組み合わせの概算、について話しました。予想通りの結果になって面白かったですね。

ただ、64ビットのこんな表し方じゃ実数どころか有理数の一部しか表せないじゃん、とか、nCk の結果が10^308くらいになる前に分子の n! はとっくに10^308を超えるのにどうやって計算してるの？とか、新たな疑問が出てきますよね。

前者はその通りでコンピュータの計算は誤差だらけです。電卓で１÷３をやったあと×３しても１に戻らないとかよくあることです。

後者はあたしもわからないです。真面目に n! と k! (n-k)! をそれぞれ計算して割ってるわけじゃなくてもっと賢い（または手を抜いた）計算をしてるのかな、とか、一時的に64ビットよりも long な例えば128ビットとか使って計算してるのかな、とか色々考えますけど、まあいっか！って感じです。

なんでだろう？という疑問を突き詰めて考えるのもとっても面白いけど、突き詰め過ぎずに考えるのも楽しいです。そんな感じで気楽に気軽に、色々学んでいきたいです。