こんにちは．
「Fibonacci 数列の一般項を使って計算してみた（けど，浮動小数点数の誤差により正確には求まらなかった）」というようなツイートを見かけて，この記事を思いつきました．
Fibonacci 数列について今更説明する必要はないとは思いますが，
\begin{cases}
\mathrm{fib}_0 = 0, \\
\mathrm{fib}_1 = 1, \\
\mathrm{fib}_n = \mathrm{fib}_{n - 1} + \mathrm{fib}_{n - 2} & (n \geqslant 2)
\end{cases}
によって定まる正整数列 \{ \mathrm{fib}_n \}_{n \geqslant 0} のことで，次のような一般項が知られています：
\mathrm{fib}_n = \frac{\varphi^n - \overline{\varphi}^n}{\sqrt{5}}.
ただし，\varphi は黄金比で，\overline{\varphi} はその共役（詳しくは後述）です：
\varphi = \frac{1 + \sqrt{5}}{2}, \quad \overline{\varphi} = \frac{1 - \sqrt{5}}{2}.
この一般項を用いて計算する場合，\sqrt{5} という無理数が含まれているので，浮動小数点数（C の double や Rust の f64）を使わなければなりませんし，これらの計算には当然誤差が生じてしまいます
……本当にそうでしょうか？
実は，代数学でよく知られた2次体というものを使えば，整数の演算だけで（！）一般項から Fibonacci 数列を計算できてしまいます．
2次体という難しそうな言葉が出てきましたが，定義は簡単で，（平方因子を持たない）整数 d \neq 0 に対して
\mathbb{Q} (\sqrt{d}) := \{ a + b \sqrt{d} \mid a, b \in \mathbb{Q} \}
という \mathbb{C} の部分集合のことです．（ここで，\mathbb{Q}，\mathbb{C} はそれぞれ有理数全体の集合と複素数全体の集合を表します．）
d = -1 であれば Gauss 整数環の商体ですね．
この2次体は，その名前から推測できるように体となります：
\left( a_1 + b_1 \sqrt{d} \right) + \left( a_2 + b_2 \sqrt{d} \right) = (a_1 + a_2) + (b_1 + b_2) \sqrt{d}, \\
\left( a_1 + b_1 \sqrt{d} \right) - \left( a_2 + b_2 \sqrt{d} \right) = (a_1 - a_2) + (b_1 - b_2) \sqrt{d}, \\
\left( a_1 + b_1 \sqrt{d} \right) \cdot \left( a_2 + b_2 \sqrt{d} \right) = (a_1 a_2 + b_1 b_2 d) + (a_1 b_2 + a_2 b_1) \sqrt{d}, \\
\left( a + b \sqrt{d} \right)^{-1} = \frac{a - b \sqrt{d}}{a^2 - b^2 d}.
さて，2次体というのは集合としては単に二つの有理数の組 \mathbb{Q} \times \mathbb{Q} で書けるので，そのように見たとき上の計算規則は
(a_1, b_1) + (a_2, b_2) = (a_1 + a_2, b_1 + b_2), \\
(a_1, b_1) - (a_2, b_2) = (a_1 - a_2, b_1 - b_2), \\
(a_1, b_1) \cdot (a_2, b_2) = (a_1 a_2 + b_1 b_2 d, a_1 b_2 + a_2 b_1), \\
(a, b)^{-1} = \left( \frac{a}{a^2 - b^2 d}, - \frac{b}{a^2 - b^2 d} \right)
となります．
ついに \sqrt{d} が消えましたね！
ここまで来れば後は簡単です．\mathbb{Q} (\sqrt{5}) という2次体の中で \varphi = (1/2, 1/2) と \overline{\varphi} = (1/2, -1/2) の冪を計算して，それを \sqrt{5} = (0, 1) で割れば Fibonacci 数列が計算できます．
まだ整数同士の割り算があるので誤差が生じ得ますが，平方根を計算する必要がないのは嬉しいですね．
ただ，もう少しだけ工夫もできます．
一般に，2次体の元 x = a + b \sqrt{d} \in \mathbb{Q} (\sqrt{d}) に対して \overline{x} = a - b \sqrt{d} \in \mathbb{Q} (\sqrt{d}) を x の共役（conjugate）と呼びます．d = -1 のときはいわゆる複素共役のことです．
実は，共役を取る操作と2次体の四則演算は可換となっています：
\overline{x} + \overline{y} = \overline{x + y}, \\
\overline{x} - \overline{y} = \overline{x - y}, \\
\overline{x} \cdot \overline{y} = \overline{x \cdot y}, \\
\left( \overline{x} \right)^{-1} = \overline{x^{-1}}.
このことを使うと，もし \varphi^n = a_n + b_n \sqrt{5} が計算できれば \overline{\varphi}^n = a_n - b_n \sqrt{5} が分かるので，結局
\mathrm{fib}_n = \frac{\left( a_n + b_n \sqrt{5} \right) - \left( a_n - b_n \sqrt{5} \right)}{\sqrt{5}} = 2 b_n
となります．従って，\varphi^n さえ求まれば Fibonacci 数列の一般項も自動的に求まります！
また，a_n と b_n は必ず半整数となります．
そのことを確認するために，2 \varphi^n = c_n + d_n \sqrt{5} と置いてみましょう．さきほど見たように d_n = \mathrm{fib}_n なので，当然整数です．一方，\{ (c_n, d_n) \}_{n \geqslant 0} という数列は
\begin{cases}
\displaystyle c_n = \frac{c_{n - 1} + 5 d_{n - 1}}{2}, \\
\displaystyle d_n = \frac{c_{n - 1} + d_{n - 1}}{2}
\end{cases}
という漸化式を満たす（これは，c_n + d_n \sqrt{5} = (c_{n - 1} + d_{n - 1} \sqrt{5}) \varphi から従います）ので，特に
c_{n - 1} = 2 d_n - d_{n - 1} = 2 \mathrm{fib}_n - \mathrm{fib}_{n - 1}
も整数です．
以上のことを用いたサンプルコードがこちらです：
https://play.rust-lang.org/?version=beta&mode=debug&edition=2018&gist=625acd5173e4a9fa51d5a1045beadff9
fibonacci_add() は n = 92 で overflow するのに対して，fibonacci_general() は n = 90 で overflow します．おおよそ理論通りですね．
余談ですが，今回の実装ではじめて Rust の (min_)const_generics を使ってみました．ほかにも代数的な計算例に使えそうで楽しいです．
（まあ C++ でも同じことはできますが……．）
Discussion