Porter's constant

The Porter's constant describes the average number of computation steps that are required to solve the Euclidean algorithm . It is named after the English mathematician John William Porter.

definition

In general, the greatest common divisor of two positive natural numbers and is determined using the Euclidean algorithm . Let the number of steps of the algorithm be , the mean number of steps with fixed n is: ${\displaystyle \operatorname {ggT} (n,m)}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle T(n,m)}$

${\displaystyle T(n)={\frac {1}{n}}\sum _{0\leq m<n}T(n,m)}$.

Since this simplifies the analysis, the mean over coprime (n, m) is considered instead:

${\displaystyle \tau _{n}={\frac {1}{\phi (n)}}\sum _{0\leq m<n,ggT(m,n)=1}T(n,m)}$

where is Euler's Phi function and ${\displaystyle \phi (n)}$

${\displaystyle T(n)={\frac {1}{n}}\sum _{d|n}\phi (d)\tau _{d}}$

Porter showed in 1975:

${\displaystyle \tau _{n}={\frac {12\ln 2}{\pi ^{2}}}\ln n+C+O(n^{-{\frac {1}{6}}+\epsilon })}$

It turns a Landau-symbold represents and is arbitrary. ${\displaystyle O}$ ${\displaystyle \epsilon >0}$

C is Porter's constant:

${\displaystyle C={{6\ln 2} \over {\pi ^{2}}}\left[3\ln 2+4\gamma -{{24} \over {\pi ^{2}}}\zeta '(2)-2\right]-{{1} \over {2}}=1.4670780794\ldots }$

It says:

• ${\displaystyle \gamma }$for the Euler-Mascheroni constant .
• ${\displaystyle \zeta (s)}$for the Riemannian zeta function and for the value of its derivative at position 2. ${\displaystyle \zeta ^{\prime }(2)}$

The prefactor of the leading logarithmic term was previously obtained from Hans Arnold Heilbronn (he found an error term which was improved to by T. Tonkov ) and independently from John D. Dixon. ${\displaystyle O(\ln \ln \,n)^{4}}$ ${\displaystyle O(\ln \ln \,n^{2})}$

If one considers the means via : ${\displaystyle m,n<N}$

${\displaystyle A(N)={1 \over {N^{2}}}\sum _{\begin{matrix}1\leq m<N\\1\leq n<N\end{matrix}}T(n,m)}$,

Norton proved in 1990:

${\displaystyle A(N)={\frac {12\ln 2}{\pi ^{2}}}\left(\ln N-{\frac {1}{2}}+{\frac {\zeta ^{\prime }(2)}{\zeta (2)}}\right)+C-{\frac {1}{2}}+O(N^{-{1 \over 6}+\epsilon })}$

with any . ${\displaystyle \epsilon >0}$

literature

• HA Heilbronn: On the Average Length of a Class of Finite Continued Fractions , in: P. Turan (Hrsg.), Number Theory and Analysis, Plenum 1969, pp. 87-96
• JD Dixon: The number of steps in the Euclidean Algorithm , J. Number Theory, Volume 2, 1970, pp. 414-422 Online (accessed November 18, 2019)
• JW Porter: On a Theorem of Heilbronn , Mathematika, Volume 22, 1975, pp. 20-28
• Donald E. Knuth : Evaluation of Porter's Constant , Computers and Mathematics with Applications, Volume 2, 1976, pp. 137-139
• DE Knuth: The Art of Computer Programming , Volume 2, 2nd Edition, Reading 1981, pp. 355-357
• GH Norton: On the Asymptotic Analysis of the Euclidean Algorithm , J. Symb. Comput., Volume 10, 1990, pp. 53-58 Online (accessed November 18, 2019)

Individual evidence

1. ↑ Knuth, The Art of Computer Programming, Volume 2, 1981, pp. 354f
2. ^ Knuth, Art of Computer Programming, Volume 2, 1981, p. 357
3. ↑ Donald Knuth's evaluation of Porter's constant was described by him in Evaluation of Porter's constant , Comp. and Math. with Applic., Vol. 2, 1976, pp. 137-139. There he also cites a contribution by JW Wrench Jr.
4. ↑ T. Tonkov, On the average length of finite continued fractions , Acta Arithmetica, Vol. 26, 1974, pp. 47-57. Quoted from Knuth, Evaluation of Porter's constant, Comp. and Math. with Applic., Volume 2, 1976, p. 137 Online (accessed November 18, 2019)
5. ↑ Norton, J. Symb. Comp., Vol. 10, 1990, p. 57