Real number approximation by a rational number in the approximating k-ary algorithm

Abstract

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.

Keywords

• approximating k-ary algorithm
• farey sequence
• continued fractions