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

Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05) Radix representation; digital problems (11A63) Continued fractions and generalizations (11J70)

Cited in

(15)

• On semi-regular finite continued fractions
• Dynamical analysis of a class of Euclidean algorithms.
• High moments of the Estermann function
• The law of large numbers for the sum of the partial quotients of a rational number with fixed denominator
• Navigating in the Cayley graphs of \(\text{SL}_N(\mathbb{Z})\) and \(\text{SL}_N(\mathbb{F}_p)\).
• Quasi-Monte Carlo methods and pseudo-random numbers
• Digits and continuants in Euclidean algorithms. Ergodic versus Tauberian theorems
• Limit laws for rational continued fractions and value distribution of quantum modular forms
• On the distribution of partial quotients of reduced fractions with fixed denominator
• New versions of Miller-loop secured against side-channel attacks
• Mean value of sums of partial quotients of continued fractions
• Linear extensions and continued fractions
• Equality cases of the Alexandrov-Fenchel inequality are not in the polynomial hierarchy
• Searching for differential addition chains
• Recognition of pieces of arithmetic hyperplanes using the Stern-Brocot tree

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)