背景：
当作者最初用许多其他语言标记但后来专注于 Haskell 问题时，我被“拖”到看到这个问题：
Haskell 中的 Fibonacci's Closed-form expression 。
不幸的是，我对 Haskell 没有任何经验，所以我无法真正参与这个问题。然而，其中一个答案引起了我的注意，回答者将其变成了一个纯整数数学问题。听起来棒极了对我来说，所以我必须弄清楚它是如何工作的，并将其与递归斐波那契实现进行比较，看看它有多准确。我有一种感觉，如果我只记得涉及无理数的相关数学，我可能能够自己解决所有问题（但我没有）。所以对我来说，第一步是将它移植到我熟悉的语言上。在这种情况下，我正在做 C#。
幸运的是，我并没有完全蒙在鼓里。我在另一种函数式语言 (OCaml) 方面有丰富的经验，所以其中很多对我来说看起来有些熟悉。从转换开始，一切看起来都很简单，因为它基本上定义了一个新的数字类型来帮助计算。但是，我在翻译过程中遇到了一些障碍，无法完成。我得到完全错误的结果。
分析：
这是我正在翻译的代码：
data Ext = Ext !Integer !Integer
deriving (Eq, Show)
instance Num Ext where
fromInteger a = Ext a 0
negate (Ext a b) = Ext (-a) (-b)
(Ext a b) + (Ext c d) = Ext (a+c) (b+d)
(Ext a b) * (Ext c d) = Ext (a*c + 5*b*d) (a*d + b*c) -- easy to work out on paper
-- remaining instance methods are not needed
fib n = divide $ twoPhi^n - (2-twoPhi)^n
where twoPhi = Ext 1 1
divide (Ext 0 b) = b `div` 2^n -- effectively divides by 2^n * sqrt 5
因此，根据我的研究和我可以推断的内容（如果我在任何地方错了，请纠正我），第一部分Ext使用具有两个Integer参数的构造函数声明类型（我猜将继承Eq和Show类型/模块）。
接下来是Extwhich "派生" from的实现Num。 fromInteger从 执行转换Integer。 negate是一元否定，然后是二元加法和乘法运算符。
最后一部分是实际的斐波那契实现。
问题：
在答案中，hammar（回答者）提到求幂由Num. 但这意味着什么以及它如何实际应用于这种类型？是否有我遗漏的隐含数字“字段”？它是否只是将幂运算应用于它包含的每个相应数字？我假设它是后者并最终得到这个 C# 代码：
public static Ext operator ^(Ext x, int p) // "exponent"
{
// just apply across both parts of Ext?
return new Ext(BigInt.Pow(x.a, p), BigInt.Pow(x.b, p));
// Ext (a^p) (b^p)
}
然而，这与我对为什么negate需要的理解相冲突，如果这真的发生，它就不需要它。
现在是代码的肉。我将第一部分读
divide $ twoPhi^n - (2-twoPhi)^n为：
将以下表达式的结果相除：twoPhi^n - (2-twoPhi)^n。
很简单。提高twoPhi到nth 次幂。从中减去其余的结果。在这里，我们正在做二进制减法，但我们只实现了一元否定。还是我们没有？或者是否可以隐含二进制减法，因为它可以由加法和否定（我们有）组合而成？我假设后者。这减轻了我对否定的不确定性。
最后一部分是实际的划分：
divide (Ext 0 b) = b `div` 2^n. 这里有两个问题。根据我的发现，没有除法运算符，只有一个`div`函数。所以我只需要在这里划分数字。这个对吗？或者是否有一个除法运算符，但有一个单独的`div`函数来做其他特别的事情？
我不确定如何解释该行的开头。它只是一个简单的模式匹配吗？换句话说，这只适用于第一个参数是 a 的情况0吗？如果不匹配（第一个非零），结果会是什么？或者我应该解释它，因为我们不关心第一个参数并无条件地应用函数？这似乎是最大的障碍，使用任何一种解释仍然会产生不正确的结果。
我有没有在任何地方做出错误的假设？还是没关系，我只是错误地实现了 C#？
代码：
这是到目前为止的（非工作）翻译和 完整的源代码（包括测试），以防万一有人感兴趣。
// code removed to keep post size down
// full source still available through link above
进步：
好的，所以看看到目前为止的答案和评论，我想我知道从这里去哪里以及为什么。
取幂只需要做它通常做的事情，p在我们已经实现乘法运算的情况下乘以时间。我从来没有想过我们应该做数学课一直告诉我们做的事情。加法和否定的隐含减法也是一个非常方便的功能。
在我的实现中还发现了一个错字。我应该在我应该成倍增加的时候添加。
// (Ext a b) * (Ext c d) = Ext (a*c + 5*b*d) (a*d + b*c)
public static Ext operator *(Ext x, Ext y)
{
return new Ext(x.a * y.a + 5*x.b*y.b, x.a*y.b + x.b*y.a);
// ^ oops!
}
结论：
所以现在已经完成了。我只对基本操作员进行了实施，并对其进行了一些重命名。以与复数类似的方式命名。到目前为止，与递归实现一致，即使输入非常大。这是最终的代码。
static readonly Complicated TWO_PHI = new Complicated(1, 1);
static BigInt Fib_x(int n)
{
var x = Complicated.Pow(TWO_PHI, n) - Complicated.Pow(2 - TWO_PHI, n);
System.Diagnostics.Debug.Assert(x.Real == 0);
return x.Bogus / BigInt.Pow(2, n);
}
struct Complicated
{
private BigInt real;
private BigInt bogus;
public Complicated(BigInt real, BigInt bogus)
{
this.real = real;
this.bogus = bogus;
}
public BigInt Real { get { return real; } }
public BigInt Bogus { get { return bogus; } }
public static Complicated Pow(Complicated value, int exponent)
{
if (exponent < 0)
throw new ArgumentException(
"only non-negative exponents supported",
"exponent");
Complicated result = 1;
Complicated factor = value;
for (int mask = exponent; mask != 0; mask >>= 1)
{
if ((mask & 0x1) != 0)
result *= factor;
factor *= factor;
}
return result;
}
public static implicit operator Complicated(int real)
{
return new Complicated(real, 0);
}
public static Complicated operator -(Complicated l, Complicated r)
{
var real = l.real - r.real;
var bogus = l.bogus - r.bogus;
return new Complicated(real, bogus);
}
public static Complicated operator *(Complicated l, Complicated r)
{
var real = l.real * r.real + 5 * l.bogus * r.bogus;
var bogus = l.real * r.bogus + l.bogus * r.real;
return new Complicated(real, bogus);
}
}
这是完全更新的来源。