Logarithmus

Standardmäßig wird die ganzzahlige Exponentiation definiert als $a^n = \underbrace{a\cdot\ldots\cdot a}_{n\times}$, bzw. rekursiv als $a^n = \left\{\begin{array}{cl} a & \mbox{ für } n=1 \\ a\cdot a^{n-1} & \mbox{ für } n>1\end{array}\right.$

Die $n$-te Wurzel $\sqrt[n]{a}$ wird definiert als die positive Lösung der Gleichung $x^n=a$.

Negative Exponenten

Man sieht schnell, dass für alle $m>n>1$ gilt $\frac{a^m}{a^n}=a^{m-n}$. Es stellt sich heraus, dass man dies in konsistenter Weise auch für $n\ge m$ so definieren kann. Damit wird $a^0=1$ und $a^{-n}=\frac{1}{a^n}$.

Man überprüft leicht, dass die bekannten Potenzgesetze immernoch gelten. Eine "Grauzone" ist aber zum Beispiel, was $0^0$ ist.

Rationale Exponenten

Ebenfalls stellt man schnell fest, dass für $n\mid m$ gilt $\sqrt[n]{a^m} = a^{\frac{m}{n}}$. Auch dies kann man in konsistenter Weise als Definition für generelle rationale Exponenten nutzen: Jede rationale Zahl lässt sich darstellen als Bruch $\frac{p}{q}$, und man definiert $a^{\frac{p}{q}} := \sqrt[q]{a^p}$.

Auch hier kann man schnell überprüfen, dass die Potenzgesetze noch gelten.

Reelle Exponenten

Für allgemeine reelle Exponenten bräuchte die saubere Definition etwas mehr mathematisches Werkzeug, wir begnügen uns hier mit intuitivem Verständnis.

Für positives $a$ ist die Funktion $x\mapsto a^x$ streng monoton steigend, das heißt, $x < y$ impliziert $a^x < a^y$. Wenn wir nun $a^r$ für ein irrationales $r$ berechnen wollen, so stellen wir fest, dass wir rationale Zahlen $k, l$ mit $k<r<l$ finden, die beliebig nah an $r$ herankommen, das heißt, $|l-k|$ wird beliebig klein. Wegen der Monotonizität wird dann aber $|a^l-a^k|$ ebenfalls beliebig klein, und $a^l$ bzw. $a^k$ nähern sich beliebig genau einer bestimmten reellen Zahl. Wir definieren $a^r$ einfach als diese Zahl.

Wir können auf diese Weise beliebig genaue Näherungen von $a^r$ berechnen.

Logarithmus

Gegeben sei die Gleichung $a^b=c$. Haben wir $a$ und $b$ gegeben, können wir $c$ leicht ausrechnen. Haben wir umgekehrt $b$ und $c$ gegeben, ist $a=c^{\frac{1}{b}}$ ebenfalls leicht auszurechnen. Was wir noch nicht können, ist, auszurechnen, was $b$ sein muss, wenn wir $a$ und $c$ gegeben haben. Dieses $b$ nennt man den Logarithmus zur Basis $a$ von $c$, und schreibt $\log_a c$.

Logarithmen haben einige schöne Eigenschaften.

Zunächst ist $\log_a (b\cdot c) = \log_a b + \log_a c$. Das sieht man leicht, indem man sich überlegt, dass wenn $a^x=b$ und $a^y=c$ ist, dann $a^{x+y}=a^x\cdot a^y = b\cdot c$. Auf diesem Prinzip basieren Rechenschieber.

Weiterhin ist $\log_b x = \frac{\log_a x}{\log_a b}$. Denn ist $b^y=x$, und $a^z=b$, so ist $(a^z)^y=a^{zy}=x$, also $\log_a x=zy = \log_a b \cdot \log_b x$.

Logarithmen sind also proportional zueinander. Deshalb haben die meisten Taschenrechner keine zweistellige Logarithmusfunktion, sondern nur $\ln = \log_e$, den natürlichen Logarithmus, zur Basis $e$, der Euler'schen Zahl, die rund $2,718281828$ ist. Die genaue Bedeutung der Zahl $e$ ist für den Kurs nicht wichtig. Oft schreibt man auch einfach nur $\log x$, je nach dem meint man damit den natürlichen Logarithmus, manchmal auch den Logarithmus zur Basis 10. Wir verwenden Logarithmen im Kurs hauptsächlich zur Beschreibung von Komplexitätsklassen, bei denen es auf lineare Faktoren nicht ankommt. Wenn wir im Kurs $\log x$ schreiben, ist die Basis entsprechend nicht relevant.

$\lceil\log_{10} a\rceil$ gibt an, wie viele Dezimalstellen $a$ vor dem Komma hat. Analog gibt $\lceil\log_2 a\rceil$ an, wie viele Binärstellen $a$ hat.

Ausblick: Komplexe Exponenten

Auch wenn wir das im Kurs nicht brauchen, sei hier ein Ausblick auf komplexe Exponenten gegeben. Die Euler'sche Zahl $e$ ist definiert als

$\begin{align}e &= 1 + \frac{1}{1} + \frac{1}{1 \cdot 2} + \frac{1}{1 \cdot 2 \cdot 3} + \frac{1}{1 \cdot 2 \cdot 3 \cdot 4} + \dotsb \\ &= \frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} + \dotsb \\ &= \sum_{k=0}^{\infty}{\frac{1}{k!}} \\ \end{align}$

