Real number approximation by a rational number in the approximating k-ary algorithm
The best approximation by the irreducible fraction with the denominator not exceeding some specified value n was investigated. The aim of this study was to find the fastest approximation algorithm that enables to accelerate the convergence of the k-ary algorithm for computing the greatest common div...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Kazan Federal University
2019-06-01
|
| Series: | Учёные записки Казанского университета: Серия Физико-математические науки |
| Subjects: | |
| Online Access: | https://kpfu.ru/uz-eng-phm-2019-2-6.html |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | The best approximation by the irreducible fraction with the denominator not exceeding some specified value n was investigated. The aim of this study was to find the fastest approximation algorithm that enables to accelerate the convergence of the k-ary algorithm for computing the greatest common divisor. The approximation based on Farey sequences was described; this method was considered using a quick exit condition, precomputation of the initial steps, and search in the Farey sequence built in advance. We also discussed the approximation with continued fractions and proposed an algorithm using a precomputation and continued fractions. The time and memory complexity of these algorithms were shown; these methods were compared with respect to running time and iterations amount. It was concluded that the approximation with the help of Farey sequences and precomputation is the fastest method, but the approximation with continued fractions has no additional memory demands. |
|---|---|
| ISSN: | 2541-7746 2500-2198 |