バックグラウンド：
著者が最初に他の多くの言語でタグ付けしたが、後にHaskellの質問に焦点を合わせたとき、私はこの質問を見ることに「引きずり込まれ」
ました。
残念ながら、私はHaskellの経験がまったくないので、質問に実際に参加することができませんでした。しかし、答えの1つが私の目に留まり、答え者はそれを純粋な整数の数学の問題に変えました。それは素晴らしかった私にとっては、それがどのように機能するかを理解し、これを再帰的なフィボナッチの実装と比較して、それがどれほど正確であるかを確認する必要がありました。無理数を含む関連する数学を思い出せば、自分ですべてを解決できるかもしれないと感じています（しかし、私はそうしません）。ですから、私にとっての最初のステップは、それを私が精通している言語に移植することでした。この場合、私は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は2つのパラメーターを持つコンストラクターで型を宣言します（そして型/モジュールIntegerを継承すると思います）。EqShow
次は、Extから「派生」する実装ですNum。 fromIntegerからの変換を実行しIntegerます。 negateは単項否定であり、次に2進加算および乗算演算子があります。
最後の部分は、実際のフィボナッチの実装です。
質問：
回答の中で、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。
ものすごく単純。3乗twoPhiしnます。それから残りの結果を引きます。ここではバイナリ減算を行っていますが、単項否定のみを実装しました。それとも私たちはしませんでしたか？または、加算と否定（私たちが持っている）を組み合わせて構成することができるので、バイナリ減算を暗示することができますか？私は後者を想定しています。そして、これは否定についての私の不確実性を和らげます。
最後の部分は実際の分割です：
divide (Ext 0 b) = b `div` 2^n。ここで2つの懸念。私が見つけたところによると、除算演算子はなく、`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);
}
}
そして、これが完全に更新されたソースです。