14

背景:

当作者最初用许多其他语言标记但后来专注于 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参数的构造函数声明类型(我猜将继承EqShow类型/模块)。

接下来是Extwhich "派生" from的实现NumfromInteger从 执行转换Integernegate是一元否定,然后是二元加法和乘法运算符。

最后一部分是实际的斐波那契实现。

问题:

在答案中,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。

很简单。提高twoPhinth 次幂。从中减去其余的结果。在这里,我们正在做二进制减法,但我们只实现了一元否定。还是我们没有?或者是否可以隐含二进制减法,因为它可以由加法和否定(我们有)组合而成?我假设后者。这减轻了我对否定的不确定性。


最后一部分是实际的划分: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);
    }
}

这是完全更新的来源

4

3 回答 3

9

[...],第一部分使用一个构造函数声明 Ext 类型,该构造函数将具有两个 Integer 参数(我猜将继承 Eq 和 Show 类型/模块)。

Eq并且Show类型类。您可以将它们视为类似于 C# 中的接口,只是功能更强大。deriving是一种构造,可用于为少数标准类型类(包括EqShow等)自动生成实现Ord。这减少了您必须编写的样板数量。

instance Num Ext部分提供了Num类型类的显式实现。这部分的大部分内容你都做对了。

[回答者] 提到求幂是由 Num 中的默认实现处理的。但这意味着什么以及它如何实际应用于这种类型?是否有我遗漏的隐含数字“字段”?它是否只是将幂运算应用于它包含的每个相应数字?

这对我来说有点不清楚。^不在类型类Num中,而是完全按照Num方法定义的辅助函数,有点像扩展方法。它通过二进制取幂实现对正整数幂的取幂。这是代码的主要“技巧”。

[...] 我们正在做二进制减法,但我们只实现了一元否定。还是我们没有?或者是否可以隐含二进制减法,因为它可以由结合加法和否定(我们有)组成?

正确的。二进制减号的默认实现是x - y = x + (negate y).

最后一部分是实际的划分:divide (Ext 0 b) = b `div` 2^n. 这里有两个问题。根据我的发现,没有除法运算符,只有一个 div 函数。所以我只需要在这里划分数字。这个对吗?或者是否有一个除法运算符,但有一个单独的 div 函数可以做其他特别的事情?

Haskell 中的运算符和函数之间只有句法上的区别。可以通过将运算符写成圆括号将其视为函数(+),或者将函数写成 将其视为二元运算符`backticks`

div是整数除法,属于类型类Integral,所以它是为所有类整数类型定义的,包括Int(机器大小的整数)和Integer(任意大小的整数)。

我不确定如何解释该行的开头。它只是一个简单的模式匹配吗?换句话说,这是否仅适用于第一个参数为 0 的情况?如果不匹配(第一个非零),结果会是什么?或者我应该解释它,因为我们不关心第一个参数并无条件地应用函数?

提取√5的系数确实只是一个简单的模式匹配。整数部分与零匹配,以向读者表达我们确实希望它始终为零,并且如果代码中的某些错误导致程序不为零,则使程序崩溃。


一个小小的改进

在原始代码中替换Integer为,您可以编写更接近Binet 的公式Rationalfib n

fib n = divSq5 $ phi^n - (1-phi)^n
  where divSq5 (Ext 0 b) = numerator b
        phi = Ext (1/2) (1/2)

这会在整个计算过程中执行除法,而不是将其全部保存到最后。这导致计算fib (10^6).

于 2011-05-21T19:23:05.447 回答
8

首先,,Num是类型类,而不是类型或模块。它们有点类似于 C# 中的接口,但是是静态解析而不是动态解析的。ShowEq

其次,求幂是通过与 的实现相乘来执行的^,它不是类型类的成员Num,而是一个单独的函数。

实现如下:

(^) :: (Num a, Integral b) => a -> b -> a
x0 ^ y0 | y0 < 0    = error "Negative exponent"
        | y0 == 0   = 1
        | otherwise = f x0 y0
    where -- f : x0 ^ y0 = x ^ y
          f x y | even y    = f (x * x) (y `quot` 2)
                | y == 1    = x
                | otherwise = g (x * x) ((y - 1) `quot` 2) x
          -- g : x0 ^ y0 = (x ^ y) * z
          g x y z | even y = g (x * x) (y `quot` 2) z
                  | y == 1 = x * z
                  | otherwise = g (x * x) ((y - 1) `quot` 2) (x * z)

这似乎是解决方案中缺少的部分。

你是对的减法。它是通过加法和否定来实现的。

现在,该divide函数仅在a等于 0 时进行除法。否则我们会遇到模式匹配失败,表明程序中存在错误。

div函数是一个简单的整数除法,相当于/在C#中应用于整数类型。Haskell中也有运算符/,但它表示实数除法。

于 2011-05-21T15:26:29.887 回答
4

C# 中的快速实现。我使用平方和乘法算法实现了求幂。

a+b*Sqrt(5)将这种具有形式的类型与具有形式的复数进行比较是很有启发性的a+b*Sqrt(-1)。加法和减法的工作原理相同。乘法略有不同,因为 i^2 在这里不是 -1 而是 +5。除法稍微复杂一些,但也不应该太难。

求幂定义为将一个数与自身相乘 n 次。但这当然很慢。所以我们使用与平方和乘法算法((a*a)*a)*a相同的事实来重写。(a*a)*(a*a)所以我们只需要log(n)乘法而不是n乘法。

仅计算单个组件的指数是行不通的。那是因为您的类型背后的矩阵不是对角线。将此与复数的性质进行比较。您不能简单地分别计算实部和虚部的指数。

struct MyNumber
{
    public readonly BigInteger Real;
    public readonly BigInteger Sqrt5;

    public MyNumber(BigInteger real,BigInteger sqrt5)
    {
        Real=real;
        Sqrt5=sqrt5;
    }

    public static MyNumber operator -(MyNumber left,MyNumber right)
    {
        return new MyNumber(left.Real-right.Real, left.Sqrt5-right.Sqrt5);
    }

    public static MyNumber operator*(MyNumber left,MyNumber right)
    {
        BigInteger real=left.Real*right.Real + left.Sqrt5*right.Sqrt5*5;
        BigInteger sqrt5=left.Real*right.Sqrt5 + right.Real*left.Sqrt5;
        return new MyNumber(real,sqrt5);
    }

    public static MyNumber Power(MyNumber b,int exponent)
    {
        if(!(exponent>=0))
            throw new ArgumentException();
        MyNumber result=new MyNumber(1,0);
        MyNumber multiplier=b;
        while(exponent!=0)
        {
            if((exponent&1)==1)//exponent is odd
                result*=multiplier;
            multiplier=multiplier*multiplier;
            exponent/=2;
        }
        return result;
    }

    public override string ToString()
    {
        return Real.ToString()+"+"+Sqrt5.ToString()+"*Sqrt(5)";
    }
}

BigInteger Fibo(int n)
{
    MyNumber num = MyNumber.Power(new MyNumber(1,1),n)-MyNumber.Power(new MyNumber(1,-1),n);
    num.Dump();
    if(num.Real!=0)
      throw new Exception("Asser failed");
    return num.Sqrt5/BigInteger.Pow(2,n);
}

void Main()
{
  MyNumber num=new MyNumber(1,2);
  MyNumber.Power(num,2).Dump();
  Fibo(5).Dump();
}
于 2011-05-21T15:44:10.017 回答