Материал: Лекция 2 Генерирование простых чисел [восстановлен]
Пример цепной дроби
[−3, 2,1, 4] = −3 + |
|
1 |
|
|
= − |
47 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
13 |
|
|
|
|
|
|
|
|
|
|
|||
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
1+ |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Неполные частные имеют вид |
|
|
a 0 = −3 a 1= 2 a 2 =1 |
|
a 3 = 4 |
||||||||||||
полные частные имеют вид |
|
|
|
α0 =[−3, 2,1, 4] = −3 + |
|
1 |
|
|
= − |
47 |
|||||||
|
|
|
|
|
1 |
|
|
13 |
|||||||||
|
|
|
|
|
|
|
|
|
|
2 + |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
1+ |
1 |
|
|
|
|||
|
|
α =[2,1, 4] == 2 + |
|
1 |
= 14 |
|
|
|
4 |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
1 |
|
|
|
1 |
1 |
5 |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
+ 4 |
|
|
|
|
|
|
|
|
||
α2 =[1, 4] =1+ 14 = 54
α3 =[4] = 4
Пример цепной дроби
(продолжение)
•Цепная дробь, образованная отбрасыванием всех элементов после некоторого номера k, называется k-ой подходящей дробью
δ0 =[−3] = −3
δ1 =[−3, 2] = −3 + |
1 |
|
= − |
5 |
|
|
||||||
|
|
2 |
|
|
|
|
2 |
|
|
|||
δ2 =[−3, 2,1] = −3 + |
|
|
|
1 |
|
|
= − |
8 |
|
|||
2 |
+ |
1 |
|
3 |
|
|||||||
|
|
|
|
|
|
|
||||||
|
|
1 |
|
|
|
|
|
|
||||
δ3 =[−3, 2,1, 4] = −3 + |
|
|
|
|
1 |
|
|
|
|
= − |
47 |
|
|
|
|
|
|
1 |
|
|
|
13 |
|||
2 |
+ |
|
|
|
|
|
|
|
||||
|
1+ 1 |
|
|
|
|
|||||||
|
|
|
|
|
|
4 |
|
|
|
|
||
• Подходящие дроби можно представить рациональными |
|||||||||||
числами |
Pk |
k=0,1,…..,n . |
|
|
|
|
|
||||
|
P0 |
= a0 |
Qk |
|
P1 |
= a0a1 +1 |
|
Pk |
|
ak Pk −1 + Pk −2 |
|
δ0 = |
|
δ1 = |
δk = |
= |
для k ≥ 2 |
||||||
Q0 |
|
||||||||||
|
Q1 |
Qk |
|
||||||||
|
1 |
|
|
a1 |
|
|
ak Qk −1 +Qk −2 |
||||
Свойства:
1. P Q |
− P Q |
= (−1)n−1 |
7. Если a =[a0 , a1, , a , ], то |
n n−1 |
n−1 n |
|
δ0 <δ2 < <δ2k < ≤ a ≤ δ2k +1 < <δ3 <δ1 |
2. PnQn−2 − Pn−2Qn = (−1)n−1 an |
|||
3. (PnQn ) =1 |
|
|
|
|
8. |
Если a =[a ,a , ,a , ], то |
|
a−δ |
n |
|
≤ |
1 |
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|||||
4. 1 = Q ≤ Q |
< Q |
< |
|
|
0 1 |
|
|
|
|
QnQn−1 |
1 |
|||
|
|
|
|
|
||||||||||
0 |
1 |
2 |
|
|
|
|
|
|
|
|
|
|
||
5. Если P0 |
>1, то P1 > P2 |
> |
|
|
|
|
|
|
|
|
||||
6. δn −δn−1 = (−1)n−1
QnQn−1
Вычисление цепной дроби
Достаточно выписать Алгоритм Евклида для чисел P иQ, и взять столбец , полученный при этом целых частных в
качестве неполных частных искомой дроби |
P |
= |
173 |
||||
173 = 281 0 +173 |
|
|
|
|
Q |
|
281 |
|
|
|
|
|
|
|
|
281 =173 1+108 |
|
|
|
|
|
|
|
173 =108 1+ 65 |
P |
= |
173 |
=[0,1,1,1,1,1,1, 21] |
|
|
|
108 = 65 1+ 43 |
|
281 |
|
|
|
||
Q |
|
|
|
||||
65 = 43 1+ 22 |
|
|
|
|
|
|
|
43 = 22 1+ 421 |
|
|
|
|
|
|
|
22 = 21 1+1 |
|
|
|
|
|
|
|
21 =1 21+ 0 |
|
|
|
|
|
|
|
Применение цепных дробей
1.Для приближения действительных чисел рациональными с наилучшим приближением.
2.Для сокращения обыкновенных дробей
3.Для решения диофантовых уравнений с двумя неизвестными.
4. Для решения сравнений первой степени ax ≡ b(mod m) .
П.1 Любая подходящая дробь δk =[a0 , a1, , ak ], k = 0,1,2 является наилучшим приближением к действ. числу
a =[a0 , a1, , an , ].
В основе практического применения используется свойство |
|||||||||
|
a −δn |
|
≤ |
|
δn+1 −δn |
|
= |
1 |
Для нахождения наилучшего |
|
|
|
|
||||||
|
|
|
|
Qn+1Qn |
|||||
|
|
|
|
|
|
|
|
|
|
приближения с точностью ∆, рассматриваются знаменатели |
|||||||||
тех подходящих дробей, для которых Qn+1Qn > ∆−1 |
|||||||||