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 Bearbeiten

Allgemein wird mithilfe des euklidischen Algorithmus der größte gemeinsame Teiler   von zwei positiven natürlichen Zahlen   und   bestimmt. Die Anzahl der Schritte des Algorithmus sei  , die mittlere Anzahl der Schritte bei festem n ist:

 .

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

 

wobei   die Eulersche Phi-Funktion ist und

 

Porter zeigte 1975:

 

Dabei stellt   ein Landau-Symbold dar und   ist beliebig.

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

 

Dabei steht:

Der Vorfaktor des führenden logarithmischen Terms wurde schon zuvor von Hans Arnold Heilbronn (er fand einen Fehlerterm  , der von T. Tonkov auf   verbessert wurde)[4] und unabhängig von John D. Dixon erhalten.

Betrachtet man das Mittel über  :

 ,

bewies Norton 1990:[5]

 

mit beliebigem  .

Literatur Bearbeiten

  • 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)

Einzelnachweise Bearbeiten

  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