第二周
前言:
10.20
今天体测跑了一公里,拿下了三分三十的成绩,有时感觉自己当时走体育会不会比现在混得好()
学习笔记:
一些杂项
很久以前就想写一下这个快速平方根取倒数算法了,这个好像还很有历史“渊源”来着,据说给当时“雷神之锤”的开发带来了巨大优化。
首先我们思考一下,平方根应该用哪种算法求,显然这是一个只能逼近的值,因此我们想到了“牛顿迭代”算法:
\[x_n=x_{n-1}-\frac{f'(x_{n-1})}{f(x_{n-1})}
\]
考虑函数 \(f(x)=x^2-a\) ,利用 \(f(x)=0\) 解出 \(\sqrt{a}\) 的值,先选定一个初始值 \(x_0\) 然后:
\[x_n=x_{n-1}-\frac{2x_{n-1}}{x_{n-1}^2-a}
\]
迭代求解。
显然复杂度是与求解的精度相关的,早期游戏工程师为了简化复杂度(众所周知早期算法工程师常从底层最大限度的优化算法,极致压榨 \(PC\) 机效率),从浮点数的性质入手:
\(32\) 位浮点数的 IEEE754
存储形式是这样的:
- \(S\) 是符号位,在开平方根是不必理会,因为计算机系统运算是基于实数的,在实数中对负数开平方是没有意义的
- \(E\) 表示阶码,但是有 \(127\) 的平移用来表示正负,故 \(E−127\) 是阶码表示的实际值
- \(M\) 表示尾码,表示原二进制浮点数第一个 \(1\) 之后的所有数位,基本可以认为隐藏了一位 \(1\) ,实际值为 \(1.xxxxxxx\)。
那么类似于十进制的科学计数法,我们可以将浮点数表示为:
\[y=(1+ \frac{M}{2^{23}})⋅2^{E−127}
\]
对于 \(\sqrt{a}\)