Man kann zeigen, dass

$e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!}$ für $x\in\mathbb{R}$, wobei man in diesem Fall $0^0=1$ setzt. Setzt man hier nun eine imaginäre Zahl $i\varphi$ ein, so erhält man

$\begin{align} e^{i\varphi}& \\ &= \sum_{k=0}^{\infty} \frac{(i\varphi)^k}{k!} \\ &= \sum_{k=0}^{\infty} \frac{(i\varphi)^{2k}}{(2k)!} + \sum_{k=0}^{\infty} \frac{(i\varphi)^{2k+1}}{(2k+1)!} \\ &= \sum_{k=0}^{\infty} \frac{(-1)^k \varphi^{2k}}{(2k)!} + \sum_{k=0}^{\infty} \frac{i(-1)^k\varphi^{2k+1}}{(2k+1)!} \\ &= \sum_{k=0}^{\infty} \frac{(-1)^k \varphi^{2k}}{(2k)!} + i\sum_{k=0}^{\infty} \frac{(-1)^k\varphi^{2k+1}}{(2k+1)!} \\ &= \cos \varphi + i\cdot \sin \varphi \end{align}$

Insbesondere ist also $e^{i\pi} + 1 = 0$ (bekannte Formel).

Um nun von $e^{i\varphi}$ zu beliebigem $a^{i\varphi}$ zu kommen, können wir wiederum den Logarithmus verwenden: $a^{i\varphi} = (e^{\log_e a})^{i\varphi} = e^{i\varphi\log_e a}$. Und für komplexe Exponenten dann $a^{x+iy} = a^x\cdot a^{iy}$.

Binary Search

In vielen Problemen in der Informatik tritt der Logarithmus natürlich auf. Ein Beispiel stellt Binärsuche dar. Man stelle sich vor, man hätte eine sortierte Liste von Zahlen:

   22  23  39  45  47  55  58  59  61  67  69

Angenommen wir wollen feststellen, ob eine bestimmte Zahl, zum Beispiel 48, darin vorkommt. Die naive Methode wäre, einfach alle Elemente durchzugehen, und mit der Zahl zu vergleichen. Dazu müssten wir im schlimmsten Fall so viele Zahlen vergleichen, wie Elemente in der Liste sind. Da wir wissen, dass die Liste sortiert ist, geht es aber schneller:

Wir schauen uns zunächst nur das mittlere Element an, und vergleichen es. Ist es gleich unserer Zahl, sind wir fertig. Ist es kleiner als unsere Zahl, so wissen wir, dass die Zahl höchstens rechts von uns stehen kann, ist es größer, dann links.

                      > 48
                        ↓
   22  23  39  45  47  55  58  59  61  67  69

Damit können wir alle Elemente die rechts oder links von der Zahl stehen ignorieren, effektiv stehen wir also vor dem selben Problem, aber jetzt mit einer Liste die nur rund halb so lang ist, deren Mitte wir wieder anschauen können, und immer so weiter:

           < 48
            ↓
   22  23  39  45  47

              < 48
                ↓
           39  45  47

                  < 48
                    ↓
                   47

Am Ende bleibt nur noch ein Element übrig. Wenn das nicht gleich dem gesuchten Element ist wissen wir, dass es nicht vorkommt.

Mit jedem Schritt halbiert sich die Anzahl der Elemente die übrig sind. Das heißt, wenn wir am Anfang $n$ Elemente haben, haben wir nach $k$ schritten rund $(\frac{1}{2})^k\cdot n$ Elemente übrig. Das heißt, wir sind ungefähr fertig, wenn $(\frac{1}{2})^k\cdot n \approx 1$, also $n \approx 2^k$, also $k \approx \log_2 n$.

Eine ähnliche Strategie kann man zum Beispiel verwenden, um Wörterbücher zu durchsuchen.