Pfeilschreibweise

aus Wikipedia, der freien Enzyklopädie

In der Mathematik ist die Pfeilschreibweise eine Methode, die Donald Ervin Knuth 1976 entwickelte, um sehr große Zahlen zu schreiben. Sie ist eng verwandt mit der Ackermannfunktion. Die Idee basiert auf wiederholter Exponentierung, ebenso wie ein Exponent eine wiederholte Multiplikation ist und die Multiplikation eine wiederholte Addition ist.

Dies ist eine Übersetzung des englischen Artikels Knuths Pfeilschreibweise.

[Bearbeiten] Einführung

Die Multiplikation einer natürlichen Zahl kann als wiederholte Addition definiert werden.

$\begin{matrix} a \cdot b & = & \underbrace{a+a+\dots+a} \\ & & b\mbox{ Kopien von }a \end{matrix} .$

Zum Beispiel,

$\begin{matrix} 3\cdot 2 & = & \underbrace{3+3} & = & 6\\ & & 2\mbox{ Kopien von }3 \end{matrix} .$

Eine natürliche Zahl als Exponent $b$ kann als wiederholte Multiplikation definiert werden:

$\begin{matrix} a\uparrow b= a^b = & \underbrace{a\cdot a\cdot\dots\cdot a}\\ & b\mbox{ Kopien von }a \end{matrix} .$

Zum Beispiel,

$\begin{matrix} 3\uparrow 2= 3^2 = & \underbrace{3\cdot 3} & = & 9\\ & 2\mbox{ Kopien von }3 \end{matrix} .$

Dies inspirierte Knuth dazu einen „Doppelpfeil“-Operator für wiederholte Exponenten zu definieren:

$\begin{matrix} a\uparrow\uparrow b & = {\ ^{b}a} = & \underbrace{a^{a^{{}^{.\,^{.\,^{.\,^a}}}}}} & = & \underbrace{a\uparrow a\uparrow\dots\uparrow a} \\ & & b\mbox{ Kopien von }a & & b\mbox{ Kopien von }a \end{matrix}$

Zum Beispiel,

$\begin{matrix} 3\uparrow\uparrow 2 & = {\ ^{2}3} = & \underbrace{3^3} & = & \underbrace{3\uparrow 3} & = & 27 \\ & & 2\mbox{ Kopien von }3 & & 2\mbox{ Kopien von }3 \end{matrix} .$

Dieser Operator ist rechts assoziativ, das heißt er wird von rechts nach links ausgewertet:

Nach dieser Definition ist,

$3\uparrow\uparrow2=3^3=27$

$3\uparrow\uparrow3=3^{3^3}=3^{27}=7625597484987$

$3\uparrow\uparrow4=3^{3^{3^3}}=3^{7625597484987}$ (diese Zahl vollständig auszuschreiben würde ungefähr 1,37 Terabyte Speicherplatz belegen, also $7.625.597.484.987 \cdot \frac{\log 3}{\log 2}$ bits)

$3\uparrow\uparrow5=3^{3^{3^{3^3}}} = 3^{3^{7625597484987}}$

usw.

Dies führt bereits zu einigen sehr großen Zahlen, aber Knuth erweiterte seine Notation noch. Er führte einen „Dreifachpfeiloperator“ ein um wiederholte Anwendung des „Doppelpfeils“ darzustellen.

$\begin{matrix} a\uparrow\uparrow\uparrow b= & \underbrace{a_{}\uparrow\uparrow a\uparrow\uparrow\dots\uparrow\uparrow a}\\ & b\mbox{ Kopien von }a \end{matrix}$

gefolgt von einem „Vierfachpfeiloperator“:

$\begin{matrix} a\uparrow\uparrow\uparrow\uparrow b= & \underbrace{a_{}\uparrow\uparrow\uparrow a\uparrow\uparrow\uparrow\dots\uparrow\uparrow\uparrow a}\\ & b\mbox{ Kopien von }a \end{matrix}$

und so weiter. Die allgemeine Regel dazu lautet, dass ein $n$ -fach Pfeiloperator zu einer $n$ -fachen Wiederholung eines $n - 1$ fachen Pfeiloperators wird:

$\begin{matrix} a\ \underbrace{\uparrow_{}\uparrow\!\!\dots\!\!\uparrow}\ b= a\ \underbrace{\uparrow\!\!\dots\!\!\uparrow} \ a\ \underbrace{\uparrow_{}\!\!\dots\!\!\uparrow} \ a\ \dots \ a\ \underbrace{\uparrow_{}\!\!\dots\!\!\uparrow} \ a \\ \quad\ \ \,n\qquad\ \ \ \underbrace{\quad n_{}\!-\!\!1\quad\ \,n\!-\!\!1\qquad\quad\ \ \ \,n\!-\!\!1\ \ \ } \\ \qquad\qquad\quad\ \ b\mbox{ Kopien von }a \end{matrix}$

