プログラムで小数点以下の計算をおこなうと誤差が生じることがあります。コンピュータの場合、二進法で計算の処理をおこなっていますが、小数点以下の数を2進数で表現できない場合があり、人間目線だと意外なところで誤差が発生することがあります。
切り上げの計算と誤差への対応
10の-18乗以上～10の18乗以下の整数 X が与えられるので、X / 10 以上の整数のうち最小のものを出力してください。
例：入力が「27」であれば、X / 10 は 2.7なのでこれ以上の整数のうち最小のものは 3 です。入力が -13 であれば、X / 10 は -1.3 なのでこれ以上の整数のうち最小のものは -1 です。
一見簡単そうな問題ですが、注意が必要な問題です。Math.Ceilingメソッドを使えばよさそうですが、これではダメです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
using System; class Program { static void Main() { long value = long.Parse(Console.ReadLine()); Solve(value); } static void Solve(long value) { double value2 = value / 10D; long ans = (long)Math.Ceiling(value2); Console.WriteLine(ans); } } |
実行してみると以下のような結果になります。123456789123456789を渡したときの答えが間違っています。正しい答えは12345678912345679です。
|
1 2 3 4 5 6 7 8 |
static void Main() { Solve(27); // 3 (OK) Solve(-13); // -1 (OK) Solve(40); // 4 (OK) Solve(-20); // -2 (OK) Solve(123456789123456789); // 12345678912345678 (NG) } |
正しい切り上げの処理をするには？
なぜこのようなことがおきるのでしょうか？
double のような一般的な小数型(倍精度浮動小数点型)は高々 2進法で53桁、10進数に換算すると約16桁程度の精度しか持ちません。よって大きい数を計算しようとすると誤差が発生して正しい計算ができなくなります。誤差の影響を避けるためには整数型のみを利用するようにします。
正の数である a を b で割ったときの整数部分であれば以下の公式で求めることができます。
それからもうひとつ問題があります。a が負数のときはどうするかです。このような「割られる数が負である」かつ「余りが発生している」場合には上記の式で計算した答えから1 を引きます。これで正しい答えを得ることができます。
|
1 2 3 4 5 6 7 |
static void Solve2(long value) { long ans = (value + 10 - 1) / 10; if (value + 10 - 1 < 0 && (value + 10 - 1) % 10 != 0) ans--; Console.WriteLine($"{value} => {ans}"); } |
平方根の比較
1以上 10の9乗以下の整数である a, b, c が入力される。√a + √b ＜ √c かどうか？
これまでの流れから以下のコードではダメです。
|
1 2 3 4 5 6 7 |
static void Solve(long a, long b, long c) { if (Math.Sqrt(a) + Math.Sqrt(b) < Math.Sqrt(c)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } |
元の問題を少しかえて √a + √b = √c かどうかを考えてみます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class Program { static void Main() { IsEqual(2, 2, 8); // √2 + √2 = √8 はいいのだが IsEqual(2, 8, 18); // √2 + √8 ≠ √18 となってしまう } static void IsEqual(long a, long b, long c) { if (Math.Sqrt(a) + Math.Sqrt(b) == Math.Sqrt(c)) Console.WriteLine($"√{a} + √{b} = √{c}"); else Console.WriteLine($"√{a} + √{b} ≠ √{c}"); } } |
2乗して比較する
√8 = 2 × √2, √18 = 3 × √2 なのだから √2 + √8 = √18 になるはずなのですが、このコードでは等しくないと判定されます。これも倍精度浮動小数点型の誤差が原因です。整数として処理をしなければ数学的に正しい結果を得ることはできません。
√a + √b と √c の大小関係は両辺を2乗しても変わりません。そこで（√a + √b）の２乗と c を比較します。すると左辺は a + 2√ab + b となります。移項して左辺を 2√ab だけにしてもう一度両辺を2乗します。すると左辺は 4ab となり、右辺は（c – a – b) ^ 2 となります。この大小関係を比較します。
しかしこれでは実は不十分です。2乗すると負数も正数となります。だから c – a – b ≧ 0 であることも確認しなければなりません。
両辺は等しい ⇔ c – a – b ≧ 0 「かつ」 4ab =（c – a – b) ^ 2
左辺が大きい ⇔ c – a – b ≦ 0 「または」 4ab ＞（c – a – b) ^ 2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
static void IsEqual(long a, long b, long c) { if (c - a - b >= 0) { // Math.Pow(c - a - b, 2)ではなく(c - a - b) * (c - a - b)としなければならない if (4 * a * b < (c - a - b) *(c - a - b)) Console.WriteLine($"√{a} + √{b} < √{c}"); if (4 * a * b == (c - a - b) * (c - a - b)) Console.WriteLine($"√{a} + √{b} = √{c}"); if (4 * a * b > (c - a - b) * (c - a - b)) Console.WriteLine($"√{a} + √{b} > √{c}"); } else Console.WriteLine($"√{a} + √{b} > √{c}"); } |
対数の比較
これは対数の大小を考える問題です。底が2、真数 a の対数と底が2、真数 c の対数を b 倍したものとの比較です。a, b, c はいずれも1以上 10の9乗以下の整数です。これも当然のことながら以下のコードではダメです。
|
1 2 3 4 5 6 7 |
static void Solve(long a, long b, long c) { if(Math.Log(a, 2) < b * Math.Log(c, 2)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } |
整数同士で評価するのであればaとcのb乗を比較することになりますが、bは最大で10の9乗です。絶対に無理なのですが、ここは c が 2 以上の場合、bがある程度大きくなればつねに右辺のほうが大きくなることに気づきましょう。
Math.Log(1000000000, 2)を計算してみると59と60の間の値になります。ということはaがとりうる最大値（Math.Log(1000000000, 2)）であったとしてもよりも 60 * Math.Log(2, 2) のほうが大きいのです。60乗ならループを回せば計算できます。またcのb乗を計算しようとしてオーバーフローした場合はaよりも大きな値であることがわかります。
またc が 1のときは右辺は0になります。左辺を右辺を小さくするaは1以上10の9乗以下という範囲内には存在しないのでこの場合は”No”を出力すればよいことになります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
static void Solve(long a, long b, long c) { if (c == 1) { Console.WriteLine("No"); return; } if (b >= 60 && c >= 2) { Console.WriteLine("Yes"); return; } // a と c ^ b を比較するためにc ^ bを計算する long x = 1; long preX = 1; for (int i = 0; i < b; i++) { x *= c; // x > a であったり ｘx がオーバーフローしたら右辺が大きいので終了 if (x > a || preX > x) { Console.WriteLine("Yes"); return; } preX = x; } Console.WriteLine("No"); } |
