为什么在实践中不使用斐波那契数列的封闭形式？
Why is closed form for fibonacci sequence not used in practice?
斐波那契数列有一个封闭形式，可以通过generating functions获得。它是：
f_n = 1/sqrt(5) (phi^n-\psi^n)
有关术语的含义，请参阅上面的 link 或 here。
但是，有人讨论 here 这种封闭形式并没有真正在实践中使用，因为当 n 变得大约一百或更大时，它开始产生错误的答案。
但在答案here中，似乎采用的方法之一是快速矩阵求幂，可用于在 O(log(n)) 时间内非常有效地获得第 n 个斐波那契数。
但是，封闭式表达式涉及一堆 n 次方的项。因此，您可以通过快速取幂计算所有这些项，并以这种方式有效地获得结果。为什么对矩阵进行快速求幂比对出现在封闭形式表达式中的标量进行求幂更好？此外，寻找如何有效地对矩阵进行快速求幂，接受的答案 here 建议我们转换为对角线形式并在标量上进行。
那么问题是 - 如果矩阵的快速求幂有利于在 O(log(n)) 时间内计算第 n 个斐波那契数，那么当它涉及标量的快速取幂？
请注意，此处的“实践”指的是竞争性编程（实际上，您基本上永远不想计算大量的斐波那契数）。因此，第一个原因是计算斐波那契数的正常方法输入速度更快，不会出错，而且代码更少。另外，对于小数字，它会比奇特的方法更快。
当涉及大数时，如果您不关心精度，快速矩阵乘法是 O(log(n))。然而，在竞争性编程中，我们几乎总是关心精度并想要正确答案。为此，我们需要提高数字的精度。 n 越大，要求的精度就越高。我不知道确切的公式，但我可以想象，由于需要更高的精度，只需要 O(log n) 乘法的矩阵乘法将需要类似 O(log n) 位的精度，因此时间复杂度将实际上最终有点糟糕（O（log ^ 3 n）也许？）。更不用说，更难编码而且非常慢，因为你乘以任意精度的数字。
用于计算斐波那契数列的“封闭式”公式，您需要对无理数进行 n 次幂，这意味着您必须接受仅使用近似值（通常，双-精度浮点运算），因此对于大数结果不准确。
相反，在计算斐波那契数列的“矩阵求幂”公式中，你求幂的矩阵n是一个整数矩阵，所以你可以做整数使用“big int”库对任意大整数进行算术运算而不损失精度（或者如果你使用像 Python 这样的语言，“big ints”是默认值）。
所以不同之处在于，您不能对无理数进行精确算术运算，但可以对整数进行运算。
斐波那契数列有一个封闭形式，可以通过generating functions获得。它是：
f_n = 1/sqrt(5) (phi^n-\psi^n)
有关术语的含义，请参阅上面的 link 或 here。
但是，有人讨论 here 这种封闭形式并没有真正在实践中使用，因为当 n 变得大约一百或更大时，它开始产生错误的答案。
但在答案here中，似乎采用的方法之一是快速矩阵求幂，可用于在 O(log(n)) 时间内非常有效地获得第 n 个斐波那契数。
但是，封闭式表达式涉及一堆 n 次方的项。因此，您可以通过快速取幂计算所有这些项，并以这种方式有效地获得结果。为什么对矩阵进行快速求幂比对出现在封闭形式表达式中的标量进行求幂更好？此外，寻找如何有效地对矩阵进行快速求幂，接受的答案 here 建议我们转换为对角线形式并在标量上进行。
那么问题是 - 如果矩阵的快速求幂有利于在 O(log(n)) 时间内计算第 n 个斐波那契数，那么当它涉及标量的快速取幂？
请注意，此处的“实践”指的是竞争性编程（实际上，您基本上永远不想计算大量的斐波那契数）。因此，第一个原因是计算斐波那契数的正常方法输入速度更快，不会出错，而且代码更少。另外，对于小数字，它会比奇特的方法更快。
当涉及大数时，如果您不关心精度，快速矩阵乘法是 O(log(n))。然而，在竞争性编程中，我们几乎总是关心精度并想要正确答案。为此，我们需要提高数字的精度。 n 越大，要求的精度就越高。我不知道确切的公式，但我可以想象，由于需要更高的精度，只需要 O(log n) 乘法的矩阵乘法将需要类似 O(log n) 位的精度，因此时间复杂度将实际上最终有点糟糕（O（log ^ 3 n）也许？）。更不用说，更难编码而且非常慢，因为你乘以任意精度的数字。
用于计算斐波那契数列的“封闭式”公式，您需要对无理数进行 n 次幂，这意味着您必须接受仅使用近似值（通常，双-精度浮点运算），因此对于大数结果不准确。
相反，在计算斐波那契数列的“矩阵求幂”公式中，你求幂的矩阵n是一个整数矩阵，所以你可以做整数使用“big int”库对任意大整数进行算术运算而不损失精度（或者如果你使用像 Python 这样的语言，“big ints”是默认值）。
所以不同之处在于，您不能对无理数进行精确算术运算，但可以对整数进行运算。