An optimal, stable continued fraction algorithm for arbitrary dimension

We analyse a continued fraction algorithm (abbreviated CFA) for arbitrary dimension n showing that it produces simultaneous diophantine approximations which are up to the factor 2^((n+2)/4) best possible. Given a real ve
We analyse a continued fraction algorithm (abbreviated CFA) for arbitrary dimension n showing that it produces simultaneous diophantine approximations which are up to the factor 2^((n+2)/4) best possible. Given a real vector x=(x_1,...,x_{n-1},1) in R^n this CFA generates a sequence of vectors (p_1^(k),...,p_{n-1}^(k),q^(k)) in Z^n, k=1,2,... with increasing integers |q^{(k)}| satisfying for i=1,...,n-1 | x_i - p_i^(k)/q^(k) | <= 2^((n+2)/4) sqrt(1+x_i^2) |q^(k)|^(1+1/(n-1)) By a theorem of Dirichlet this bound is best possible in that the exponent 1+1/(n-1) can in general not be increased.
show moreshow less

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Author:Carsten Rössner, Claus Peter Schnorr
URN:urn:nbn:de:hebis:30-12463
Document Type:Article
Language:English
Date of Publication (online):2005/07/19
Year of first Publication:1996
Publishing Institution:Univ.-Bibliothek Frankfurt am Main
Release Date:2005/07/19
Tag:Dirichlet bound ; continued fraction algorithm ; floating point arithmetic; integer relation ; simultaneous diophantine approximations
Source:5th IPCO Conference on Integer Programming and Combinatorial Optimization.Springer LNCS 1084, 31 - 43, 1996 , s.a. ECCC Report TR96-020 , http://www.mi.informatik.uni-frankfurt.de/research/papers.html
HeBIS PPN:224866249
Institutes:Mathematik
Informatik
Dewey Decimal Classification:510 Mathematik
Sammlungen:Universitätspublikationen
Licence (German):License Logo Veröffentlichungsvertrag für Publikationen

$Rev: 11761 $