Porter-Konstante

Die Porter-Konstante beschreibt die durchschnittliche Anzahl von Rechenschritten, die zur Lösung des euklidischen Algorithmus benötigt wird. Sie ist nach dem englischen Mathematiker John William Porter benannt.

Definition

Allgemein wird mithilfe des euklidischen Algorithmus der größte gemeinsame Teiler $\operatorname {ggT} (n,m)$ von zwei positiven natürlichen Zahlen $n$ und $m$ bestimmt. Die Anzahl der Schritte des Algorithmus sei $T(n,m)$, die mittlere Anzahl der Schritte bei festem $n$ ist:

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

Da das die Analyse vereinfacht, wird stattdessen das Mittel über teilerfremde $(n,m)$ betrachtet:

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

wobei $\phi (n)$ die Eulersche Phi-Funktion ist und

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

Porter zeigte 1975:

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

Dabei stellt $O$ ein Landau-Symbold dar und $\epsilon >0$ ist beliebig.

$C$ ist die Porter-Konstante:

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

Dabei steht:

• $\gamma$ für die Euler-Mascheroni-Konstante.
• $\zeta (s)$ für die riemannische Zeta-Funktion und $\zeta ^{\prime }(2)$ für den Wert von deren Ableitung an der Stelle 2.

Der Vorfaktor des führenden logarithmischen Terms wurde schon zuvor von Hans Arnold Heilbronn (er fand einen Fehlerterm $O(\ln \ln \,n)^{4}$, der von T. Tonkov auf $O(\ln \ln \,n^{2})$ verbessert wurde) und unabhängig von John D. Dixon erhalten.

Betrachtet man das Mittel über $m,n<N$:

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

bewies Norton 1990:

$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^{-{\frac {1}{6}}+\epsilon })$

mit beliebigem $\epsilon >0$.

Literatur

• H. A. Heilbronn: On the Average Length of a Class of Finite Continued Fractions, in: P. Turan (Hrsg.), Number Theory and Analysis, Plenum 1969, S. 87–96
• J. D. Dixon: The number of steps in the Euclidean Algorithm, J. Number Theory, Band 2, 1970, S. 414–422 Online (abgerufen am 18. November 2019)
• J. W. Porter: On a Theorem of Heilbronn, Mathematika, Band 22, 1975, S. 20–28
• Donald E. Knuth: Evaluation of Porter's Constant, Computers and Mathematics with Applications, Band 2, 1976, S. 137–139
• D. E. Knuth: The Art of Computer Programming, Band 2, 2. Auflage, Reading 1981, S. 355–357
• G. H. Norton: On the Asymptotic Analysis of the Euclidean Algorithm, J. Symb. Comput., Band 10, 1990, S. 53–58 Online (abgerufen am 18. November 2019)