【プログラミング】でっかい整数を扱おう！【Decimalのススメ】
スポンサードリンク
こんにちは。ふぁんたです。
早速ですが、皆さん。
大きな数をプログラム上で扱うときは、どんな型を使っていますか？
int？大きいですよね。42億ぐらいまでですね。
だいたいの計算はこれで済んじゃいますね。
時々足りなくなることもありますけど。
longもいいですよね。define int longとして、intなんかには頼りたくないよと思う人も居るでしょう。
これだとだいたい922京ぐらいまでは扱うことができます。2の63乗ぐらいです。
さて、プログラミングコンテストでこんな問題が出ました。
その中に、気になる記述が。
「この問題の制約下で答えは 63乗 未満であることが証明できます。」
確かに、答えは2の63乗未満でした。
しかし、計算の順番を間違えると、計算途中で2の63乗を超える数字が出現し、longの長さで足りなくなってしまうことが起こります（起こりました）。
これを回避するために、もっと大きい範囲の数字を扱える必要があります。
今日はそんな、double型とDecimal型のお話をします。
というか、主にDecimalを推します。
doubleでいいじゃん
「double型だったら、確か大きな数字が扱えるよ」
そうなんです。実はlongよりdoubleの方が、圧倒的に扱える桁数がでかいんです。
10の308乗(1の後に0が308回続く) までの数字を格納しておくことができるんです。
さっきのlongが1000京=10の19乗なので、比べ物になりません。圧倒的です。
いわゆる「無量大数」でも10の68乗なので、文字通り「桁違い」です。
でも、実は、doubleには2つの落とし穴があるんです。
doubleの落とし穴① 正確な値を保存する点で、弱い
10の308乗までの数字を格納しておくことができる！という話がありましたが、実は、正確ではありません。
だいたい10進数で15桁ぐらい × 10の(-321乗から308乗ぐらいまで) を保持するのに使われます。
この「だいたい10進数で15桁ぐらい」が曲者なのです。
例えば、1を20個続けた数を考えましょう。20桁全部が1の大きい数字です。
これを、double型では正確に保持することができません。
「10進数で15桁ぐらい」が入るところに、1が20桁続いた部分は入らないので、切り捨てが行われます。
double側としては「大体1が15桁ぐらい続いて、それが10進数で20桁になるようにする数なんだろ」ぐらいの認識でいます。
よって、正確な数字になりません。
(longの桁はギリギリ全部入る)
doubleの落とし穴② 正確な小数に弱い
我々の世界は10進数。コンピューターは2進数です。小数だと、ここの変換に問題が生じてきます。
例えば、0.1という数字。
我々10進数の世界では0.1と書きますが、実は2進数では、ぴったりこの数字の表現ができません。
実験をします。
Googleのスプレッドシートを開き、A1からA10000までに「0.1」を入れます。
A10001に「=SUM(A1:A10000)」を入れます。（0.1を10000回足す）
本当に、0.1がぴったり0.1なら、A10001は「1000」になるはずです。
しかし、結果の有効桁数をどんどん増やしていくと、ピッタリ1000にならないことがわかります。
「正確に小数を保存して計算したい場合」（例：Panasonic 2019-C : Sqrt Inequality）なんかでは、doubleは使わないほうがいいでしょう。
Decimalを推させてください
そこで、10進数の数字の部分を「10進数のまま保存する」、つまり誤差なしで計算できる型が欲しくなりませんか。
それが、Decimal型なんです。
doubleのさらに倍のメモリ容量を食う上、10の28乗までしか取り扱えないという、さっきの308乗に比べてかなり見劣りしますが、
整数だろうが小数(10の-28乗まで)だろうが、
正確に！誤差なく！格納・計算することができます。
10の28乗は2の90乗よりも大きいので、longでちょっとオーバーフローしそうなときとかにもしっかり使えます。
小数にも強いので、さっきのPanasonic 2019-C : Sqrt Inequalityなんかも普通に(二乗して移項しないで）解けてしまいます。
（このdecimal形式については、実は自分の卒論のテーマにおおきく関わってたことなので、結構語りたいんですけどうるさいだけなんで黙ります）
Bigintegerとかいう型もあるんですが、足したり掛けたりに特別な手続きが必要だったりでいちいち覚えてられません。decimalは+-*/普通に使える。
28桁までと少ないけれど、整数がlongよりも広く、小数がdoubleよりも圧倒的に正確なんです。
Decimal流行れ！！！！
スポンサードリンク