背景:
当作者最初用许多其他语言标记但后来专注于 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
类型/模块)。
接下来是Ext
which "派生" 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
到n
th 次幂。从中减去其余的结果。在这里,我们正在做二进制减法,但我们只实现了一元否定。还是我们没有?或者是否可以隐含二进制减法,因为它可以由加法和否定(我们有)组合而成?我假设后者。这减轻了我对否定的不确定性。
最后一部分是实际的划分:
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);
}
}
这是完全更新的来源。