Function nekolib::math::continued_fraction_::continued_fraction
source · pub fn continued_fraction(
a: impl Iterator<Item = i128>
) -> impl Iterator<Item = (i128, i128)>
Expand description
連分数展開。
$[a_0, a_1, \dots, a_{i-1}]$ の連分数展開。 $a_\bullet$ を生成するイテレータから $$ a_0 + \frac{1}{a_1 + \frac{1}{\cdots\, + \frac{1}{a_{\bullet}}}} $$ を生成するイテレータを作る。
Implementation notes
std::iter::successors
によって次の項が計算されるタイミングの関係で、
実際には必要ない値の計算のせいでオーバーフローし、panic するのを避けるため、
同等の処理を map
中に再度書いている。
Pell 方程式を解く際、解は i128
に収まるが上記の問題で panic したのでこうなった。
実際には release build では問題なく動くことが予想されるので無視してもいい気もするが…
Examples
use nekolib::math::continued_fraction;
let frac_exp = [1, 2];
let sqrt3 = std::iter::once(1).chain(frac_exp.iter().copied().cycle());
let mut it = continued_fraction(sqrt3);
assert_eq!(it.next(), Some((1, 1)));
assert_eq!(it.next(), Some((2, 1)));
assert_eq!(it.next(), Some((5, 3)));
assert_eq!(it.next(), Some((7, 4)));
assert_eq!(it.next(), Some((19, 11)));
assert_eq!(it.next(), Some((26, 15)));
let (x, y) = it.nth(24).unwrap();
assert!(((x as f64 / y as f64) - 3.0_f64.sqrt()).abs() < 1.0e-16);