java - 対数アルゴリズム

Question

任意の底の対数を評価する必要がありますが、それは問題ではありません。これにはアルゴリズムがありますか？私は Java でプログラミングしているので、Java コードには問題ありません。

バイナリ対数を非常に高速に見つける方法は? (せいぜい O(1)) で質問に答えられるかもしれませんが、わかりません。明確にすることはできますか？

Answer 1

このIDを使用します。

log _b（n）= log _e（n）/ log _e（b）

ここで、はlog任意の基数の対数関数であり、nは数でありb、は基数です。たとえば、Javaでは、これは256の2を底とする対数を見つけます。

Math.log(256) / Math.log(2)
=> 8.0

Math.log()ちなみにベースeを使用しています。またMath.log10()、baseを使用するもあります10。

Answer 2

これが非常に遅いことはわかっていますが、ここでの問題は精度であるため、一部の人にとっては役立つかもしれません. これを行う 1 つの方法は、単純な +-x/ 操作で構成される、使用したい高精度型をベースから使用するルート検出アルゴリズムを本質的に実装することです。

ニュートン法を実装することをお勧めします。これは、必要な反復回数が比較的少なく、収束性が高いためです。この種のアプリケーションの場合、具体的には、適切な入力検証が実装されていれば、常に正しい結果が得られると言っても過言ではありません。

単純な定数「a」を考えると、

a が従うように解かれようとする場合、

ニュートン法を繰り返し使用して、指定された許容範囲内で "a" を見つけることができます。ここで、各 a-i 回の反復は次のように計算できます。

分母は

、

これは、ニュートン法に必要な関数の一次導関数であるためです。これが解決されると、「a」は「a = log,b(x)」問題の直接的な答えであり、単純な +-x/ 操作で取得できるので、もう準備完了です。「待って、でもそこに力があるの？」. はい。べき乗関数が十分に正確であると信頼できる場合は、先に進んでそこで使用しても問題はありません。それ以外の場合は、これらのメソッドを使用して、べき乗操作を一連の他の +-x/ 操作にさらに分解できます。累乗の 10 進数を単純化して、一連の乗算演算で簡単に計算できる 2 つの整数累乗演算にします。このプロセスにより、最終的に解決すべき n 乗根が残ります。これは、ニュートン法でも見つけることができます。その道を行く場合は、これをニュートン法に使用できます

ご覧のとおり、これは b = 1 に到達するまで再帰的に解決する必要があります。

ふう、しかし、そうです、それだけです。これは、+-x/ 操作のみで全体を通して高精度型を使用することを確認することで、問題を解決できる方法です。以下は、ソフトウェアの元の関数によって与えられたソリューションと比較して、log,2(3) を解決するために Excel で行った簡単な実装です。ご覧のとおり、最適化関数が与えるものを監視することで、必要な許容値に達するまで "a" を改良し続けることができます。ここでは、最初の推測として a=2 を使用しました。これは、ほとんどの場合に使用でき、問題ないはずです。