从正弦查找表计算反正弦的效率
我已经实现了一个查找表来计算系统中的正弦/余弦值。我现在需要反三角函数（arcsin/arccos）。
我的应用程序正在嵌入式设备上运行，由于程序内存有限，我无法在该设备上添加 arcsin 的第二个查找表。所以我想到的解决方案是浏览正弦查找表以检索相应的索引。
我想知道这个解决方案是否比使用来自数学标准库的标准实现更有效。
有人已经对此进行过实验吗？
LUT 当前的实现是一个从 0 到 PI/2 的正弦值数组。表中存储的值将乘以 4096，以保留对我的应用程序具有足够精度的整数值。查找表的分辨率为 1/4096，为我们提供了 6434 个值的数组。 然后我有两个函数 sine &余弦，以弧度角度乘以 4096 作为参数。这些函数将给定的角度转换为第一象限中相应的角度，并读取表中相应的值。
我的应用程序在 dsPIC33F 上以 40 MIPS 运行，我使用 C30 编译套件。
I have implemented a lookup table to compute sine/cosine values in my system. I now need inverse trigonometric functions (arcsin/arccos).
My application is running on an embedded device on which I can't add a second lookup table for arcsin as I am limited in program memory. So the solution I had in mind was to browse over the sine lookup table to retrieve the corresponding index.
I am wondering if this solution will be more efficient than using the standard implementation coming from the math standard library.
Has someone already experimented on this?
The current implementation of the LUT is an array of the sine values from 0 to PI/2. The value stored in the table are multiplied by 4096 to stay with integer values with enough precision for my application. The lookup table as a resolution of 1/4096 which give us an array of 6434 values.
Then I have two funcitons sine & cosine that takes an angle in radian multiplied by 4096 as argument. Those functions convert the given angle to the corresponding angle in the first quadrant and read the corresponding value in the table.
My application runs on dsPIC33F at 40 MIPS an I use the C30 compiling suite.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
由于你没有告诉我们有关硬件、编译器或你的代码的信息，所以很难肯定地说任何事情。但是，先验地，我希望编译器的标准库比您的代码更有效。
It's pretty hard to say anything with certainty since you have not told us about the hardware, the compiler or your code. However, a priori, I'd expect the standard library from your compiler to be more efficient than your code.
也许不幸的是，您必须使用不支持 C++ 的 C30 编译器，否则我会指出您 优化使用定点算术的数学密集型应用程序及其相关库。
然而，CORDIC 算法的一般原则适用，并且内存占用将远远小于您的内存占用目前的实施。该文章解释了 arctan() 的生成以及 arccos() 和 arcsin() 可以根据所述计算 这里。
当然，这也表明您还需要平方根和除法。尽管 PIC24/dsPIC 具有硬件整数除法，但这些可能会很昂贵。关于数学加速的文章也涉及平方根。您的查找表方法对于直接查找可能会更快，但对于反向搜索可能不会更快，但本文中解释的方法更通用且更精确（该库使用 64 位整数作为 36.28 位整数）定点，您可能会在应用程序中获得较低的精度和范围），并且肯定比使用软件浮点的标准库实现更快。
It is perhaps unfortunate that you have to use the C30 compiler which does not support C++, otherwise I'd point you to Optimizing Math-Intensive Applications with Fixed-Point Arithmetic and its associated library.
However the general principles of the CORDIC algorithm apply, and the memory footprint will be far smaller than your current implementation. The article explains the generation of arctan() and the arccos() and arcsin() can be calculated from that as described here.
Of course that suggests also that you will need square-root and division also. These may be expensive though PIC24/dsPIC have hardware integer division. The article on math acceleration deals with square-root also. It is likely that your look-up table approach will be faster for the direct look-up, but perhaps not for the reverse search, but the approaches explained in this article are more general and more precise (the library uses 64bit integers as 36.28 bit fixed point, you might get away with less precision and range in your application), and certainly faster than a standard library implementation using software-floating-point.
您可以使用“中途”方法，结合粗粒度查找表以节省内存，并结合中间值的数值近似值（例如 麦克劳林级数，比线性插值更准确。）
一些示例这里。
这个问题也有一些相关链接。
You can use a "halfway" approach, combining a coarse-grained lookup table to save memory, and a numeric approximation for the intermediate values (e.g. Maclaurin Series, which will be more accurate than linear interpolation.)
Some examples here.
This question also has some related links.
6434 的二分搜索将需要约 12 次查找才能找到该值，如果需要更高的精度，则随后进行插值。由于正弦曲线的性质，您将在一端获得比另一端更高的精度。如果您可以节省内存，那么在输入上均匀分布您自己的逆表可能是速度和准确性的更好选择。
就与内置版本的比较而言，您必须对其进行测试。执行此操作时，请注意图像尺寸增加了多少。在某些系统中，stdin 实现可能相当庞大。
A binary search of 6434 will take ~12 lookups to find the value, followed by an interpolation if more accuracy is needed. Due to the nature if the sin curve, you will get much more accuracy at one end than the other. If you can spare the memory, making your own inverse table evenly spaced on the inputs is likely a better bet for speed and accuracy.
In terms of comparison to the built-in version, you'll have to test that. When you do, pay attention to how much the size of your image increases. The stdin implementations can be pretty hefty in some systems.