@mitchan5 (hiro Minami)posted at 2022-08-24

Logの取り扱い方

Q&A

解決したいこと

Atcoderの競プロ典型90問の020-Log Inequality でのlogの取り扱い方を教えていただきたいです。

発生している問題・エラー

こちらのURLになります。
https://atcoder.jp/contests/typical90/tasks/typical90_t

該当するソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
  int64_t a, b, c, d;
  cin >> a >> b >> c;
  d = pow(c, b);
 	  if(a < d) cout << "Yes" << endl;
 	  else cout << "No" << endl;
  }

自分で試したこと

単純にlogを使ってしまうと計算中の誤差によって答えがずれると思い、powによる累乗で比較を行いましたがうまくいきませんでした。

またif(a<pow(c,b))とした時と、d = pow(c, b); if(a < d)とした時とで、WAのつくケースが変わっており、なぜ変化するのかがわかりません。

よろしくお願いいたします。

2Answer

@PondVillege posted at 2022-08-24

単純にlogを使ってしまうと計算中の誤差によって答えがずれると思い、powによる累乗で比較を行いましたがうまくいきませんでした。

前半正解で，後半も前半と同様の理由で答えがずれます．丸め誤差ですね．

IEEE754の話になってしまいますが，単純に言って64bit整数aとpow(long, long)では有効な桁数が違います．後者は52bit精度です．

したがって，

if(a<pow(c,b))とした時と、d = pow(c, b); if(a < d)とした時とで、WAのつくケースが変わる

という問題も桁数の差で起きるということです．前者は52bit精度で比較されるのに対して，後者ではdに代入し，空いた桁は0埋めされて64bit精度で比較されます．おそらくここに差分があるのでしょう．前者は52桁の比較しか行わない，すなわちaの持つ比較されなかった12桁が実質0埋めされたと考えると良いでしょう．

したがって，有効桁数が大きいpowl()を使うと解決すると思います．ただのpow()はdoubleを返しますが，powl()はlong doubleで精度が112桁のものを返してくれるので丸め誤差なしの比較が可能です．

1Like

Comments

@mitchan5
Questioner
いつも分かりやすい説明ありがとうございます！
ほかの人の回答でfor文で累乗を求めていたものがACになっていた理由がわかりました。
ありがとうございます。
@PondVillege
そうですね，問題の性質上，bのc乗，制約で示された最大値13^17はおよそ8.6504159e+18ですから，64bit整数の範囲に収まる値をとっており，for文で累乗を求めるのが一番何も気にしなくて良い実装になります．こういった見通しもAtCoderでは大事ですね．long doubleが標準で無いようなPython等の言語にも通用する手法となっており，アルゴリズムを適切に使えている感じがします．

@tueda posted at 2022-08-24

pow関数の引数は整数ではありません。

https://cpprefjp.github.io/reference/cmath/pow.html

よって、ここではdouble版が呼ばれています。すると戻り値もdoubleなので有効数字が18桁に届いていません。

以下は、powのdouble版が呼ばれることを示すテストコードです。

https://wandbox.org/permlink/SEVQ5fynYfTgvN4a

#include <bits/stdc++.h>
using namespace std;

template<typename T>
T my_pow(const T& a, int b) {
    T r = 1;
    for (int i = 0; i < b; i++) {
        r *= a;
    }
    return r;
}

int main() {
    int64_t b = 17;
    int64_t c = 13;
    cout << setprecision(20);
    cout << "int64_t           " << my_pow(c, b)                        << endl;
    cout << "pow               " << pow(c, b)                           << endl;
    cout << "pow(float)        " << pow((float)c, (float)b)             << endl;
    cout << "pow(double)       " << pow((double)c, (double)b)           << endl;
    cout << "pow(long double)  " << pow((long double)c, (long double)b) << endl;
}

int64_t           8650415919381337933
pow               8650415919381338112
pow(float)        8650415977864888320
pow(double)       8650415919381338112
pow(long double)  8650415919381337933

解決するには、この問題の場合$b \le 17$ということなので、素直に$c$を$b$回掛ければ十分でしょう。（環境によってはlong doubleにキャストして明示的にlong double版のpowを呼んでもよい。）

なお、d = pow(c, b); if(a < d)だと、aとdがint64_tとして比較されますが、if(a<pow(c,b))の場合は、aがdoubleにキャストされてから右辺と比較されるので、精度が変わります。

1Like

Comments

@mitchan5
Questioner
tuedaさん、ご丁寧に回答いただき、ありがとうございます！
有効数字よくわかりました、またよろしくお願いいたします！

Are you sure you want to delete the question?

Logの取り扱い方

解決したいこと

発生している問題・エラー

該当するソースコード

自分で試したこと

2Answer

Comments

Comments

Your answer might help someone💌