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 ${\displaystyle \operatorname {ggT} (n,m)}$ von zwei positiven natürlichen Zahlen ${\displaystyle n}$ und ${\displaystyle m}$ bestimmt. Die Anzahl der Schritte des Algorithmus sei ${\displaystyle T(n,m)}$, die mittlere Anzahl der Schritte bei festem n ist:

${\displaystyle 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:^[1]

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

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

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

Porter zeigte 1975:

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

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

C ist die Porter-Konstante:^[2][3]

${\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 }$

Dabei steht:

• ${\displaystyle \gamma }$ für die Euler-Mascheroni-Konstante.
• ${\displaystyle \zeta (s)}$ für die riemannische Zeta-Funktion und ${\displaystyle \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 ${\displaystyle O(\ln \ln \,n)^{4}}$, der von T. Tonkov auf ${\displaystyle O(\ln \ln \,n^{2})}$ verbessert wurde)^[4] und unabhängig von John D. Dixon erhalten.

Betrachtet man das Mittel über ${\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)}$,

bewies Norton 1990:^[5]

${\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 })}$

mit beliebigem ${\displaystyle \epsilon >0}$.

Literatur

• 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)
• D. E. Knuth: The Art of Computer Programming, Band 2, 2. Auflage, Reading 1981, S. 355–357
• 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
• 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
• 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)

Einzelnachweise

1. ↑ Knuth, The Art of Computer Programming, Band 2, 1981, S. 354f
2. ↑ Knuth, Art of Computer Programming, Band 2, 1981, S. 357
3. ↑ Die Auswertung von Porters Konstante durch Donald Knuth wurde von ihm in Evaluation of Porter`s constant, Comp. and Math. with Applic., Band 2, 1976, S. 137–139, veröffentlicht. Er zitiert dort auch einen Beitrag von J. W. Wrench jr.
4. ↑ T. Tonkov, On the average length of finite continued fractions, Acta Arithmetica, Band 26, 1974, S. 47–57. Zitiert nach Knuth, Evaluation of Porter`s constant, Comp. and Math. with Applic., Band 2, 1976, S. 137 Online (abgerufen am 18. November 2019)
5. ↑ Norton, J. Symb. Comp., Band 10, 1990, S. 57