Exp

top Top: -

par Par: 65 lines

Problem Statement

LM0上の Float 配列 \(X\) の各要素 \(X[i]\) について、指数関数 \(Y[i] = \exp(X[i])\) を計算し、LM1上に出力してください。

Explanation

Exp low prec と同様の問題ですが、許される誤差が小さくなっているため、より精度を上げないといけません。また、\(A\) の下限値も -89 まで下がっています。

マクローリン展開の次数を増やすだけではこの問題を解くことはできません。そこで、引数低減というテクニックを使います。

引数低減とは、指数関数の計算を \(e^x = 2^k \cdot e^r\) の形に変形し、計算を効率的かつ正確に行う手法です。

この変形の目的は、マクローリン展開で計算する部分の引数 \(r\) を、\(0\) に近い値にすることです。引数が \(0\) に近ければ近いほど、マクローリン展開はより速く収束するため、少ない項数で高い精度を得られます。

\(r\) の絶対値が小さくなるように、\(k=\operatorname{round}(x/\ln(2)); r = x-k\times\ln(2)\) で求めます (\(\ln(x) = \log_e(x)\))。こうすることで、\(r\) の絶対値は \(\ln(2) \approx 0.693\) 以下になります。

この \(r\) を用いて \(\exp(r)\) を計算し、最後に \(2^k\) を掛けることで、元の \(\exp(x)\) を求めます。

引数低減を行うことで、7次までのマクローリン展開で Accept が得られることを確認しています。

\(k\), \(r\) を求める実装

丸め関数 \(\operatorname{round}(x)\) は、\(\operatorname{floor}(x + 0.5)\) と同じです。MN-Core では、fvfma 命令で x * 1.44269504 + 0.5 を計算し、ALU の ffloor 命令で \(k\) を求めると良いでしょう。

最後に \(2^k\) を掛ける実装

実数のまま、\(2^k\) の値を求めて ffmul するのは大変です。そこで、IEEE 754形式の浮動小数点数を整数として扱い、指数部に \(k\) を加算することで \(2^k\) 倍を実現します。

fftoi 命令で \(k\) を整数に変換し、ilsl 命令で \(k\) を 23 ビット左シフトすることで、加算すべき値が分かります。

ただし、\(k\) が \(-128\) 以下の場合、指数部がオーバーフローして正しくない値になっていまいます。

そのため、もとの入力 \(x\) が \(-127.5 \times \ln(2) = -88.3763\) 以下の場合は、結果を \(0\) にする必要があります。

なお、今回の問題は \(10^{-6}\) までの絶対誤差を許容するため、入力が \(\ln(10^{-6}) = -13.81551\) 以下であれば \(0\) と答えても Accept されます。

そのため、しきい値はこの -14 から -88 の範囲で適当に選ぶことができます。

また、本来は負のオーバーフローだけでなく、大きな入力が与えられた場合の正のオーバーフローも考慮する必要がありますが、今回の問題では入力の上限が \(2\) なので、正のオーバーフロー対策は不要です。

多層パーセプトロンに使われる Softmax 関数 では内部で Exp が使われますが、この用途のときは Exp の入力を 0 以下に調整して使用するため、この背景に沿った問題設定となっています。

Inputs

Outputs

Testcases

testcase.vsm

Submission

ログイン / 新規登録