کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9496506 | 1630683 | 2005 | 56 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Euclidean algorithms are Gaussian
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
اعداد جبر و تئوری
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We obtain a central limit theorem for a general class of additive parameters (costs, observables) associated to three standard Euclidean algorithms, with optimal speed of convergence. We also provide very precise asymptotic estimates and error terms for the mean and variance of such parameters. For costs that are lattice (including the number of steps), we go further and establish a local limit theorem, with optimal speed of convergence. We view an algorithm as a dynamical system restricted to rational inputs, and combine tools imported from dynamics, such as transfer operators, with various other techniques: Dirichlet series, Perron's formula, quasi-powers theorems, and the saddle-point method. Such dynamical analyses had previously been used to perform the average-case analysis of algorithms. For the present (dynamical) analysis in distribution, we require estimates on transfer operators when a parameter varies along vertical lines in the complex plane. To prove them, we adapt techniques introduced recently by Dolgopyat in the context of continuous-time dynamics (Ann. Math. 147 (1998) 357).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Number Theory - Volume 110, Issue 2, February 2005, Pages 331-386
Journal: Journal of Number Theory - Volume 110, Issue 2, February 2005, Pages 331-386
نویسندگان
Viviane Baladi, Brigitte Vallée,