在不使用 float 的情况下确定给定整数是否是 C 中斐波那契数列的元素
Determine if a given integer number is element of the Fibonacci sequence in C without using float
我最近参加了一次面试，失败了，最后被告知没有足够的经验为他们工作。
职位是嵌入式C软件开发人员。目标平台是某种非常简单的 32 位架构，那些处理器不支持浮点数及其运算。因此不能使用双精度和浮点数。
任务是为此体系结构开发 C 例程。这个 接受一个整数和 returns 无论它是否是斐波那契数 。但是，在执行期间，从内存 中只允许使用额外的 1K 临时空间 space 。这意味着：即使我模拟了非常大的整数，我也不能只是建立序列并进行交互。
据我所知，如果
之一，则正整数恰好是斐波那契数
(5n ^ 2) + 4
或
(5n ^ 2) − 4
是一个完美的正方形。所以我回答了这个问题：很简单，因为例程必须确定是否是这种情况。
然后他们回应：在当前的目标体系结构上，不支持类似浮点的操作，因此无法使用标准库的 sqrt 函数检索平方根数。还提到由于体系结构的限制，除法和模数等基本操作也可能无法正常工作。
然后我说，好吧，我们可以用直到 256 的平方数构建一个数组。然后我们可以遍历并将它们与公式给出的数字进行比较（见上文）。他们说：这是一个糟糕的方法，即使它会奏效。因此他们不接受那个答案。
最后我放弃了。因为我没有其他想法。我问，解决方案是什么：他们说，不会被告知；但建议我尝试自己寻找它。我的第一个方法（2公式）应该是关键，但平方根可以交替进行。
我在家里用谷歌搜索了很多，但从未找到任何 "alternative" 平方根计数器算法。到处都允许使用浮点数。
对于除法和取模等运算，可以使用所谓的"integer-division"。但是平方根要用什么？
即使我没有通过面试，这对我来说也是一个非常有趣的话题，在不允许浮点运算的架构上工作。
因此我的问题：
- 如何模拟浮点数（如果只允许使用整数）？
- 对于上述问题，C 中可能的解决方案是什么？欢迎使用代码示例。
这种面试的重点是看你如何处理新问题。如果您碰巧已经知道答案，那无疑是您的功劳，但它并不能真正回答问题。面试官感兴趣的是看着你解决问题。
出于这个原因，面试官通常会添加额外的限制，试图带您走出舒适区，看看您如何应对。
我认为您知道关于识别斐波那契数列的事实真是太好了。如果不查阅维基百科，我不会知道它。这是一个有趣的事实，但它真的有助于解决问题吗？
显然，有必要计算 5n²±4，计算平方根，然后验证其中一个是整数。通过以足够的精度访问浮点实现，这不会太复杂。但那有多少精度呢？如果 n 可以是任意的 32 位有符号数，那么 n² 显然不适合 32 位。事实上，5n²+4 可能有 65 位那么大，不包括符号位。这远远超出了 double（通常为 52 位）甚至 long double（如果可用）的精度。所以计算精确的平方根会有问题。
当然，我们实际上并不需要精确的计算。我们可以从一个近似值开始，计算它的平方，看看它是比 5n² 多四还是少四。而且很容易看出如何计算出一个好的猜测：它将非常接近 n×√5。通过使用 √5 的良好预计算近似值，我们可以轻松地进行此计算，而无需浮点数、除法和 sqrt 函数。 （如果近似值不准确，我们可能需要向上或向下调整结果，但是使用恒等式 (n+1)² = n²+2n+1 很容易做到；一旦我们有了 n²，我们就可以计算 (n+1)² 仅添加。
我们仍然需要解决精度问题，因此我们需要一些处理 66 位整数的方法。但是我们只需要实现正整数的加法和乘法，比成熟的 bignum 包要简单得多。事实上，如果我们能够证明我们的平方根估计足够接近，我们就可以安全地进行验证模 2³¹。
所以解析解可以起作用，但在深入研究之前，我们应该问一下它是否是最佳解。次优编程的一个非常常见的问题是拼命坚持你提出的第一个想法，即使它的复杂性变得越来越明显。这将是面试官想知道的关于你的事情之一：你在面对新信息或新要求时有多灵活。
那么还有什么其他方法可以知道 n 是否是斐波那契数。一个有趣的事实是，如果 n 是 Fib(k)，那么 k 是 log<sub>φ</sub>(k×√5 + 0.5)。由于 log<sub>φ</sub> 很容易从 log<sub>2</sub> 计算出来，这又可以通过简单的按位运算来近似，我们可以尝试找到 k 的近似值并使用经典的 O(log k) 递归计算 Fib(k) 来验证它。 None 以上涉及的数字大于 32 位有符号类型的容量。
更简单的是，我们可以 运行 循环遍历斐波那契数列，检查我们是否达到了目标数字。只需要 47 个循环。或者，这 47 个数字可以预先计算并使用二进制搜索进行搜索，使用远小于允许的 1k 字节。
编程职位的面试官不太可能测试斐波那契数列的特定 属性 知识。因此，除非他们提供 属性 进行测试，否则他们正在检查候选人解决此类问题的方法以及他们对算法的一般知识。值得注意的是，迭代 table 个正方形的想法在几个方面都没有得到很好的回应：
- 至少，二进制搜索应该是 table 查找的第一个想法。还可以提出一些计算查找方法供讨论，例如使用 find-first-set-bit 指令索引到 table.
- 散列可能是另一个值得考虑的想法，尤其是因为可以构建高效的自定义散列。
- 一旦我们决定使用 table，直接的 table 斐波那契数列可能比 table 正方形更有用。
我最近参加了一次面试，失败了，最后被告知没有足够的经验为他们工作。
职位是嵌入式C软件开发人员。目标平台是某种非常简单的 32 位架构，那些处理器不支持浮点数及其运算。因此不能使用双精度和浮点数。
任务是为此体系结构开发 C 例程。这个 接受一个整数和 returns 无论它是否是斐波那契数 。但是，在执行期间，从内存 中只允许使用额外的 1K 临时空间 space 。这意味着：即使我模拟了非常大的整数，我也不能只是建立序列并进行交互。
据我所知，如果
之一，则正整数恰好是斐波那契数(5n ^ 2) + 4
或
(5n ^ 2) − 4
是一个完美的正方形。所以我回答了这个问题：很简单，因为例程必须确定是否是这种情况。
然后他们回应：在当前的目标体系结构上，不支持类似浮点的操作，因此无法使用标准库的 sqrt 函数检索平方根数。还提到由于体系结构的限制，除法和模数等基本操作也可能无法正常工作。
然后我说，好吧，我们可以用直到 256 的平方数构建一个数组。然后我们可以遍历并将它们与公式给出的数字进行比较（见上文）。他们说：这是一个糟糕的方法，即使它会奏效。因此他们不接受那个答案。
最后我放弃了。因为我没有其他想法。我问，解决方案是什么：他们说，不会被告知；但建议我尝试自己寻找它。我的第一个方法（2公式）应该是关键，但平方根可以交替进行。
我在家里用谷歌搜索了很多，但从未找到任何 "alternative" 平方根计数器算法。到处都允许使用浮点数。
对于除法和取模等运算，可以使用所谓的"integer-division"。但是平方根要用什么？
即使我没有通过面试，这对我来说也是一个非常有趣的话题，在不允许浮点运算的架构上工作。
因此我的问题：
- 如何模拟浮点数（如果只允许使用整数）？
- 对于上述问题，C 中可能的解决方案是什么？欢迎使用代码示例。
这种面试的重点是看你如何处理新问题。如果您碰巧已经知道答案，那无疑是您的功劳，但它并不能真正回答问题。面试官感兴趣的是看着你解决问题。
出于这个原因，面试官通常会添加额外的限制，试图带您走出舒适区，看看您如何应对。
我认为您知道关于识别斐波那契数列的事实真是太好了。如果不查阅维基百科，我不会知道它。这是一个有趣的事实，但它真的有助于解决问题吗？
显然，有必要计算 5n²±4，计算平方根，然后验证其中一个是整数。通过以足够的精度访问浮点实现，这不会太复杂。但那有多少精度呢？如果 n 可以是任意的 32 位有符号数，那么 n² 显然不适合 32 位。事实上，5n²+4 可能有 65 位那么大，不包括符号位。这远远超出了 double（通常为 52 位）甚至 long double（如果可用）的精度。所以计算精确的平方根会有问题。
当然，我们实际上并不需要精确的计算。我们可以从一个近似值开始，计算它的平方，看看它是比 5n² 多四还是少四。而且很容易看出如何计算出一个好的猜测：它将非常接近 n×√5。通过使用 √5 的良好预计算近似值，我们可以轻松地进行此计算，而无需浮点数、除法和 sqrt 函数。 （如果近似值不准确，我们可能需要向上或向下调整结果，但是使用恒等式 (n+1)² = n²+2n+1 很容易做到；一旦我们有了 n²，我们就可以计算 (n+1)² 仅添加。
我们仍然需要解决精度问题，因此我们需要一些处理 66 位整数的方法。但是我们只需要实现正整数的加法和乘法，比成熟的 bignum 包要简单得多。事实上，如果我们能够证明我们的平方根估计足够接近，我们就可以安全地进行验证模 2³¹。
所以解析解可以起作用，但在深入研究之前，我们应该问一下它是否是最佳解。次优编程的一个非常常见的问题是拼命坚持你提出的第一个想法，即使它的复杂性变得越来越明显。这将是面试官想知道的关于你的事情之一：你在面对新信息或新要求时有多灵活。
那么还有什么其他方法可以知道 n 是否是斐波那契数。一个有趣的事实是，如果 n 是 Fib(k)，那么 k 是 log<sub>φ</sub>(k×√5 + 0.5)。由于 log<sub>φ</sub> 很容易从 log<sub>2</sub> 计算出来，这又可以通过简单的按位运算来近似，我们可以尝试找到 k 的近似值并使用经典的 O(log k) 递归计算 Fib(k) 来验证它。 None 以上涉及的数字大于 32 位有符号类型的容量。
更简单的是，我们可以 运行 循环遍历斐波那契数列，检查我们是否达到了目标数字。只需要 47 个循环。或者，这 47 个数字可以预先计算并使用二进制搜索进行搜索，使用远小于允许的 1k 字节。
编程职位的面试官不太可能测试斐波那契数列的特定 属性 知识。因此，除非他们提供 属性 进行测试，否则他们正在检查候选人解决此类问题的方法以及他们对算法的一般知识。值得注意的是，迭代 table 个正方形的想法在几个方面都没有得到很好的回应：
- 至少，二进制搜索应该是 table 查找的第一个想法。还可以提出一些计算查找方法供讨论，例如使用 find-first-set-bit 指令索引到 table.
- 散列可能是另一个值得考虑的想法，尤其是因为可以构建高效的自定义散列。
- 一旦我们决定使用 table，直接的 table 斐波那契数列可能比 table 正方形更有用。