A rigorous version of R.P. Brent's model for the binary Euclidean algorithm
A rigorous version of R.P. Brent's model for the binary Euclidean algorithm
复制标题
R.P. Brent 二进制欧几里得算法模型的严格版本
DOI：
10.1016/j.aim.2015.12.008
复制
发表时间：
2016
影响因子：
1.7
通讯作者：
Morris I
中科院分区：
文献类型：
--
作者：
Morris I
二进制欧几里德算法是计算最大公约数的经典欧几里德算法的改进，它避免了普通的整数除法，而只支持除以2的幂。二进制欧几里德算法在应用于有界大小的整数对时的步数期望是由R.P.Brent于1976年首次通过将该算法作为随机动力系统的启发式模型来研究的。基于对相关Ruelle传递算子期望的数值研究，Brent得到了该算法在处理大整数大小有界的奇数对时所执行的平均步数的猜想渐近表达式。1998年，B.Vallée通过归纳法对Brent模型进行了修正，严格证明了算法执行的平均步数的渐近公式；然而，这一结果与Brent启发式的关系仍然是猜想的。在这篇文章中，我们建立了先前关于Brent转移算子的猜想性质，直接证明了它具有谱隙并且保持唯一的连续密度。证明了这种密度全纯地扩展到复右半平面，并且在零点具有对数奇性。通过将这些结果与经典解析数论的方法相结合，我们证明了关于期望步数的三个猜想公式的正确性，解决了D.E.Knuth在计算机程序设计艺术中提出的几个未决问题。
The binary Euclidean algorithm is a modification of the classical Euclidean algorithm for computation of greatest common divisors which avoids ordinary integer division in favour of division by powers of two only. The expectation of the number of steps taken by the binary Euclidean algorithm when applied to pairs of integers of bounded size was first investigated by R.P. Brent in 1976 via a heuristic model of the algorithm as a random dynamical system. Based on numerical investigations of the expectation of the associated Ruelle transfer operator, Brent obtained a conjectural asymptotic expression for the mean number of steps performed by the algorithm when processing pairs of odd integers whose size is bounded by a large integer. In 1998 B. Vallée modified Brent's model via an induction scheme to rigorously prove an asymptotic formula for the average number of steps performed by the algorithm; however, the relationship of this result with Brent's heuristics remains conjectural. In this article we establish previously conjectural properties of Brent's transfer operator, showing directly that it possesses a spectral gap and preserves a unique continuous density. This density is shown to extend holomorphically to the complex right half-plane and to have a logarithmic singularity at zero. By combining these results with methods from classical analytic number theory we prove the correctness of three conjectured formulae for the expected number of steps, resolving several open questions promoted by D.E. Knuth inThe Art of Computer Programming.