※ 2019/02/11 に https://wkwkhautbois.wordpress.com/ に投稿した内容の再掲です。

久しぶりの投稿です。 CodeIQやPaizaは今まで何度か挑戦したことがありました。先日、「みんなのプロコン2019」なるコンテストがAtCoderで開かれるということを知り、アカウントを作り初めてAtCoderに挑戦しました。

AtCoderのアカウント自体を作ったばかりで使い方が分からずバタバタしたり、「え、Python3.4なの?(ちょっと古くない?)」とか焦ったりしながら挑戦する中で、掛け算 , 割り算 と浮動小数点 でハマったのでまとめます。

ハマったこと

C問題「 When I hit my pocket… 」を解いていたときのこと。入力例3の入力を試すも、微妙に計算結果が合わない。

このときの使用言語はPython3。出力の際に、最後に

print('%d' % x)

のようにしていた。最初は

print(x)

としていたが、浮動小数点の書式で出力されてしまったので上記のようにしていた。思えばこのときすぐに気づくべきだった。。

すると、小さい数字では上手くいくのに大きな数字になると微妙に値がずれる現象が発生した。具体的には、 48518828981938099 が出力されてほしいのに、 48518828981938096 が出力された。おかしいなと思い、試しにExcelで計算をしてみた。すると、Pythonのときとも違う値が出てきた。

そこで、浮動小数点演算になっている可能性に気づいた。しかし、偶数のときと奇数のときで場合分けをしていて、整数以外でてこないはず…どこで？

整数演算の結果の型

Pythonは除算の演算子の意味が、Python2とPython3で異なることが、破壊的変更なので結構有名。

Python2: 3 / 2 → 1
Python3: 3 / 2 → 1.5 、3 // 2 → 1

それから、Python3では全ての整数がint型で、Python2のlong型相当になっている。

ここまで知っていたが、一つ知らなかったことがあった。 6÷2のように、 割り切れる演算 のときの結果はどうなるのか? つまり、次のようなときにどういう結果になるか?

if a % 2 == 0:
    b = a / 2
else:    
    b = (a - 1) / 2

このとき、bは常に浮動小数点数(float)になる。実行コストを考えてみれば当たり前で、いちいち割り切れるかどうか判断してintとfloatを分けるはずもなく。ただ、浮動小数点数であっても結果が整数(に極めて近い小数)だったら問題になることは今までなくて気にしたことがなかった。

というわけで、除算の演算子を”/”から”//”に変えて一段落。

あれ、Excelは?

Excelでの結果がPythonで浮動小数点数演算になっていたときと違った。どうやらExcelでは内部的に全て浮動小数点数で扱っているようで、大きな数の乗算で誤差がでてくる。

セルに直接

=348728501 * 139130667

と入力してみたり、各セルに入力して

=A1 * B1

みたいにしてみたりしたが、どうも計算誤差が出てしまう。

上の計算は、正しくは 48,518,828,946,040,167 なのだが、Excelでは 48,518,828,946,040,200 になる。 33大きい 。表示形式を「通貨」にしてもダメだった。お金の計算はもう少し慎重にしてほしい。

Javascript:整数型の存在しない言語

Javascriptでは数値は全て浮動小数点数で扱われるということを思い出した。それで問題になったことはあまり聞いたことがないが、どうなるかNode.js 8で上記の計算を試してみると、 48,518,828,946,040,170 になった。こんどは 3だけ大きい 。 Node.jsで競技プログラミングに参加するのは避ける方が懸命のようだ。あるいは、対処法がある??

なお、整数演算が安全にできる範囲は定数で取得することができて、手元の環境でも確認したが Number.MAX_SAFE_INTEGER は9,007,199,254,740,991 だった。なるほど確かにそれを超えていた。

[参考] qiita.com

Pythonのfloatでの演算

Python3で小数に変換してから掛け合わせて、整数として表示すると、 48,518,828,946,040,168 になる。これまたNode.jsともExcelともちょっと違って 差は1 。ここで差がなかったら、プログラミングコンテスト中に気づくこともなかったかもしれないから逆にラッキーか。各言語(ツール)の結果の差は、浮動小数点数の内部表現の違いからくるのだろうか?CPUが浮動小数点数演算の回路を持っているからそれに依存するのが速いのだと思っていたけど、違うのだろうか?

学んだこと

スクリプト言語では動的に型付けされることもあって、あまり強くは型について意識していませんでした。それが便利なわけですがど、数値演算なら誤差に、文字列なら不用意な変換やら何やらに悩むことがあり、気をつける必要があると改めて学びました。

あと、5000兆円を手に入れたときにはExcelやJavascriptを利用したアプリで資産管理しないようが良さそうです。気をつけましょう。

わくわく技術ブログ

プログラミング・統計・機械学習

プログラミングコンテスト中に浮動小数点数で悩んだ話