Analysis of the subtractive algorithm for greatest common divisors
From MaRDI portal
Publication:4074953
DOI10.1073/pnas.72.12.4720zbMath0315.10005OpenAlexW2000138878WikidataQ37462809 ScholiaQ37462809MaRDI QIDQ4074953
Donald E. Knuth, Andrew Chi-Chih Yao
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
Continued fractions and generalizations (11J70) Radix representation; digital problems (11A63) Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05)
Related Items
On semi-regular finite continued fractions ⋮ Limit laws for rational continued fractions and value distribution of quantum modular forms ⋮ Dynamical analysis of a class of Euclidean algorithms. ⋮ On the distribution of partial quotients of reduced fractions with fixed denominator ⋮ New versions of Miller-loop secured against side-channel attacks ⋮ The law of large numbers for the sum of the partial quotients of a rational number with fixed denominator ⋮ Mean value of sums of partial quotients of continued fractions ⋮ High moments of the Estermann function ⋮ Digits and continuants in Euclidean algorithms. Ergodic versus Tauberian theorems ⋮ Quasi-Monte Carlo methods and pseudo-random numbers ⋮ Navigating in the Cayley graphs of \(\text{SL}_N(\mathbb{Z})\) and \(\text{SL}_N(\mathbb{F}_p)\).
