线性拟合log2(1+x)

hbghlyj

Aliasing to an integer as an approximate logarithm中提到:

If \(x\) is a positive normal number:
\[x = 2^{e_x} (1 + m_x)\]
then
\[\log_2(x) = e_x + \log_2(1 + m_x)\]
and since \(m_x \in [0, 1)\), the logarithm on the right-hand side can be approximated by
\[\log_2(1 + m_x) \approx m_x + \sigma\]
where \(\sigma\) is a free parameter used to tune the approximation. For example, \(\sigma = 0\) yields exact results at both ends of the interval, while\[\sigma = \frac{1}{2} - \frac{1+\ln(\ln(2))}{2\ln(2)} \approx 0.0430357\tag1\]yields the optimal approximation (the best in the sense of the uniform norm of the error). However, this value is not used by the algorithm as it does not take subsequent steps into account.
Thus there is the approximation
\[\log_2(x) \approx e_x + m_x + \sigma.\]

式(1)是怎么计算出来的呢?
首先,计算函数$\log_2(1+x)-x$在$[0,1]$的最大值

1. Maximize[{Log2[1 + x] - x, 0 <= x <= 1}, x]

Copy the Code

$$M\coloneqq1-\frac{1+\ln(\ln (2))}{\ln (2)}$$
函数在0和1的值都是0,通过分析单调性知,函数值介于0和$M$之间.

对于0和$M$之间的$\sigma$,误差在[0,1]的最大值(uniform norm)等于$$\sup_{[0,1]}\left|\log_2(1+x)-x-\sigma\right|=\max\{\sigma,M-\sigma\}$$
所以取$\sigma=\frac12M$即可使上式最小,所以
$$\sigma=\frac{1}{2} - \frac{1+\ln(\ln(2))}{2\ln(2)}$$

hbghlyj

Hummus and Magnets
...
Now what remains is to find the constant. We already know what B and L are but we don’t have σ yet. Remember, σ is the adjustment we used to get the best approximation of the logarithm, so we have some freedom in picking it. I’ll pick the one that was used to produce the original implementation, 0.0450465. Using this value you get: \[{\frac 32}L(B - \sigma) = {\frac 32}2^{23}(127 - 0.0450465) = 1597463007\] Want to guess what the hex representation of that value is? 0x5f3759df. (As it should be of course, since I picked σ to get that value.) So the constant is not a bit pattern as you might think from the fact that it’s written in hex, it’s the result of a normal calculation rounded to an integer.

But as Knuth would say: so far we’ve only proven that this should work, we haven’t tested it. To give a sense for how accurate the approximation is here is a plot of it along with the accurate inverse square root:

Graph of approximation vs. accurate value This is for values between 1 and 100. It’s pretty spot on right? And it should be – it’s not just magic, as the derivation above shows, it’s a computation that just happens to use the somewhat exotic but completely well-defined and meaningful operation of bit-casting between float and integer.
...

hbghlyj

Matrix67 旧闻一则：神秘的0x5f3759df 不可思议的Quake III源码
Fast Inverse Square Root, Chris Lomont