0

I got asked this question last interview and expect it again. The interview was for firmware engineer that program embedded systems. The microprocessors and micro controllers available for these applications are not very powerful usually and the simpler ones do not have capability to do floating point calculations (no multiplier or divider present inside).

So what are the possible answers to this question than and what (if anything) does fixed point arithmetic have to do with this?

Is it possible to use the Newton-Raphson method to do this calculation at all? How?

4

3 回答 3

9

与任何诸如此类的面试问题一样,明智的反应是提出反问。旨在澄清和消除问题的聪明问题表明您可以思考而不是简单地喷出所接受的智慧或教条,并且还会缩小问题的范围,使您的答案更可能适用。在这种情况下,没有浮点的MCU不使用浮点的软件实现之间可能存在区别。如果是后者,那么定点肯定是相关的,但在许多应用中是整数平方root 可能就足够了 - 您可能会问这个问题,但在这种情况下, isqrt(2) == 1 似乎不太可能足够。对于前者,这种情况并不排除使用浮点数。

通常,嵌入式系统中使用浮点时的问题是缺少浮点单元 (FPU),从而导致在软件中实现的浮点运算要慢得多且确定性较差。缺少 FPU 甚至硬件整数乘法或除法并不排除使用浮点,它只是意味着此类操作要慢得多并且需要更大的代码空间。

在大多数系统上,即使没有硬件浮点支持,标准库数学函数仍然会受到软件浮点的支持,并且可以正常使用——即使在 8 位系统上——但不要指望Mega-FLOPS性能。在某些情况下,性能下降以及库实现的不确定性可能会阻止其使用,在这种情况下,有许多算法可以返回更快或更确定性的性能。

如果要求根的值很大并且整数结果足够精确,那么纯整数解决方案将是最快的,但是对于一般情况,有许多解决方案,其中 Newton-Raphson 是其中之一,但不太可能是最优的 -它是平方根算法的冒泡算法;使用它是因为它易于教授和理解,而不是因为它的性能。

使用定点是可能的,但不是内在数据类型,代码可能变得不那么容易编写和调试。我使用Anthony Williams 编写的库;它是用 C++ 编写的并定义了一个fixed类;C++ 的函数和运算符重载能力意味着大多数浮点代码可以简单地通过替换floatdouble来移植fixed。在 ARM 处理器上,fixed该类的执行速度大约是软件浮点的五倍。然而,Anthony 的 sqrt 算法可以改进,正如我在这里描述的那样,使用基于文章The Neglected Art of Fixed Point Arithmetic的实现- 那篇文章中的代码是用 C 语言编写的,因此可能更普遍适用(其中 C++ 不可用或不实用 - 尽管这是一个不同的论点!)。

Jack Crenshaw 在他的《用于实时编程的数学工具包》一书中用了一整章的篇幅介绍了 sqrt() 函数,他从一个朴素的 Newton-Raphson 实现开始并逐渐对其进行改进。他还提出了一个整数解,但有趣的是不是定点的。杰克在书中包含的一些内容已经出现在他的期刊文章中;例如他对整数平方根的处理。

无论哪种方式,我都可以这样回答这个问题:

我会评估标准库软件的浮点性能、精度和对代码大小的影响,只有当我发现它不足以满足应用程序要求时,我才会考虑使用已建立的算法和可能的定点算术的优化解决方案。

请注意我使用的术语“既定算法”;它有效地忽略了这样一个事实,即我可能不知道或不记得任何特定算法的名称,而我真正想说的是我不知道哪种算法是合适的,但我没有愚蠢到重新发明轮子,因为我不太可能想出比目前还没有的东西更好的东西,并且通过仔细的研究和评估,如果可行的话,我会达到预期的结果。如果一位受访者事先提出了这个答案并提出了一些聪明的问题,我会发现这完全可以接受。当然,面试官可能没有你那么聪明,而且心里可能有一个他认为“正确”的答案“一;你可能不想在一个有这种教条反应的组织中工作。面试是一个双向的过程——你正在面试这个组织,看看你是否想给你的服务带来好处。

于 2012-09-02T10:12:52.467 回答
4

是的,您可以使用 Newton-Raphson 计算平方根。通常它是这样完成的:

设 x 为数字。我们将首先近似 1/sqrt(x),然后将其乘以 x 以产生 x/sqrt(x),即 sqrt(x)。

给定 x,创建 1/sqrt(x) 的粗略估计。通常,这是通过一个小的查找表来完成的,但任何合理的估计就足够了(包括 1)。调用初始估计 e 0

根据需要重复此步骤多次:根据当前估计值 e i,创建新估计值 e i+1 = 1/2·e i ·(3−x·e i 2 )。通常,所需的步数可以通过数值分析、1/sqrt(x) 的初始估计的质量以及应用程序所需的精度提前确定。

最后,返回最后一个 e i ·x 以估计 sqrt(x)。

该序列收敛速度非常快,通常用于计算平方根。您可以从牛顿方法的维基百科页面开始,了解如何推导出平方根倒数的序列。另请注意,它不使用除法,这通常是一个缓慢的操作。

您将使用定点进行这些计算,因为您需要比整数提供的精度更高的精度,但浮点不可用。

本质上,面试官是想看看你是否有嵌入式处理器上的数值算法经验。

于 2012-09-01T23:44:20.877 回答
3

ENIAC 仅使用加法和减法计算平方根。它基于公式,前n个奇数之和是n的平方。

要计算 m 的平方根,求前 n 个奇数之和超过 m 的最小整数 n。这可以通过从 m 中减去连续的奇数整数来完成,直到获得负结果。如果 n 是最小整数,m - (1 + 3 + 5 + ... + 2n-1) < 0(n - 1)^2 <= m < n^2. 令 a 等于第 n 个奇数,求解2n - 1双不等式(n-1) <= sqrt(m) < n

a - 1 <= 2*sqrt(m) < a + 1

或者

(a - 1)/2 <= sqrt(m) < (a + 1)/2

资料来源: http ://www4.wittenberg.edu/academics/mathcomp/bjsdir/ENIACSquareRoot.htm

但是,这实际上不适用于 m = 2,仅适用于大数。

于 2012-09-01T21:44:05.873 回答