Analysis of the binary Euclidean algorithm
Analysis of the binary Euclidean algorithm
复制标题
二元欧氏算法分析
DOI：
10.1145/1093397.1093399
复制
发表时间：
1976
期刊：
影响因子：
--
通讯作者：
R. Brent
中科院分区：
文献类型：
--
作者：
R. Brent
二进制欧几里德算法使用减法、移位和奇偶校验来找到两个整数u和v的GCD。与经典的欧几里德算法不同，它不需要除法。我们分析了一个连续模型的二进制算法，并找到预期的迭代次数。
The binary Euclidean algorithm finds the GCD of two integers u and v using subtraction, shifting and parity testing. Unlike the classical Euclidean algorithm, no divisions are required. We analyse a continuous model of the binary algorithm, and find the expected number of iterations.