2

有谁知道一种（最好是快速）计算 4.12 固定点角度正弦的方法？（结果是圆的 32768 度或度数）

4.12定点表示数字为16位，左移12位，所以1.0变为(1 << 12)或4096。0.5为(0.5 << 12) == 2048，以此类推。

4

2 回答 2

8

如果您想要最大速度，则预先计算是要走的路。由于您有 2 16 (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 的整个范围......减少约 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% 左右，即 6K 半。

于 2009-11-15T04:50:23.673 回答
1

最快的方法是简单地预先计算它们并将其存储在查找表中。

当然，这一切都取决于您期望计算它的值的精度。更多细节会很好。

于 2009-11-15T03:20:02.020 回答