Beispiele:

$3\uparrow\uparrow\uparrow2 = 3\uparrow\uparrow3 = 3^{3^3} = 3^{27}=7,625,597,484,987$

$\begin{matrix} 3\uparrow\uparrow\uparrow3 = 3\uparrow\uparrow3\uparrow\uparrow3 = 3\uparrow\uparrow(3\uparrow3\uparrow3) = & \underbrace{3_{}\uparrow 3\uparrow\dots\uparrow 3} \\ & 3\uparrow 3\uparrow 3\mbox{ Kopien von }3 \end{matrix} \begin{matrix} = & \underbrace{3_{}\uparrow 3\uparrow\dots\uparrow 3} \\ & 7.625.597.484.987 \mbox{ Kopien von }3 \end{matrix}$

[Bearbeiten] Notation

In Ausdrücken wie $a b$ , wird in der Schreibweise der Exponent $b$ für gewöhnlich hochgestellt gegenüber der Basis $a$ . Allerdings lassen viele Umgebungen — wie beispielsweise Programmiersprachen und Klartexte wie E-Mail — solche zweidimensionalen Layouts nicht zu. Man hat sich hier mit der Notation $a \uparrow b$ beholfen. Der Pfeil soll als 'Erhöhung des Exponenten' gelesen werden. Lässt die Umgebung keinen Pfeil zu, wird statt dessen das Zirkumflex ^ genutzt.

Die hochgestellte Schreibweise $a b$ bietet sich nicht zu einer Verallgemeinerung an. Deshalb hat Knuth die Pfeilnotation gewählt, die stattdessen ein einer Zeile geschrieben werden kann.

Im Kontext der Programmiersprache C, wird das ^ Zeichen für den XOR Operator verwendet. Hier wird ** als alternative zum $\uparrow$ genutzt. Dabei kommt hier ebenfalls die wiederholte Schreibung zum Einsatz, die eine wiederholte Anwendung des einzelnen Operators bedeuten soll. Es wäre also möglich *** als Äquivalent zum Doppelpfeil $\uparrow\uparrow$ zu nutzen, dies ist allerdings nicht gebräuchlich.

[Bearbeiten] Definition

Die Pfeilnotation wird formal definiert durch

$a\uparrow^n b= \left\{ \begin{matrix} a^b, & \mbox{wenn }n=1; \\ 1, & \mbox{wenn }b=0; \\ a\uparrow^{n-1}(a\uparrow^n(b-1)), & \mbox{sonst} \end{matrix} \right.$

für alle natürlichen Zahlen $a, b, n$ für die gilt $b \ge 0, n \ge 1$ .

$\uparrow^n$ bedeutet hier $n$ nebeneinanderstehende Pfeile (z.B. $a \uparrow^3 b = a \uparrow \uparrow \uparrow b$ ).

Alle Pfeiloperatoren (normale Exponentenschreibweise wird hierbei als $a \uparrow b$ angesehen) sind rechtsassoziativer Operatoren, das heißt bei mehreren Operatoren wird der Ausdruck von rechts nach links ausgewertet. Zum Beispiel gilt allgemein: $a \uparrow b \uparrow c = a \uparrow (b \uparrow c)$ , nicht $(a \uparrow b) \uparrow c$ ; zum Beispiel
$3\uparrow\uparrow 3=3^{3^3}$ ist $3^{(3^3)}=3^{27}=7625597484987$ nicht $\left(3^3\right)^3=27^3=19683.$

Für diese rechtsassoziativität gibt es einen guten Grund. Würden wir von links nach rechts auswerten, dann würde $a \uparrow\uparrow b$ dasselbe ergeben wie $a \uparrow (a \uparrow (b - 1))$ , so dass $\uparrow\uparrow$ keinen neuen Operator ergeben würde. Siehe hierzu auch Potenzturm.

[Bearbeiten] Siehe auch

[Bearbeiten] Literatur

Donald E. Knuth: Coping With Finiteness. In: Science. 194, Nr. 4271, Dezember 1976, S. 1235-1236.

Guido Walz (Red.): Pfeilnotation. In: Lexikon der Mathematik. 4. Moo bis Sch, Spektrum Akademischer Verlag, Heidelberg 2002, ISBN 3-8274-0436-3.
Robert Munafo: Large Numbers

Kategorie: Mathematische Notation

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Pfeilschreibweise

aus Wikipedia, der freien Enzyklopädie

Inhaltsverzeichnis

[Bearbeiten] Einführung

[Bearbeiten] Notation

[Bearbeiten] Definition

[Bearbeiten] Siehe auch

[Bearbeiten] Literatur

Views

Navigation

Mitmachen

Suche

Andere Sprachen