ABC169-C問題"Multiplication 3"を通して浮動点小数の扱いを勉強する(とちゅう)
未分類
仕事の資料が作り終わらず、やる気が起きず寝ていたらABC169に参加しそびれたのですが、どうやらB問題とC問題で誤答(WA)が連発したようです。
特にC問題では、小数(浮動点小数)を型変換する際に生じる誤差についてキチンと理解していないと間違うというトリッキーな問題でした。
私は翌日起きてからこの問題を解こうとしたら全く解けず絶望したのですが、教育的な問題だと思い、この機会に「何が起きているのか？」を勉強してみることにしました。
また、私含む初心者にとって公式解説の行間はあまりにも空きすぎていると思うので、復習がてらゆっくり理解していくことを目的として、メモを書いていきます。
実は、3月ごろに開催されたコンテストのこの問題も、小数の扱いを理解しないと危ない問題だったのですが、嘘解法でたまたまACしてしまったためあんまり復習していませんでした。反省。こちらも一緒に理解を進めたので、いつか記事にしたいとは思っています。
先に言及しておくと、ABC169-C問題に関しては、結論からいえばpythonなどで有効桁数を非常に大きくした固定小数点を使えば一発で解決します。
そうなると固定小数点で全部やればいいので、浮動小数点について勉強する意味ある？となりそうですが、いろいろな事情からそういうわけにいかないようで、現実様々なところで浮動小数点型が使われているため、やっぱりちゃんと学んだほうがよさそうです。
素人が勉強のために書いているメモなので、誤りを含む可能性が大いにあります。親切に指摘して頂けると大変喜びます。
叩いたり晒し上げたりする/されるよりは、共に学べると良いなと思っています。
■0.999999... = 1?
全然別の話題からスタートしますが、
中学生が循環小数を習ったときにこんな疑問が出てくるはずです。
「1=(1/3) * 3 = 0.333333.... * 3 = 0.999999...」は正しい式なのか？
私含めて多くの人が疑問だったものだと思います。
教えてgoo!にも旧石器時代に質問された形跡があり、古くから共通の疑問だったと思われます。
結論から言うと0.999999... = 1は正しく、ε-N論法のようにして解釈することが出来ます。
(素人なので、説明に誤りがあれば教えてください)
初項a[1] = 0.9
a[n+1] = a[n] + 0.9 * (1/10)^n (n>=1)
となる数列を用意すると、これは
a[1] = 0.9, a[2] = 0.99, a[3] = 0.999, ...
となる単調増加の数列となりますが、
項数を無限に大きくしていくと、その項は0.999999...と同じとみなせます。
ここで、任意の小さい正の数εを用意することを考えます。このとき、
|1 - a[N]| < ε
となるNが絶対見つかるかどうか？を考え、見つかれば、a[N]の極限は1であると解釈できます。
この場合では、実際にどんなεを持ってきても、この不等式を満たすNを取ってくることができます。
例えば0.0000000003742という数を用意したときは、a[10]を用意すれば式を満たします。(もちろんそれ以降の項でもいいです)
もっと大胆にいえば、どんなε(<1)が用意されたとしても、N=floor(1/ε)とすれば、オーバーキルで絶対上記の不等式を満たします。
このことから、a[n]は1に収束する数列であり、項数を無限大に発散させた0.999999... は1と同じである解釈することが出来ます。
この事は直感的でなく、しばらくは納得できないかもしれませんが、これは9が無限に続くから言えることであって、
確実なことは、0.999999...と無限に続かずに、途中で切った場合は絶対に1にならないということです。
「0.999999...は1にならないでしょ」という感覚は、脳内で勝手にどこかの桁で打ち切ってしまうことから出てくる考えだと思われます。
最初の例で0.333333333 * 3と9桁で切ってしまった場合は答えは0.999999999となり、0.000000001の誤差が生じます。
このように、循環小数を人の都合で勝手な桁数で切ると、それを用いた計算結果には誤差が生じることになります。
■2進数の循環小数
さて、循環小数は10進数の世界でなく2進数の世界にもあります。
2進数の世界では、10進数で小数部分が (0or1) * 2^(-1) + (0or1) * 2^(-2) + (0or1) * 2^(-3) + ...と表せない限り循環小数になります。例えば10進数でいう0.1は2進数に直すと
0.0001 1001 1001 1001 1001 1001 1001 1001 1001...と続くようです。
しかしコンピュータサイエンスの世界では、実際のメモリに値を格納しないといけないので、有限の数のメモリに小数を保存しないといけません。そのため、格納できる小数の桁数(2進数の桁数)が決まっています。
例えばfloat型では23bitです*。つまり、循環小数が24桁以上続く場合、それ以降の情報は落とさないといけません。
循環小数を人の都合で勝手な桁数で切ると、それを用いた計算結果には誤差が生じることから、これを使った計算には誤差が発生します。
(循環小数でなかったとしても、2進数で表したときに24桁以上になるような数を扱う際には、同様のことが発生します)
*
float型をはじめ多くの浮動小数点型では、全ての小数を
1.xx * 2^(yy)
の形にしてxxの部分とyyの部分を記憶することを行います。
ここで、整数部分は絶対に1になるように変形するとルールが決められているようなので(ケチ表現というらしい)、この1をメモリに保存する必要はなく、この1を除いた23bitを保存します。そのため有効数字は24桁あるようです(2進数の24桁です)
たとえば、10進数でいう0.275は2進数で0.011と表されますが、これを(10進数では2.75*10^1と表すのと同様にすることで)1.1*2^(-2)のように表したとき、実際に整数部分の1は情報として持つ必要がないということです。この場合小数第1位の"1"と指数の肩の"2"さえ覚えておけば、1.1*2^(-2)のデータを格納することが出来ます。
環境・定義によってあらわせるbitの数は異なるようですが、今回は下記wikipediaのリンク先にある"IEEE 754 での単精度浮動小数点数の形式: binary32"の環境を前提とします。私の環境でもfloatを使うとこうなるので。他の環境のことは知りません
floatの表し方のフォーマットはwikipediaなどを参照
さて、例えば0.1(10進数)をfloatに格納することを考えます。
c++でいえば、float val = 0.1; としたときの動作です。
(実際にやった例)
前述の通り0.1(10進数)を2進数に変換すると
0.1 = 0. 0001 1001 1001 1001 1001 1001 100(1 1001 1001 ...)
ですが、動作の定義上、実際には最初の1が出たbit(青文字)の次のbitから23bitぶん(最初の1は保存しなくてよい)、floatデータへ格納されます。
この時点では
1.1001 1001 1001 1001 1001 100 * 2^(-4)
のように保存されているはずです。
次に、カッコ内の部分はfloatには格納しきれないbitです。この部分に関しては切り捨てや切り上げなどの丸め処理がなされます。
恐らく言語や環境によって違うのでしょうが、私の環境では赤文字のbit(格納できないbitのうち一番大きな桁)を見て、0なら切り捨て、1なら切り上げ(切り上げたら1個左のbitを1増やす)の処理がなされます。(いわゆる0捨1入)
1.1001 1001 1001 1001 1001 101 * 2^(-4)
これで処理は終了です。実際には2進数のこの値がメモリに格納されています。
見てきてわかるように、カッコ内を切り捨てるかわりに、その左のbitを1増やしてしまうので、トータルでみると真の数に比べて格納した数は大きくなってしまっています。
実際に0.1をfloatに格納し、それを10進数に直すと実際にやった例のようになります。ぴったり0.1ではない、0.1より少し大きな数が出力されているのが分かります。
また、ここでは無理やり小数第35位まで表示させていますが、小さな数を表すbit(さっきの説明でいうとカッコの中にあったbit)は全て丸め処理をされて0になっているので、途中の桁からは全て0が出力されるのが分かります。
さて、ここで出てきた数字0.100000001490116119384765625と、真の数0.1との差の絶対値が誤差です。
今回は切り上げの場合を考えましたが、切り捨ての場合も同様に考えることが出来、この場合は真の値より小さい値が出ることになります。
■ 丸め処理をした時の誤差はどのくらい？
いろんな数をfloatに格納した場合、相対誤差の大きさは最大どのくらいでしょうか？
1.xx * 2^(-yy) のフォーマットで表したとき、仮数部分(1.xxの部分)の2^(-24)桁(小数第24位)以降の情報が無くなりますが、
たとえば真の数の仮数部分が
1.0000 0000 0000 0000 0000 0001
と表される場合、これに切り上げ処理を行うと
1.0000 0000 0000 0000 0000 001(0)
となります。(カッコ内はfloatのbitに格納されない)
このようなとき、つまり切り上げ処理を行った仮数部から真の数の仮数部を引いて
0.0000 0000 0000 0000 0000 0001
となるときに相対誤差は最大となります。大きさは2^(-24)です。
切り捨て処理をしたときの相対誤差の最大も同じように考えることが出来、最大2^(-24)の誤差が生じえます。
普通に小数を計算するときは、それがイチイチ切り捨てられるか切り上げられるかが分からないので(普通はそう)、±2^(-24)の誤差を認めて計算をしないといけないと理解できます。
言い換えると、
任意の数Fをfloatに入れたとき、floatに入れた値は
F*(1-2^(-24)) から F*(1+2^(-24))の値のどれかを取る
といってもいいと思います。
2^(-24)は6*10^(-8)程度の値であり、
「float型では有効数字は7桁程度」というのは恐らくここからくる話でしょう。
逆に、
floatに入っている数がF'のとき、
真の数は大体
F'*(1-2^(-24))からF'*(1+2^(-24))の間くらいにある
と言ってもいいような気はします。正確ではないとは思いますが。
以上が、floatに格納した際の誤差についての理解です。
さて、ここまではずっとfloatの例をずっと続けてきましたが、
doubleでは仮数部が52bitのためケチ表現を加え、2進数で53桁の有効数字を持ちます。
同様の議論をすることで相対誤差の最大は2^(-53)≒1.1×10^(-16)。
c++かつgccの場合(AtCoderのc++はそうです)、long doubleを使うと仮数部64bitが使用可能のようです。
このlong doubleにはどうやらケチ表現は使われないようなので、有効数字は65桁ではなく64桁(これも2進数)です。
これも同様に考えることで相対誤差の最大は2^(-64)≒5.4×10^(-20)です。
■ABC169 C問題の2つのトラップ
やっと本題ですが、この問題には小数の扱いに関して2段階のトラップがあります。
1つ目はfloat,doubleを使うことによる有効桁数の不足で、
2つ目は小数を整数型へキャストする際に生じる切り捨てによって起こる誤差です。
どちらも本質的には「長く続く小数(循環小数に限らない)を勝手に有限のbitしか保存できないメモリに入れることで起こる誤差」から来るものだと(私は)理解していますが。
■ABC169 C問題 トラップ1 float,doubleを使うことによる有効桁数の不足
C問題では0以上10^15以下の整数A(有効数字は最大15桁)と0以上10未満の小数B(有効数字は最大3桁)を掛け算します。
掛け算した結果、有効数字は最大18桁となります。
例えば999 9900 0000 0001*9.99を考えましょう(ちなみにこれはテストケースのhand_01と同一です)。
この結果は正確には9989 9001 0000 0009.99=9.9899 0010 0000 0099 9*10^15です。
(つまり、このテストケースでは9989900100000009と出力しなくてはなりません)。
仮に上記の計算が正確に出来たとしましょう。(ナイーブに実装するだけでは実際には正確に行うことが出来ません。後で言及します)
この正確な計算結果9.9899 0010 0000 0099 9*10^15をdoubleに格納することを考えます。
上述の議論から、doubleに格納した時点で1.1*10^(-16)程度の相対誤差が生じるので、
だいたい9.99*10^15*1.1*10^(-16)≒1.1の絶対誤差が発生しうることになります。
積の整数部分をこたえなくてはいけない問題なのに1程度の絶対誤差が発生するということは、
誤った答えが出る可能性が大いにあると理解できます。
ちなみに、実際に1程度の誤差が出ることが確かめられます(1行目の結果を参照。下3ケタが099ではなく100となってしまっています)。
1.1*10^(-16)の相対誤差が生じうるdoubleでさえこの結果なので、
6*10^(-8)程度の相対誤差が生じうるfloatでは論外の結果が出てくることは想像できます。
上記のリンクの出力2行目はfloatに9.9899 0010 0000 0099 9*10^15を格納した結果です。
さらに実はそれ以前の問題があって、
999 9900 0000 0001*9.99
は、9.99をdoubleに格納して計算しようとする時点で正確に計算することは出来ていません。
9.99をdoubleに格納するときも誤差が発生するからです。
よって、例えば
としようものなら、2段階で誤差が発生していることになります。(今まで説明していたのは2番目の誤差のこと)
もっと精度の高い浮動小数点型(long doubleなど)を使う事ができれば2つ目の誤差は回避できそうですが、
1つ目の誤差は有限精度の浮動小数点型をそのまま使うだけでは、どんな精度のものを使っても解決することができません。
(long doubleを使っただけの例)
上記のコードでWAを出しているケースの中身は
A=776013196293085, B=2.60 (after_contest_01)
です。
本来の計算結果(積)は2017 6343 1036 2021となり、整数になるはずです。
しかし、Bを浮動小数点型に格納すると、切り捨てまたは切り上げが起こり2.60より少しだけ異なる値が保存されます。
(2.6 = 2.5 + 0.1と考えれば、2.5は2進数の有限小数で表せ、かつ0.1は上記の例があるので分かりやすいでしょうか。)
切り上げで保存してくれればまだ良いのですが、切り捨てたときが最も悪さをするケースです。
正確に2.6と保存してほしいところを2.6よりちょっと小さい数を保存してしまうことになり、
正確には積は2017 6343 1036 2021となるところが、2017 6343 1036 2021よりちょっと小さい数(+誤差)が結果として出てきます。そして小数点以下を切り捨てると、下2桁が21ではなく20となってしまう、ということです。
結局のところ、浮動小数点型を使わないで計算する必要がありそうです。
出来る方法としては、安全にBを整数に変換して、整数の掛け算として処理するか、
任意精度で計算できるdecimal型(pythonなど)を使って、正確にA*Bを計算する方法がありそうです。
前者の方法をメインに考えますが、「安全にBを整数に変換する」ためにもう少し考える必要があり、ここが2番目のトラップです。
後者の方法は全く別物なので、あとから補足だけします。
((20200624 0:26 ここまで。)
■ABC169 C問題 トラップ2 小数を整数型にキャストすることによる誤差
特にC問題では、小数(浮動点小数)を型変換する際に生じる誤差についてキチンと理解していないと間違うというトリッキーな問題でした。
私は翌日起きてからこの問題を解こうとしたら全く解けず絶望したのですが、教育的な問題だと思い、この機会に「何が起きているのか？」を勉強してみることにしました。
また、私含む初心者にとって公式解説の行間はあまりにも空きすぎていると思うので、復習がてらゆっくり理解していくことを目的として、メモを書いていきます。
実は、3月ごろに開催されたコンテストのこの問題も、小数の扱いを理解しないと危ない問題だったのですが、嘘解法でたまたまACしてしまったためあんまり復習していませんでした。反省。こちらも一緒に理解を進めたので、いつか記事にしたいとは思っています。
先に言及しておくと、ABC169-C問題に関しては、結論からいえばpythonなどで有効桁数を非常に大きくした固定小数点を使えば一発で解決します。
そうなると固定小数点で全部やればいいので、浮動小数点について勉強する意味ある？となりそうですが、いろいろな事情からそういうわけにいかないようで、現実様々なところで浮動小数点型が使われているため、やっぱりちゃんと学んだほうがよさそうです。
素人が勉強のために書いているメモなので、誤りを含む可能性が大いにあります。親切に指摘して頂けると大変喜びます。
叩いたり晒し上げたりする/されるよりは、共に学べると良いなと思っています。
■0.999999... = 1?
全然別の話題からスタートしますが、
中学生が循環小数を習ったときにこんな疑問が出てくるはずです。
「1=(1/3) * 3 = 0.333333.... * 3 = 0.999999...」は正しい式なのか？
私含めて多くの人が疑問だったものだと思います。
教えてgoo!にも旧石器時代に質問された形跡があり、古くから共通の疑問だったと思われます。
結論から言うと0.999999... = 1は正しく、ε-N論法のようにして解釈することが出来ます。
(素人なので、説明に誤りがあれば教えてください)
初項a[1] = 0.9
a[n+1] = a[n] + 0.9 * (1/10)^n (n>=1)
となる数列を用意すると、これは
a[1] = 0.9, a[2] = 0.99, a[3] = 0.999, ...
となる単調増加の数列となりますが、
項数を無限に大きくしていくと、その項は0.999999...と同じとみなせます。
ここで、任意の小さい正の数εを用意することを考えます。このとき、
|1 - a[N]| < ε
となるNが絶対見つかるかどうか？を考え、見つかれば、a[N]の極限は1であると解釈できます。
この場合では、実際にどんなεを持ってきても、この不等式を満たすNを取ってくることができます。
例えば0.0000000003742という数を用意したときは、a[10]を用意すれば式を満たします。(もちろんそれ以降の項でもいいです)
もっと大胆にいえば、どんなε(<1)が用意されたとしても、N=floor(1/ε)とすれば、オーバーキルで絶対上記の不等式を満たします。
このことから、a[n]は1に収束する数列であり、項数を無限大に発散させた0.999999... は1と同じである解釈することが出来ます。
この事は直感的でなく、しばらくは納得できないかもしれませんが、これは9が無限に続くから言えることであって、
確実なことは、0.999999...と無限に続かずに、途中で切った場合は絶対に1にならないということです。
「0.999999...は1にならないでしょ」という感覚は、脳内で勝手にどこかの桁で打ち切ってしまうことから出てくる考えだと思われます。
最初の例で0.333333333 * 3と9桁で切ってしまった場合は答えは0.999999999となり、0.000000001の誤差が生じます。
このように、循環小数を人の都合で勝手な桁数で切ると、それを用いた計算結果には誤差が生じることになります。
■2進数の循環小数
さて、循環小数は10進数の世界でなく2進数の世界にもあります。
2進数の世界では、10進数で小数部分が (0or1) * 2^(-1) + (0or1) * 2^(-2) + (0or1) * 2^(-3) + ...と表せない限り循環小数になります。例えば10進数でいう0.1は2進数に直すと
0.0001 1001 1001 1001 1001 1001 1001 1001 1001...と続くようです。
しかしコンピュータサイエンスの世界では、実際のメモリに値を格納しないといけないので、有限の数のメモリに小数を保存しないといけません。そのため、格納できる小数の桁数(2進数の桁数)が決まっています。
例えばfloat型では23bitです*。つまり、循環小数が24桁以上続く場合、それ以降の情報は落とさないといけません。
循環小数を人の都合で勝手な桁数で切ると、それを用いた計算結果には誤差が生じることから、これを使った計算には誤差が発生します。
(循環小数でなかったとしても、2進数で表したときに24桁以上になるような数を扱う際には、同様のことが発生します)
*
float型をはじめ多くの浮動小数点型では、全ての小数を
1.xx * 2^(yy)
の形にしてxxの部分とyyの部分を記憶することを行います。
ここで、整数部分は絶対に1になるように変形するとルールが決められているようなので(ケチ表現というらしい)、この1をメモリに保存する必要はなく、この1を除いた23bitを保存します。そのため有効数字は24桁あるようです(2進数の24桁です)
たとえば、10進数でいう0.275は2進数で0.011と表されますが、これを(10進数では2.75*10^1と表すのと同様にすることで)1.1*2^(-2)のように表したとき、実際に整数部分の1は情報として持つ必要がないということです。この場合小数第1位の"1"と指数の肩の"2"さえ覚えておけば、1.1*2^(-2)のデータを格納することが出来ます。
環境・定義によってあらわせるbitの数は異なるようですが、今回は下記wikipediaのリンク先にある"IEEE 754 での単精度浮動小数点数の形式: binary32"の環境を前提とします。私の環境でもfloatを使うとこうなるので。他の環境のことは知りません
floatの表し方のフォーマットはwikipediaなどを参照
さて、例えば0.1(10進数)をfloatに格納することを考えます。
c++でいえば、float val = 0.1; としたときの動作です。
(実際にやった例)
前述の通り0.1(10進数)を2進数に変換すると
0.1 = 0. 0001 1001 1001 1001 1001 1001 100(1 1001 1001 ...)
ですが、動作の定義上、実際には最初の1が出たbit(青文字)の次のbitから23bitぶん(最初の1は保存しなくてよい)、floatデータへ格納されます。
この時点では
1.1001 1001 1001 1001 1001 100 * 2^(-4)
のように保存されているはずです。
次に、カッコ内の部分はfloatには格納しきれないbitです。この部分に関しては切り捨てや切り上げなどの丸め処理がなされます。
恐らく言語や環境によって違うのでしょうが、私の環境では赤文字のbit(格納できないbitのうち一番大きな桁)を見て、0なら切り捨て、1なら切り上げ(切り上げたら1個左のbitを1増やす)の処理がなされます。(いわゆる0捨1入)
1.1001 1001 1001 1001 1001 101 * 2^(-4)
これで処理は終了です。実際には2進数のこの値がメモリに格納されています。
見てきてわかるように、カッコ内を切り捨てるかわりに、その左のbitを1増やしてしまうので、トータルでみると真の数に比べて格納した数は大きくなってしまっています。
実際に0.1をfloatに格納し、それを10進数に直すと実際にやった例のようになります。ぴったり0.1ではない、0.1より少し大きな数が出力されているのが分かります。
また、ここでは無理やり小数第35位まで表示させていますが、小さな数を表すbit(さっきの説明でいうとカッコの中にあったbit)は全て丸め処理をされて0になっているので、途中の桁からは全て0が出力されるのが分かります。
さて、ここで出てきた数字0.100000001490116119384765625と、真の数0.1との差の絶対値が誤差です。
今回は切り上げの場合を考えましたが、切り捨ての場合も同様に考えることが出来、この場合は真の値より小さい値が出ることになります。
■ 丸め処理をした時の誤差はどのくらい？
いろんな数をfloatに格納した場合、相対誤差の大きさは最大どのくらいでしょうか？
1.xx * 2^(-yy) のフォーマットで表したとき、仮数部分(1.xxの部分)の2^(-24)桁(小数第24位)以降の情報が無くなりますが、
たとえば真の数の仮数部分が
1.0000 0000 0000 0000 0000 0001
と表される場合、これに切り上げ処理を行うと
1.0000 0000 0000 0000 0000 001(0)
となります。(カッコ内はfloatのbitに格納されない)
このようなとき、つまり切り上げ処理を行った仮数部から真の数の仮数部を引いて
0.0000 0000 0000 0000 0000 0001
となるときに相対誤差は最大となります。大きさは2^(-24)です。
切り捨て処理をしたときの相対誤差の最大も同じように考えることが出来、最大2^(-24)の誤差が生じえます。
普通に小数を計算するときは、それがイチイチ切り捨てられるか切り上げられるかが分からないので(普通はそう)、±2^(-24)の誤差を認めて計算をしないといけないと理解できます。
言い換えると、
任意の数Fをfloatに入れたとき、floatに入れた値は
F*(1-2^(-24)) から F*(1+2^(-24))の値のどれかを取る
といってもいいと思います。
2^(-24)は6*10^(-8)程度の値であり、
「float型では有効数字は7桁程度」というのは恐らくここからくる話でしょう。
逆に、
floatに入っている数がF'のとき、
真の数は大体
F'*(1-2^(-24))からF'*(1+2^(-24))の間くらいにある
と言ってもいいような気はします。正確ではないとは思いますが。
以上が、floatに格納した際の誤差についての理解です。
さて、ここまではずっとfloatの例をずっと続けてきましたが、
doubleでは仮数部が52bitのためケチ表現を加え、2進数で53桁の有効数字を持ちます。
同様の議論をすることで相対誤差の最大は2^(-53)≒1.1×10^(-16)。
c++かつgccの場合(AtCoderのc++はそうです)、long doubleを使うと仮数部64bitが使用可能のようです。
このlong doubleにはどうやらケチ表現は使われないようなので、有効数字は65桁ではなく64桁(これも2進数)です。
これも同様に考えることで相対誤差の最大は2^(-64)≒5.4×10^(-20)です。
■ABC169 C問題の2つのトラップ
やっと本題ですが、この問題には小数の扱いに関して2段階のトラップがあります。
1つ目はfloat,doubleを使うことによる有効桁数の不足で、
2つ目は小数を整数型へキャストする際に生じる切り捨てによって起こる誤差です。
どちらも本質的には「長く続く小数(循環小数に限らない)を勝手に有限のbitしか保存できないメモリに入れることで起こる誤差」から来るものだと(私は)理解していますが。
■ABC169 C問題 トラップ1 float,doubleを使うことによる有効桁数の不足
C問題では0以上10^15以下の整数A(有効数字は最大15桁)と0以上10未満の小数B(有効数字は最大3桁)を掛け算します。
掛け算した結果、有効数字は最大18桁となります。
例えば999 9900 0000 0001*9.99を考えましょう(ちなみにこれはテストケースのhand_01と同一です)。
この結果は正確には9989 9001 0000 0009.99=9.9899 0010 0000 0099 9*10^15です。
(つまり、このテストケースでは9989900100000009と出力しなくてはなりません)。
仮に上記の計算が正確に出来たとしましょう。(ナイーブに実装するだけでは実際には正確に行うことが出来ません。後で言及します)
この正確な計算結果9.9899 0010 0000 0099 9*10^15をdoubleに格納することを考えます。
上述の議論から、doubleに格納した時点で1.1*10^(-16)程度の相対誤差が生じるので、
だいたい9.99*10^15*1.1*10^(-16)≒1.1の絶対誤差が発生しうることになります。
積の整数部分をこたえなくてはいけない問題なのに1程度の絶対誤差が発生するということは、
誤った答えが出る可能性が大いにあると理解できます。
ちなみに、実際に1程度の誤差が出ることが確かめられます(1行目の結果を参照。下3ケタが099ではなく100となってしまっています)。
1.1*10^(-16)の相対誤差が生じうるdoubleでさえこの結果なので、
6*10^(-8)程度の相対誤差が生じうるfloatでは論外の結果が出てくることは想像できます。
上記のリンクの出力2行目はfloatに9.9899 0010 0000 0099 9*10^15を格納した結果です。
さらに実はそれ以前の問題があって、
999 9900 0000 0001*9.99
は、9.99をdoubleに格納して計算しようとする時点で正確に計算することは出来ていません。
9.99をdoubleに格納するときも誤差が発生するからです。
よって、例えば
long a = 999990000000001;
double b = 9.99; //1つ目
cout << (long)(a*b); //2つ目
としようものなら、2段階で誤差が発生していることになります。(今まで説明していたのは2番目の誤差のこと)
もっと精度の高い浮動小数点型(long doubleなど)を使う事ができれば2つ目の誤差は回避できそうですが、
1つ目の誤差は有限精度の浮動小数点型をそのまま使うだけでは、どんな精度のものを使っても解決することができません。
(long doubleを使っただけの例)
上記のコードでWAを出しているケースの中身は
A=776013196293085, B=2.60 (after_contest_01)
です。
本来の計算結果(積)は2017 6343 1036 2021となり、整数になるはずです。
しかし、Bを浮動小数点型に格納すると、切り捨てまたは切り上げが起こり2.60より少しだけ異なる値が保存されます。
(2.6 = 2.5 + 0.1と考えれば、2.5は2進数の有限小数で表せ、かつ0.1は上記の例があるので分かりやすいでしょうか。)
切り上げで保存してくれればまだ良いのですが、切り捨てたときが最も悪さをするケースです。
正確に2.6と保存してほしいところを2.6よりちょっと小さい数を保存してしまうことになり、
正確には積は2017 6343 1036 2021となるところが、2017 6343 1036 2021よりちょっと小さい数(+誤差)が結果として出てきます。そして小数点以下を切り捨てると、下2桁が21ではなく20となってしまう、ということです。
結局のところ、浮動小数点型を使わないで計算する必要がありそうです。
出来る方法としては、安全にBを整数に変換して、整数の掛け算として処理するか、
任意精度で計算できるdecimal型(pythonなど)を使って、正確にA*Bを計算する方法がありそうです。
前者の方法をメインに考えますが、「安全にBを整数に変換する」ためにもう少し考える必要があり、ここが2番目のトラップです。
後者の方法は全く別物なので、あとから補足だけします。
((20200624 0:26 ここまで。)
■ABC169 C問題 トラップ2 小数を整数型にキャストすることによる誤差
スポンサーサイト
コメント