定点反正弦

Question

有没有人知道(最好是快速)计算4.12固定点角度正弦的方法？(结果是一个圆或度的32768ths)

4.12定点意味着数字是16位并且左移12,所以1.0变为(1 << 12)或4096. 0.5是(0.5 << 12)== 2048等.

Answer 1

如果您想要最大速度,预先计算是可行的方法.由于您有2 ¹⁶(65,536)个可能的输入,因此天真的方法是拥有一个包含许多16位值的数组(总共使用128K内存).

但如果您不想使用所有内存(以一点点速度为代价),那么可以稍微改进一下.

假设你的输入是弧度(我假设它们是因为4.12数字的范围是0到15.999 ......,不足以代表圆圈中的所有度数),你可以利用以下事实:

• sin (n) = sin (n % (2*PI)) for n >= 2*PI
• sin (n) = -sin (n - PI) for PI <= n < 2*PI
• sin (n) = sin (PI - n) for PI/2 <= n < PI

因此,您的查找表只需要保持0到PI/2弧度之间的值,从而显着降低存储要求:您只存储0到PI/2(~1.571)而不是0到15.999的整个范围...,a减少约90%.

然后,您只需要使用模数(第一个规则)将值降低到2*PI弧度以下,并使用其他两个规则对其进行修改,以找到要查找的正确索引.Modulo可以像整数一样快速地在固定点上工作.

所以你会看到类似的东西:

def sin(r):
    if r >= PI_BY_2:
        return sin (r % PI_BY_2)
    if r >= PI:
        return -sin (r - PI)
    if r >= PI_DIV_2:
        return sin (PI - r)
    return sin_lookup[r]
def cos(r):
    if r < PI_DIV_2:
        return sin (r + PI_DIV_2_BY_3)
    return sin (r - PI_DIV_2)

该cos函数显示了从同一个表中获取余弦的成本是多么便宜,因为它们实际上只是从正弦相移90度.

如果速度极为重要且内存无关紧要,只需使用全部索引即可,因此无需进行任何计算.

另一个技巧是,如果你愿意牺牲一些准确性,增加使用更少的内存,就是不存储所有输入值的查找值.

假设正弦函数是平滑函数(没有不连续性),您可以存储每一个值,并通过简单地平均它们两侧的值来插值其间的值.

例如,如果我们有函数,则会f(x) = x * x跟随实数和插值的表(假设我们只存储偶数的x奇数值,奇数值x被插值,用*下面标记):

 x    real f(x)   interpolated f(x)
--    ---------   -----------------
 0            0                   0
 1            1                   2 *
 2            4                   4
 3            9                  10 *
 4           16                  16
 5           25                  26 *
 6           36                  36
 7           49                  50 *
 8           64                  64
 9           91                  82 *
10          100                 100

现在,这不是一个完美的例子,因为f(x)值之间的差异可能非常大,但它对于值更接近的函数更有效.

例如,sin(0),sin(1)和sin(2)(度,而不是弧度)的实数值是0,0.017452406和0.034899496(这是斜率最大的地方).sin(0)和sin(2)的平均值是0.017449748,这是实际值的误差0.0152%,一部分是6,500.

因此,对于最小的错误,您可以将内存需求减半至128K的约5%,或六个半K.