有关 Haskell -> C# 转换的问题

>Background：

我被"拖"进了这个问题：哈斯克尔
中的斐波那契闭式表达式当作者最初用许多其他语言标记，但后来专注于Haskell问题时。 不幸的是，我对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

因此，根据我的研究和我可以推断的内容（如果我在任何地方都错了，请纠正我），第一部分使用具有两个Integer参数的构造函数声明类型 Ext（我猜将继承Eq和Show类型/模块）。

接下来是从Num"派生"的Ext的实现。 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次方。 从中减去其余的结果。 在这里，我们做二进制减法，但我们只实现了一元否定。 还是我们没有？ 或者二进制减法可以隐含，因为它可以组合加法和否定（我们有）？ 我假设是后者。 这减轻了我对否定的不确定性。

---

最后一部分是实际划分：divide (Ext 0 b) = b `div` 2^n . 这里有两个问题。 据我所知，没有除法运算符，只有一个`div`函数。 所以我只需要在这里划分数字。 这是对的吗？ 还是有一个除法运算符，但有一个单独的`div`函数可以做其他特殊的事情？

我不知道如何解释行的开头。 这只是一个简单的模式匹配吗？ 换句话说，这仅适用于第一个参数是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);
    }
}

这是完全更新的来源。

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

(^) :: (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)

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();
}