擬似的なlog計算の方法を知りたい

Question

プログラム上でlog(底はe)の計算を擬似的に行う方法はありますか？
精度は高くなくてよく，速度を重視した方法がいいです．
普通にcなどにあるlogの関数を使うよりも低い精度でいいので早い方法が知りたいです．

Comments

[rinjinto]

log(x)よりも早く結果が出せるということですか？
結構厳しいような。

[maisumakun]

引数の範囲は限定できますでしょうか？

[pypy7]

ありがとうございます　引数の範囲は0~1の一様乱数です
一様乱数にlogをかませた擬似的な乱数を生成したいというのが一番の目的です

Answer 1

遅くなりましたが、Fast log2のテストをしてみました。

誤差はまあまあですが、おそらく標準のlog2よりは遅いでしょう。

ソースは以下です。

$ cat log2.c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define FRACTION (23)
#define EXPONENTMASK (0xFF)
#define BIAS (127)

float fast_log2 (float val)
{
    int *exp_ptr = (int *)&val;
    int x = *exp_ptr;
    int log_2 = ((x >> FRACTION) & EXPONENTMASK) - (BIAS + 1);
    x &= ~(EXPONENTMASK << FRACTION);
    x += BIAS << FRACTION;
    *exp_ptr = x;
    val = ((-1.0f/3) * val + 2) * val - 2.0f/3;
    return (val + log_2);
}

int main(void) {
    float f;

    f = 1.0;
    printf("%f fast_log2: %15.15f\n", f, fast_log2(f));
    f = 2.0;
    printf("%f fast_log2: %15.15f\n", f, fast_log2(f));
    f = 3.0;
    printf("%f fast_log2: %15.15f\n", f, fast_log2(f));
    printf("%f math log2: %15.15f\n", f, fast_log2(f));
    f = 0.1;
    printf("%f fast_log2: %15.15f\n", f, fast_log2(f));
    printf("%f math log2: %15.15f\n", f, log2(f));
}

実行結果

$ ./log2
1.000000 fast_log2: -0.000000059604645
2.000000 fast_log2: 0.999999940395355
3.000000 fast_log2: 1.583333253860474
3.000000 math log2: 1.583333253860474
0.100000 fast_log2: -3.319999933242798
0.100000 math log2: -3.321928073389531

Comments

[ikadzuchi]

いえ、少なくとも私のPCでは早いですね。
int time0 = clock();
double temp = 0;
for(double i=0.1; i<1; i+=0.00000001)
{
temp += fast_log2(i);
}
printf("%d\n(%f)\n", clock()-time0, temp);
のようなコードで、
mathのlog2が 1515625
fast_log2が 859375
空(加算のみ)が 296875
程度でしたので、2倍ちょっと早いようです。

Answer 2

考え方として簡単なのは範囲を区切って直線で近似する方法です。

たとえば以下のグラフは 6x-2 と 0.8x-0.8 で近似した例です。

最大誤差の見積もりは事前に可能ですから、必要な精度に応じて分割を多くすればよいでしょう。 とはいえ、標準ライブラリが提供する log はかなり高度にチューニングしていることが多いと思われるのでそれより速くなるレベルにするにはかなり雑な分割しか出来ないかもしれませんね。

CPU が対数計算のための (あるいは直接ではないにしても役立つような) 命令を持っている場合もあるので理論上の計算速度が速い式であっても専用回路にはかなわないという場合もあります。

Comments

[pypy7]

なるほど　ありがとうございます！

Answer 3

frexpを使って0.5<x<=1の範囲に持ち込んで（指数分はln(2)の定数を用意しておいて調整）、ln(1+x)のマクローリン展開を途中で打ち切る、ような流れが考えられます。

ただし、ライブラリは徹底的にチューニングされていることも多いです。自分で書いて勝てるかは、実験してみないとわかりません。

Answer 4

ググっただけですが、こんなのを見つけました

Fast log() Function - flipcode

Comments

[pypy7]

ありがとうございます!　試してみようと思います