Analysis of the subtractive algorithm for greatest common divisors

DOI10.1073/PNAS.72.12.4720MaRDI QIDQ4074953zbMATH OpenOpenAlexWikidataFDO

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

Mathematics Subject Classification ID

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)