Image Processing Reference
In-Depth Information
1
[q
1
,q
2
,...,q
n
] =
.
1
q
1
+
1
.
.
.
q
2
+
1
1
q
n
q
n−1
+
4.1.1.1
Analyzing a Continued Fraction
A brief overview of the procedure for getting the period of a DSL (with
rational slope) is given here; for details, see [34, 115, 116, 209]. Let the slope
of a DSS = a/b (1 < a < b;a,b ∈ Z). Using the Euclidean algorithm, it can
be expressed as
a
b
1
=
1
q
1
+
1
.
.
.
q
2
+
1
1
q
n
q
n−1
+
=
[q
1
,q
2
,...,q
n
]
(4.2)
where q
1
,q
2
,...,q
n
are positive integers
α
n
q
n
+ β
n
γ
n
q
n
+ δ
n
, where α
n
,β
n
,γ
n
,δ
n
are defined by q
1
,q
2
,...,q
n−1
=
(α
n−1
q
n−1
+ β
n−1
)q
n
+ α
n−1
(γ
n−1
q
n−1
+ δ
n−1
)q
n
+ γ
n−1
=
(4.3)
(α
n−1
q
n−1
+ β
n−1
)(q
n
−1) + α
n−1
(q
n−1
+ 1) + β
n−1
=
−1) + γ
n−1
(q
n−1
+ 1) + δ
n−1
.
(4.4)
(γ
n−1
q
n−1
+ δ
n−1
)(q
n
Eq. 4.3 is obtained from Eq. 4.2 based on the observation that [q
1
,q
2
,...,q
n
]
(n elements) and [q
1
,q
2
,...,q
n−1
+
1
q
n
] (n−1 elements) are equivalent, and
1
q
n
α
n−1
q
n−1
+
+ β
n−1
1
q
n
q
1
,q
2
,...,q
n−1
+
=
.
1
q
n
γ
n−1
q
n−1
+
+ δ
n−1
Eq. 4.4 is obtained from Eq. 4.3 simply by manipulating a few terms in order
to perform concatenation of two slopes (fractions), which is defined below.
