Goldener Schnitt/Verwendung in Informatik und Numerik

Datenstrukturen

In der Informatik werden Daten in Hashtabellen gespeichert, um darauf schnell zuzugreifen. Die Position $h(k)$, an der ein Datensatz $k$ in der Tabelle gespeichert wird, berechnet sich durch eine Hashfunktion $h$. Für einen effizienten Zugriff müssen die Datensätze möglichst gleichmäßig verteilt in die Tabelle geschrieben werden. Eine Variante für die Hashfunktion ist die multiplikative Methode, bei der die Hashwerte für eine Tabelle der Größe $m$ nach der folgenden Formel berechnet werden:

$h(k)=\lfloor m(kA-\lfloor kA\rfloor )\rfloor$

Dabei stellen $\lfloor \dots \rfloor$ Gaußklammern dar, die den Klammerinhalt auf die nächste ganze Zahl abrunden. Der Informatiker Donald E. Knuth schlägt für die frei wählbare Konstante $A=1/\mathrm{\Phi }$ vor, um eine gute Verteilung der Datensätze zu erhalten.

Verfahren des Goldenen Schnittes

Das Verfahren des Goldenen Schnittes (auch: Goldener-Schnitt-Verfahren, Methode des Goldenen Schnittes oder Suchverfahren Goldener Schnitt) ist ein Verfahren der mathematischen nichtlinearen Optimierung, genauer berechnet es algorithmisch eine numerische Näherung für eine Extremstelle (Minimum oder Maximum) einer reellen Funktion einer Variablen in einem Suchintervall $[a,b]$. Es basiert auf der analytischen Anwendung der ursprünglich geometrisch definierten stetigen Teilung. Im Gegensatz zum Intervallhalbierungsverfahren wird dabei das Suchintervall nicht bei jedem Schritt halbiert, sondern nach dem Prinzip des Goldenen Schnittes verkleinert. Der verwendete Parameter $\tau$ (tau) hat dabei nicht, wie bei dem allgemeineren Bisektionsverfahren, den Wert $\frac{1}{2}$, sondern es wird $\tau =\mathrm{\Phi }-1$ gewählt, sodass sich zwei Punkte $x=b-\tau (b-a)$ und $x^{\prime }=a+\tau (b-a)$ für das Optimierungsverfahren ergeben, die das Suchintervall im Goldenen Schnitt teilen.

Wird angenommen, dass jeder Punkt in jedem Intervall mit gleicher Wahrscheinlichkeit Extrempunkt sein kann, führt dies bei Unbestimmtheitsintervallen dazu, dass das Verfahren des Goldenen Schnittes um 14 % effektiver ist als die Intervallhalbierungsmethode. Im Vergleich zu diesem und weiteren sequentiellen Verfahren ist es – mathematisch gesehen – das für allgemeine Funktionen effektivste Verfahren; nur im Fall differenzierbarer Funktionen ist es der direkten mathematischen Lösung unterlegen. Dass sich dieses Verfahren in der manuellen Rechnung nicht durchgesetzt hat, liegt vor allem an den notwendigen Wurzelberechnungen für die einzelnen Zwischenschritte.

Anzahl benötigter Divisionen im euklidischen Algorithmus

Der klassische euklidische Algorithmus berechnet den größten gemeinsamen Teiler $\mathrm{g}\mathrm{g}\mathrm{T}(m,n)$ zweier natürlicher Zahlen $m$ und $n$. Dabei müssen einige Divisionen durchgeführt werden. Je nach Beschaffenheit dieser Zahlen können aber mal mehr oder mal weniger Schritte erforderlich sein. Ist etwa $m=n$, so endet der Algorithmus nach nur einem Schritt, egal wie groß diese Zahlen sind. Der Goldene Schnitt taucht in der anderen Richtung auf, nämlich beschreibt er die Anzahl der Schritte für die Fälle, in denen ganz besonders viele Divisionen gebraucht werden (worst case analysis). Bezeichnet $L(m,n)$ die Anzahl der benötigten Divisionen und ist $Z_N=L(m,n)$, wobei $1\le m,n\le N$ zufällig ausgewählt werden, so gilt

$max(Z_N)\sim \frac{\log (N)}{\log (\mathrm{\Phi })}\approx \mathrm{2,07808692}\log (N)$.

Dies zeigt, dass der euklidische Algorithmus selbst in der schlechtest möglichen Situation immer noch (nur) logarithmische Laufzeit besitzt.

Auffälligkeit

Eine weitere Verbindung zwischen der Informationstheorie und dem Goldenen Schnitt wurde durch Helmar Frank mit der Definition der Auffälligkeit hergestellt. Er konnte zeigen, dass der mathematische Wert des Maximums der Auffälligkeit sehr nah an das Verhältnis des Goldenen Schnitts herankommt.