algorithm - 対数はどのようにプログラムされていますか?

Question

線形探索と同じメカニズムを使用して把握しただけなのか、それとも二分探索のように何らかの方法で範囲を絞り込んだのか。

Answer 1

まともな数学ライブラリでの自然対数などの関数の実装は、誤差を ulp (最小精度の単位) 未満に保ちます。数学ライブラリ関数の実装者の目標は、可能な限り少ない計算で目的の精度を達成する最適な近似を見つけることです。テイラー級数は、必要な精度を達成するために必要な項が多すぎるため、通常は適切な選択ではありません。

選択される典型的な武器は、表現可能なすべての実数から非常に小さな領域に範囲を縮小し、この狭い範囲で目的の関数の正確な近似を生成する最適な近似を使用することです。この最適な近似のために選択される典型的な武器は、多項式または有理多項式 (2 つの多項式の比率) です。実装には、多項式係数が含まれているだけです。これらの係数は、Remes Exchange アルゴリズムなどの最適化手法によって構築されます。

自然対数の場合、範囲を縮小する簡単な方法があります。実数はほとんどの場合、仮数と指数で表されます: x = m *2 ^p、ここで、pは整数、mは 1 ～ 2 です。したがって、log( x ) = log( m )+ p *log( 2)。後期、p*log(2) は、既知の定数による単純な乗算です。したがって、問題は、1 と 2 の間 (または 1/2 と 1 の間) の数値の対数を見つけることになります。√2 が対数的に [1,2) の中間にあるという事実を利用して、範囲をさらに縮小することができます。したがって、必要なのは、1 から √2 までの数値の対数を計算する方法だけです。これは通常、有理多項式で行われます。2 次多項式多項式と 3 次多項式の比率は、このために非常にうまく機能します。