Function nekolib::math::sqrt_fraction_fn

pub fn sqrt_fraction_fn(
    n: i128
) -> (i128, impl Fn(i128, i128) -> (i128, i128, i128))

平方根の連分数展開。

$\sqrt{n}$ の連分数展開の $i$ step 目が次のように表されるとする。 $$ \sqrt{n} = a_0 + \frac{1}{\dots\,+\frac{1}{a_{i-1}+\frac{\sqrt{n}-b_{i-1}}{c_{i-1}}}}. $$

$a_0$ と、関数 $f: (b_i, c_i)\mapsto (a_{i+1}, b_{i+1}, c_{i+1})$ を返す。 ただし、$(a_0, b_0, c_0) = (\lfloor\sqrt{n}\rfloor, \lfloor\sqrt{n}\rfloor, 1)$ である。

実際の連分数展開が欲しいときは sqrt_fraction を用いればよい。 周期検出などをしたいときは $(b_\bullet, c_\bullet)$ が必要になる。

Derivation

todo!()

Examples

use nekolib::math::sqrt_fraction_fn;

let (a0, next) = sqrt_fraction_fn(3);
assert_eq!(a0, 1);
let (a1, b1, c1) = next(a0, 1);
let (a2, b2, c2) = next(b1, c1);
let (a3, b3, c3) = next(b2, c2);

assert_eq!((a1, b1, c1), (a3, b3, c3));  // sqrt(3) has period 2
assert_eq!([a0, a1, a2], [1, 1, 2]);  // sqrt(3) = [1; (1, 2)]