brainfuck でも三角関数がしたい【ABC168C-: (Colon) を解く】

初めに

この記事は普通の問題解説ではないので、普通の解説が見たい方は別の方の記事をご覧ください。

概要

今回は ABC168 の C 問題の「: (Colon)」を brainfuck で解いたので、軽い解説を書いていきます。

atcoder.jp

解法

今回はコンテスト後にトレンドにも上がった、余弦定理を使っていきます。
余弦定理は $c=\sqrt{a ^ 2+b ^ 2-2ab\cos\theta}$ です。

時針と分針の角度を求める

少数でやるのは嫌なので、可能な限り整数で計算します。
12 時間は 720 分なので 720 で一周となるように時針と分針の角度を求めます。
時針と分針の角度は、それぞれ

$\theta_h = 60 \times h + m\\ \theta_m = 12 \times m$

と表せます。
また、0 時をまたぐ側が短い場合もあるので、

$\theta = Min( | \theta_h - \theta_m |, 720 - | \theta_h - \theta_m |)$

として角度を出します。
ここから、弧度法に直すのですが、 $\cos$ を求めるときに計算します。

三角関数 (cos) の実装

もちろん、brianfuck には三角関数を導出するような標準関数はない(そもそも関数がない)ので自前で実装します。
具体的には、マクローリン展開を使います。
$\cos$ のマクローリン展開は以下のようなります。

$\displaystyle{\cos x = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \frac{x^6}{6!} ...}$

ここでべき乗や階乗が出てきますが、それらの計算はめんどくさいので少し工夫をします。
上記の式を下記のように変形します。

$\displaystyle{\cos x = 1 + \sum_{i = 1}^{n} (-1)^i \frac{x^2i}{2i!} = 1 + \sum_{i = 1}^{n} (-1)^i f(i)}$

ここで $f(i)$ は

$\displaystyle{f(i) = f(i-1) \times \frac{x^2}{2i(2i-1)} } ( i \geq 2)$

となります。
また、 $2i(2i-1)$ は、

$g(i) = g(i-1) + 8i - 6$

と表せます。

上記を踏まえ、 $\cos$ のマクローリン展開を書くと以下のようなコードで実現できます。

double Cos(double x, int degree)
{
    double sqX = x * x;
    double divisor = 2;  // g
    double term = sqX / 2; // f
    double ret = 1 - term;
    bool isMinus = false;
    for(int i = 2; i <= degree; i++)
    {
        term *= sqX;
        divisor += 8 * i - 6;
        term /= divisor;

        if(isMinus)
            ret -= term;
        else
            ret += term;
    }
    return ret;
}

ここで、 $x$ そのものは使用せず、 $x ^ 2$ のみを使用しています。
なので、角度を弧度法に変換する際に、

$\displaystyle{x = \theta \times \frac{\pi}{360}}$

とするのではなく、

$\displaystyle{x^2 = \theta^2 \times \left(\frac{\pi}{360} \right)^2}$

とします。
$\theta ^ 2$ は整数で計算が可能で、 $\left(\frac{\pi}{360} \right) ^ 2$ は定数なので、あらかじめ計算をしておくことができ、誤差を抑えることができます。

マクローリン展開のコードは書くのはしんどいですが、見た目ほどは難しくは内容に感じます。
(それでも数時間かけて書きましたが。)

平方根を求める

余弦定理を用いた辺の長さを求めるのに必要な数値は揃ったのであとは、 $c ^ 2$ を求めて、平方根を出すだけで終わりです。
平方根を求めるのは、開平法をやるだけです。 brainfuck での開平法の実装方法はここでは説明しません。
個人的意見としては、除算のコードよりも楽だった印象があります。

以上で問題を解くことができます。

ところで精度は足りますか？

実はこの問題、制度が結構厳しくて $10 ^ {-9}$ となっています。
通常、相対誤差が重要ですが、固定少数点を使う関係上、絶対誤差の方が重要になります。
また、最終的に平方根をとるので、少数点以下 20 桁あったほうが良いと思います。
そのため、マクローリン展開等の誤差も考えて、小数点以下 32 桁でマクローリン展開を行いました。
また、計算上出てくる最大の数値は、4000000 なので整数部分も 7 桁は必要になります。
それを加味して、最終的に、整数部分 13 桁、少数部分が 32 桁の合計 45 桁で計算を行いました。
実際、マクローリン展開の計算を考えると、これでも精度が足りていない気がするのですが、実際に AC できているので良しとしましょう。
~~(コーディング中はずっと「精度足りない気がするなぁ」と言いながら書いてました。)~~

実際の提出

実際の提出はこちら

あとがき

今回は brainfuck でも三角関数の計算はできるということを見せるためにコーディングをしましたが、三角関数の実装はもうやりたくないですね。
助長な部分も多いというのもありますが、以前紹介したオセロプログラムの行数を大幅に超えました。

次は、Grid Compression について書きたいなと思ってるんですが、果たして筆は進むのか…

質問とかあれば、ここにコメントするか Twitter　でリプもらえれば反応すると思います。
今回の記事の内容じゃなくても全然大丈夫なので気軽に質問ください。
それでは良い brainfuck ライフを。

三流プログラマの戯言

プログラミング初心者が気になったことを書き綴るだけ。主にc#