AtCoder Beginner Contest 169 C:Multiplication 3


f:id:aisakakun:20200602231649j:plain

はじめに

decimalを使用すれば精度高く浮動小数点が式中に登場する式の積が求められるらしいことはコンテスト中に分かったが、解答に至らなかったので、復習。
atcoder.jp
decimalの使用に適した形が理解できたのでメモ。

条件

問題文として与えられている条件は
 0 \leq A \leq 10^{15}
 0 \leq B \leq 10
Aは整数
Bは小数第二位まで

解答

using System;
using System.Collections.Generic;
using System.Linq;

namespace easy_Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            decimal[] AB = Array.ConvertAll(Console.ReadLine().Split(),decimal.Parse);
            Console.WriteLine(Math.Floor(AB[0]*AB[1]));
         }
    }
}

解説

decimalは符号部1ビット、指数部7ビット、仮数部96ビットで表現されます。この問題の解答を出す上で重要なのは、この3つの中でも指数部。decimalを使用する際には注意事項があります。それは、2つの桁数が違いすぎると、計算値が正確でなくなる点です。正確出なくなるのは、計算の方法に理由があります。

  1. 指数部を比較し、指数部の小さい実数の仮数部を指数部の大きい実数の指数部(すなわち小数部の精度が大きい方)に合わせて指数部の値を増やし、その分だけ10のべき乗を掛けます。
  2. 仮数部同士で加減算をします。

引用元:[C#] decimal型はどうやって加減算をしているのか - Qiita

とあります。したがって、その差が大きければ大きいほど、仮数部は10の何乗かを掛けられるということになります。
例をあげます。

A = 10^{28}
B = 10^{-8}

の場合、decimalの上限は下記サイトによると7.9228\times 10^{28}です。
本来は、

A = 10^{36} \times 10^{-8}
B = 10^{-8}

とし、

 A+B = (10^{36}+1) \times 10^{-8}

となるはずです。しかし、decimalは上限7.9228\times 10^{28}であるので10^{28}10^{8}の積をとることはできません。積をとるとオーバーフローするからです。そのため、Bの方の指数部をAに合わせようとします。

A = 10^{28}
B = 0\times10^{0}

となります。

Bは0.00000001→0

になってしまいました。このように指数部を合わせたときに一方の仮数部の値が大きく、他方の指数部が7より大きくなる可能性がある場合、切り捨てられてしまいます。
今回の問題では、上限が10^{15}、指数部は小数第二位までですので、この切り捨ては行われません。
したがって、decimalを使用することができ精度の高い計算を行うことができました。
引用元:浮動小数点数値型 - C# リファレンス | Microsoft Docs