Analysis of the subtractive algorithm for greatest common divisors
DOI10.1073/PNAS.72.12.4720zbMATH Open0315.10005OpenAlexW2000138878WikidataQ37462809 ScholiaQ37462809MaRDI QIDQ4074953FDOQ4074953
Authors: Andrew Chi-Chih Yao, Donald E. Knuth 
Publication date: 1975
Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1073/pnas.72.12.4720
Radix representation; digital problems (11A63) Continued fractions and generalizations (11J70) Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05)
Cited In (13)
- On the distribution of partial quotients of reduced fractions with fixed denominator
- High moments of the Estermann function
- Quasi-Monte Carlo methods and pseudo-random numbers
- New versions of Miller-loop secured against side-channel attacks
- Linear extensions and continued fractions
- Limit laws for rational continued fractions and value distribution of quantum modular forms
- The law of large numbers for the sum of the partial quotients of a rational number with fixed denominator
- Equality cases of the Alexandrov-Fenchel inequality are not in the polynomial hierarchy
- Digits and continuants in Euclidean algorithms. Ergodic versus Tauberian theorems
- Navigating in the Cayley graphs of \(\text{SL}_N(\mathbb{Z})\) and \(\text{SL}_N(\mathbb{F}_p)\).
- Dynamical analysis of a class of Euclidean algorithms.
- Mean value of sums of partial quotients of continued fractions
- On semi-regular finite continued fractions
This page was built for publication: Analysis of the subtractive algorithm for greatest common divisors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4074953)
