Continued fractions （连分数）¶
Continued fractions - Diophantine approximation (sagemath.org)
在 python / sage math 中，连分数的表示方式如下：
$[a_0;a_1,a_2,\ldots]=a_0+\frac1{[a_1;a_2,\ldots]}=a_0+\frac1{a_1+\frac1{a_2+\frac1{\ldots}}}$
In [12]:
Copied!
# 创建一个正常的分数 normal fraction
nf = Rational(40/27)
nf, type(nf)
# 创建一个正常的分数 normal fraction
nf = Rational(40/27)
nf, type(nf)
Out[12]:
(40/27, <class 'sage.rings.rational.Rational'>)
In [25]:
Copied!
cf = nf.continued_fraction()
cf, type(cf), cf.quotients(), cf.quotient(1)
cf = nf.continued_fraction()
cf, type(cf), cf.quotients(), cf.quotient(1)
Out[25]:
([1; 2, 13], <class 'sage.rings.continued_fraction.ContinuedFraction_periodic'>, [1, 2, 13], 2)
cf 还有很多属性和方法，构建方法也有很多，按下不表，记住 cf.value() 即可。
In [21]:
Copied!
# 值，渐进分数， cf.convergents()[1]， denominator of cf.convergent(2)
cf.value(), cf.convergents(), cf.convergent(1), cf.denominator(2)
# 值，渐进分数， cf.convergents()[1]， denominator of cf.convergent(2)
cf.value(), cf.convergents(), cf.convergent(1), cf.denominator(2)
Out[21]:
(40/27, [1, 3/2, 40/27], 3/2, 27)
In [15]:
Copied!
cf.ceil(), cf.floor()
cf.ceil(), cf.floor()
Out[15]:
(2, 1)
使用实例 ¶
连分数可用于 RSA 中的 Wiener's attack 。