2006年12月5日 星期二

InvSqrt()

看到開根號倒數 (InvSqrt(), 1 / sqrt(x)) 速算法,這真是太棒了。寫了一段 code 測試,跑 1..1000000000 出來的時間,1 / sqrtf(i) 出來平均大約是 9 秒多一點,而 InvSqrt() 是接近 3 秒。至於數值的精確度,我對 1 .. MAX 每個值丟給兩個方法看他們的差,發現數字越大越準,而 InvSqrt() 出來的值「略小於」1 / sqrtf(x)。

Let f1 = 1 / sqrtf(x), f2 = InvSqrt(x)
這個表第一欄是 MAX,第二欄是 \sigma_{1..MAX}(f1 - f2),第三欄是把第二欄 sigma 裡面的值取絕對值,第四欄是平均誤差。

1000000000: 8.0000000000 8.0000000000 0.0000000800
10000000: 5.7150559425 5.7150559425 0.0000005715
1000000: 1.8854961395 1.8854961395 0.0000018855
100000: 0.5647696257 0.5647696257 0.0000056478
10000: 0.1864424646 0.1864424646 0.0000186461


另外,這是多次 (f1 - f2) / f1 跟平均值:

1000000: 944.7488403320 0.0009447498
100000: 85.7057800293 0.0008570664
10000: 9.4323215485 0.0009433264
1000: 0.9615601301 0.0009625227


1/1000 以下的相對誤差,看起還不賴呀。以後應該會用得著 XD
張貼留言