The Euclid Algorithm is totally gaussian
We consider Euclid’s gcd algorithm for two integers $(p, q)$ with $1 \leq p \leq q \leq N$, with the uniform distribution on input pairs. We study the distribution of the total cost of execution of the algorithm for an additive cost function $d$ on the set of possible digits, asymptotically for $N \...
Main Author: | Brigitte Vallée |
---|---|
Format: | Article |
Language: | English |
Published: |
Discrete Mathematics & Theoretical Computer Science
2012-01-01
|
Series: | Discrete Mathematics & Theoretical Computer Science |
Subjects: | |
Online Access: | https://dmtcs.episciences.org/3000/pdf |
Similar Items
-
A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set
by: Serge Gaspers, et al.
Published: (2012-02-01) -
Bounds for minimum feedback vertex sets in distance graphs and circulant graphs
by: Hamamache Kheddouci, et al.
Published: (2008-01-01) -
Bounds for minimum feedback vertex sets in distance graphs and circulant graphs
by: Hamamache Kheddouci, et al.
Published: (2008-01-01) -
Linear time recognition of P4-indifference graphs
by: Michel Habib, et al.
Published: (2001-01-01) -
Lattice reduction in two dimensions: analyses under realistic probabilistic models
by: Brigitte Vallée, et al.
Published: (2007-01-01)