qua*_*231 0 embedded floating-point
我在上次采访中被问到这个问题并再次期待它.采访是针对嵌入式系统编程的固件工程师.可用于这些应用的微处理器和微控制器通常不是很强大,而较简单的微控制器和微控制器没有能力进行浮点计算(内部没有乘法器或分频器).
那么这个问题的可能答案是什么,以及定点运算与此有什么关系？
是否可以使用Newton-Raphson方法进行此计算？怎么样？
和任何这样的面试问题一样,聪明的回答就是提出反问题.旨在澄清和消除问题的明智问题表明,您可以思考而不是简单地兜售所接受的智慧或教条,并且还会缩小问题的范围,以便您的答案更适合应用.在这种情况下,没有浮点的MCU和不使用浮点的软件实现之间可能存在区别.如果是后者,那么肯定定点是相关的,但在许多应用中,整数平方根可能就足够了 - 你可能会问这个问题,但isqrt(2)== 1在这种情况下似乎是不合适的.对于前者,这种情况并不排除使用浮点.
通常,使用浮点时嵌入式系统中的问题是缺少浮点单元(FPU),导致在软件中实现的浮点运算要慢得多且不太确定.缺少FPU甚至硬件整数乘法或除法并不排除使用浮点,它只是意味着这样的操作要慢得多并且需要更大的代码空间.
在大多数系统中,即使没有硬件浮点支持,标准库数学函数仍然可以由软件浮点支持,并且可以正常使用 - 即使在8位系统上 - 但是不要期望Mega-FLOPS性能.在某些情况下,性能损失以及可能的库实现的非确定性本质会妨碍其使用,在这种情况下,有许多算法会返回更快或更确定的性能.
如果要生根的值很大且整数结果足够精确,那么纯整数解决方案将是最快的,但是对于一般情况,有一些解决方案,其中Newton-Raphson是一个,但不太可能是最优的 - 它更像是泡泡式的平方根算法 ; 之所以使用是因为它易于教导和理解,而不是因为它的性能.
使用固定点是可能的,但不是固有的数据类型,代码可能变得不那么容易编写和调试.我使用安东尼威廉姆斯写的图书馆 ; 它是用C++编写的并定义了一个fixed类; C++的函数和运算符重载功能意味着大多数浮点代码只需通过替换float或double使用即可移植fixed.在ARM处理器上,fixed该类的执行速度比软件浮点快约五倍.然而,安东尼的sqrt算法可以改进,正如我在这里所描述的那样,基于文章"被忽略的固定点算术的艺术"的实现 - 该文章中的代码在C中,因此可能更普遍适用(C++不可用或者不实际 - 虽然这是一个不同的论点!).
Jack Crenshaw在他的" 实时编程数学工具包 "(Math Toolkit for Real-Time Programming)一书中专门讨论了sqrt()函数,他开始使用一个天真的Newton-Raphson实现并逐步完善它.他也提出了一个整数解决方案,虽然有趣的是不是定点.杰克在书中所包含的一些内容已经出现在他的期刊文章中; 例如他对整数平方根的处理.
不管怎样,我可以回答如下问题:
我会评估标准库软件的浮点性能,精度和对代码大小的影响,并且只有当我发现它不适合应用程序需求时才会考虑使用已建立的算法和可能的定点算法的优化解决方案.
注意我使用术语"已建立的算法" ; 它有用的事实是我可能不知道或回想起任何特定算法的名称,我真正说的是我不知道什么算法是合适的但我不愚蠢重新发明轮子,因为我不太可能想出一些比现有的东西更好的东西,通过仔细的研究和评估,如果可行的话,我会达到预期的效果.如果一位受访者提出了这个答案并提出了明智的问题,我会发现这不仅仅是可以接受的.当然,面试官可能不像你那么聪明,并且可能有一个特别的答案,他认为他是" 正确的 "; 你可能不想在一个有这种教条反应的组织中工作.面试是一个双向的过程 - 您正在面试组织,看看您是否想要提供服务的好处.