A - kcal Editorial by MMNMM

実数(浮動小数点数)の計算・出力の誤差について

答えは \(AB/100\) です。 次のコードでACすることができます(実際の提出)。

#include <iostream>

int main(){
  int A, B;
  std::cin >> A >> B;
  std::cout << A * B / 100.0 << std::endl;
  return 0;
}

以下では、少し発展的な話題として、上のコードが出力するものの誤差を評価することについて考えます。 ここから下の内容はC++や浮動小数点数に関する文章をあまり引っかかることなく読み進められるような中級者以上のユーザーを主な対象として書いています。

まず、\(A\)\(B\)int の範囲に収まる値を入力として受け取ります。 5行目、およびそれ以前に誤差はありません。

6行目では、((A * B) / 100.0) の計算が行われます。 ここでは、次の順番で処理が行われます。

  1. AB の積を計算する
  2. 1.の結果を int から double へキャストする
  3. 2.の結果を 100.0 で割る

それぞれのパートで生まれうる誤差について考えます。

  1. AB の積は、結果が \(0\) 以上 \(1000000\) 以下の整数になります。これは int 型に収まるため、誤差はありません。
  2. 1.の結果を int から double へキャストするとき、C++17 の規格の [7.10.2] に「The result is exact if possible.」とある通り、今回は double で正確に表現できる値のため誤差はありません。
  3. 100.0double で正確に表現できる値なので、ここで行われるのは正確に値が \(AB\)\(100\) である double 型の変数どうしの割り算です。ここで std::numeric_limits<double>::is_iec559true なので、型 double は IEEE 754 に従っています。よって、その結果は \(AB/100\)double に表現可能な値に(ここでは、偶数への丸めによって)丸めたものになります。std::numeric_limits<double>::epsilon() が返す値を \(\varepsilon\) とすると、その相対誤差もしくは絶対誤差は \(\dfrac{\varepsilon}{2}\) 以下です。特に、\(AB/100\)\(0\)\(1/100\) 以上なので、その相対誤差は \(AB/100=0\) のとき \(0\)、そうでないとき \(50\varepsilon\) 以下です。

今の環境では \(50\varepsilon\)\(2\times10^{-14}\) で上からおさえられることに気をつけます。

std::cout に上で計算した値を渡し、出力します。

std::cout はデフォルトでは整数部小数部合わせて \(6\) 桁出力します。 今、浮動小数点数の丸め方は偶数への丸めになっています。

今回の制約のもとで、ある高々 \(6\) 桁の数 \(X\) と整数 \(k\) が存在して \(AB/100=X/10^k\) が成り立ちます。

\(X=0\) のとき、計算結果は \(0\) であり、出力も \(0\) なので誤差はありません。

\(X\neq0\) のとき、絶対誤差は高々 \(2X\times10^{-14-k}\) であるので、std::cout の丸めと合わせて出力される値は \(AB/100\) と等しいことが言えます。

以上から、上のコードは真の値と完全に等しい出力を行います (ただし、この問題では想定解答からの誤差によって正答が保証されるため、上のコードが出力するものと真の値との間に誤差がないことは上のコードがACすることを必ずしも意味しないことに注意してください)。

余談ですが、入力例 1 45 200 に対して 9.00000e+01 を出力する以下のコードもACを得られます(実際の提出)。

#include <iostream>
#include <iomanip>

int main(){
  int A, B;
  std::cin >> A >> B;
  std::cout << std::scientific << std::setprecision(5);
  std::cout << A * B / 100.0 << std::endl;
  return 0;
}

posted:
last update: