先週末の AtCoder ABC169 B の問題で、long long 型の整数をオーバーフローさせてしまった。しかもそれに気づけずにだいぶつまずいてしまった。
B - Multiplication 2 (https://atcoder.jp/contests/abc169/tasks/abc169_b)
Ruby や Python であれば意識せず扱える部分であっただけに悔しさがある一方で、こうも思った。 Ruby に扱える整数値に上限ってあるの？
そんなものがあっては困る！というのは百も承知で、調べてみた。
Fixnum と Bignum
Fixnum と Bignum は、どちらも整数を扱うクラスで、 Ruby 2.4 で Integer クラスに統合された。 Ruby 2.4 は個人的に Ruby を触るようになってすぐのリリースだったから、当時もこの話題を耳にしたのをうっすら覚えている。
# Ruby 2.3.8
irb(main):001:0> 1.class
=> Fixnum
irb(main):002:0> (2**62).class
=> Bignum
# Ruby 2.4.1
irb(main):001:0> 1.class
=> Integer
irb(main):002:0> (2**62).class
=> Integer
Ruby 2.3 のドキュメント にはこうある。
While Fixnum values are immediate, Bignum objects are not—assignment and parameter passing work with references to objects, not the objects themselves. 1
Fixnum はオブジェクト自身が値を保持するが、 Bignum は参照を持つだけで値は保持しない、とある。もう少し詳しくみてみたい。
Bignum のとりうる値とその仕組み
続いてこんな記事を見つけた。要点も続けて書くが、元記事は十分明快に書かれているため、僕の解釈を鵜呑みにせずこちらも読んでみてほしい。
How Big is a Bignum? - Pat Shaughnessy (http://patshaughnessy.net/2014/1/9/how-big-is-a-bignum)
Ruby の Fixnum オブジェクトは最大 64-bit の領域を確保する。このうち、64桁目が sign フラグに使われるのは C/C++ と一緒。ただし1桁目も予約されていて、それは FIXNUM_FLAG というパラメータに使われている。それは次のように整理される。
- FIXNUM_FLAG=1 のとき（つまり最小桁が1のとき）そのオブジェクトは Fixnum クラスである
- FIXNUM_FLAG=0 のとき（つまり最小桁が0のとき）そのオブジェクトは Bignum クラスであり、ポインタを参照する
- ポインタの参照先には任意の個数の 32-bit 値を持つ配列がいる</li>
で、任意の長さの配列をポインタとして持てるということは、扱える値の大きさに限度はないということになる。
そしてまた、 Fixnum と Bignum はそれぞれ実装の詳細に他ならない。だからこそ、Ruby 利用者がこれらクラスの差異を意識せずに、 Integer というインターフェースだけを利用できるよう、これらはひとつに統合されたのであった。
おわりに
つまり Ruby にオーバーフローの心配はない。ヨカッタ！
そして調べているうちに週末の悔しさは成仏させられたようだ。これもヨカッタ！