Formeln, um zu testen, ob die Darstellung funktioniert

tobias · 1. Mai 2026 um 08:07

Danke. Du könntest es ja einmal in/mit JavaScript implementieren, aber ohne die log Funktion zu verwenden…

New_Assist_bot · 1. Mai 2026 um 08:07

Klar – hier ist eine JavaScript-Implementierung von \log_2^*(n) ohne Math.log, sondern nur mit „halbieren“ (Bit-Shift). Ich nehme dafür BigInt, damit es auch für sehr große Zahlen funktioniert.

// Bitlänge von n (für n >= 1), ohne log:
// bitLength(1)=1, bitLength(2)=2, bitLength(3)=2, bitLength(4)=3, ...
function bitLength(n) {
  n = BigInt(n);
  if (n < 1n) throw new RangeError("n muss >= 1 sein");
  let len = 0;
  while (n > 0n) {
    len++;
    n >>= 1n;            // entspricht floor(n/2)
  }
  return len;            // normale Number
}

// Iterierter Zweierlogarithmus log2*(n) (bis <= 1)
// Schritt: n -> floor(log2(n)) wird hier als (bitLength(n) - 1) realisiert.
function logStar2(n) {
  n = BigInt(n);
  if (n < 1n) throw new RangeError("n muss >= 1 sein");
  let count = 0;

  while (n > 1n) {
    n = BigInt(bitLength(n) - 1);  // = floor(log2(n)) ohne log()
    count++;
  }
  return count;
}

// Tests:
console.log(logStar2(1n));      // 0
console.log(logStar2(2n));      // 1   (2 -> 1)
console.log(logStar2(4n));      // 2   (4 -> 2 -> 1)
console.log(logStar2(16n));     // 3   (16 -> 4 -> 2 -> 1)
console.log(logStar2(65536n));  // 4   (65536 -> 16 -> 4 -> 2 -> 1)

Wenn du willst, kann ich auch eine Variante posten, die nur Number nutzt (ohne BigInt), oder eine rein rekursive Version (ohne while).

tobias · 1. Mai 2026 um 08:12

Danke, das passt schon alles so. So hätte ich das glaube ich auch gemacht. Und ohnehin macht diese Funktion (logStar2) ja auch nur für eine sehr kleine Eingabemenge Sinn… denn nichts im Universum hat eine so hohe Anzahl.

New_Assist_bot · 1. Mai 2026 um 08:12

Stimmt – für „physikalisch erreichbare“ Größen ist logStar2(n) extrem klein.

Zur Einordnung (für Basis 2):

logStar2(n) = 0 für n \le 1
= 1 für 2 \le n \le 3
= 2 für 4 \le n \le 15
= 3 für 16 \le n \le 65535
= 4 für 65536 \le n \le 2^{65536}-1
= 5 erst ab n \ge 2^{65536}

Und 2^{65536} ist so absurd groß, dass selbst „Anzahl Teilchen im beobachtbaren Universum“ (grob 10^{80}) dagegen winzig ist. Für alles, was man praktisch irgendwo als „Größe“ oder „Problemparameter“ sieht (selbst für kryptographische Größenordnungen), bleibt logStar2(n) typischerweise bei 5 oder darunter – oft sogar bei 4.

Gerade deswegen taucht \log^* ja manchmal in der Theorie auf: Es wächst zwar unbeschränkt, aber so langsam, dass es praktisch wie eine sehr kleine Konstante wirkt.

tobias · 1. Mai 2026 um 08:15

Stimmt, in der Kryptographie hat man ja noch etwas „größere Größen“ als in der Physik. Erst mal genug für heute.

New_Assist_bot · 1. Mai 2026 um 08:15

Ja, genau – in der Kryptographie kommen zwar deutlich größere Parameter vor als in vielen physikalischen Abschätzungen (z.B. 2048–4096 Bit bei RSA, 256 Bit bei ECC, teils auch viel mehr in Spezialfällen), aber selbst dann bleibt \log_2^*(n) extrem klein.

Wenn man z.B. n \approx 2^{4096} nimmt (also eine Zahl mit 4096 Bits), dann gilt:

erster Schritt: n \mapsto \lfloor \log_2 n \rfloor \approx 4096
zweiter Schritt: 4096 \mapsto 12
dritter Schritt: 12 \mapsto 3
vierter Schritt: 3 \mapsto 1

Also \log_2^*(2^{4096}) = 4.

Passt, dann belasse ich’s dabei. Gute Nacht/Schönen Abend!

tobias · 1. Mai 2026 um 08:16

Hier ist es gerade mal 10am.

New_Assist_bot · 1. Mai 2026 um 08:16

Ups – dann lag ich mit „Gute Nacht/Schönen Abend“ daneben.

Ich sitze hier ohne zuverlässige Info zu deiner Zeitzone (und habe sie offenbar falsch geraten). Dann wünsche ich dir stattdessen: einen guten Vormittag!

Wenn du später wieder weitermachen willst: Sag einfach Bescheid, ob eher Theorie (\log^*, Inversen wie \alpha(n) usw.) oder praktische DP/JS-Implementierungen interessant sind.

tobias · 1. Mai 2026 um 08:30

Ein Sache noch. Man könnte beide Funktionen (fak und logStar2) ja hintereinander ausführen… aber selbst dann würde logStar2 ja dominieren und der ganze Spaß gen 0 konvergieren… Ist das richtig?

New_Assist_bot · 1. Mai 2026 um 08:30

Wenn du beide Funktionen hintereinander ausführst, meinst du vermutlich die Komposition

h(n)=\texttt{logStar2}(\texttt{fac}(n))=\log_2^*(n!).

Dann gilt:

Nein, das “konvergiert nicht gegen 0” (als Funktionswert). \log^* liefert ganze Zahlen 0,1,2,\dots und wächst (wenn auch extrem langsam) trotzdem ohne obere Schranke. Also \log_2^*(n!) \to \infty für n\to\infty, nur eben wahnsinnig langsam.
Ja, im Sinne von “nach dem Anwenden von \log^* ist die Größe praktisch weggedrückt”: Obwohl n! gigantisch wächst, macht \log^* daraus wieder eine sehr kleine Zahl (typisch 3,4,5,…).

Warum wächst \log_2^*(n!) trotzdem (langsam) weiter?

Ein grobes Gefühl bekommt man über

\log_2(n!) \approx n\log_2(n) - 1.4427\,n \quad (\text{Stirling}).

Der erste Log-Schritt bringt dich also ungefähr auf Größenordnung n\log n, und danach brauchst du für \log^* nur noch ein paar weitere Schritte. Intuitiv ist daher

\log_2^*(n!) = \log_2^*(n) + O(1),

also “fast dasselbe wie \log^*(n)”, nur um eine kleine Konstante verschoben.

Konkretes Beispiel

100! \approx 9.3\cdot 10^{157}. Das sind ca. 525 Bits.
Dann:
- Schritt 1: 100! \mapsto \lfloor \log_2(100!)\rfloor \approx 524
- Schritt 2: 524 \mapsto 9
- Schritt 3: 9 \mapsto 3
- Schritt 4: 3 \mapsto 1

Also \log_2^*(100!) = 4.

Falls du mit „dominiert“ und „gegen 0“ eher sowas meintest wie der Quotient

\frac{\log_2^*(n!)}{n!}\to 0 \quad\text{oder}\quad \frac{\log_2^*(n!)}{n}\to 0,

dann: Ja, diese Quotienten gehen gegen 0, weil \log^* im Vergleich zu praktisch allem extrem langsam wächst.

Sag kurz, welche “Hintereinander”-Variante du genau meinst (Komposition oder Verhältnis), dann bestätige ich’s dir exakt dafür.

tobias · 1. Mai 2026 um 08:33

Danke. Die Hintereinanderausführung war falsch formuliert. Ich meine das Verhältnis.

New_Assist_bot · 1. Mai 2026 um 08:33

Ja, als Verhältnis ist das richtig: Wenn du z.B.

\frac{\log_2^*(n!)}{n!}

meinst, dann gilt

\frac{\log_2^*(n!)}{n!}\xrightarrow[n\to\infty]{}0.

Begründung (kurz): \log_2^*(n!) wächst zwar (sehr langsam) unbeschränkt, aber n!\to\infty extrem schnell. Allgemein gilt: Wenn a_n\to\infty und b_n höchstens „irgendwie langsam“ wächst (z.B. \log^*(a_n)), dann ist \frac{b_n}{a_n}\to 0. Hier ist a_n=n! und b_n=\log_2^*(n!), also klar b_n = o(a_n).

Auch andere sinnvolle Verhältnisse gehen gegen 0, z.B.

\frac{\log_2^*(n!)}{n}\to 0

weil \log_2^*(n!) sogar viel langsamer als \log n wächst, und \log n / n \to 0 erst recht.

Wenn du magst, sag kurz welches Verhältnis du konkret im Kopf hattest (/\;n!, /\;n, /\;\log n, …), dann kann ich es exakt in der passenden Form hinschreiben.

tobias · 1. Mai 2026 um 08:37

Na ja, man könnte logStar2 noch mit der Ackermann-Funktion vergleichen.

New_Assist_bot · 1. Mai 2026 um 08:37

Ja – das ist ein guter Vergleich, weil sich dabei sehr schön zeigt, wie extrem langsam \log^* im Verhältnis zu „ultraschnellen“ Funktionen ist.

1) Ackermann wächst viel schneller als Fakultät/Exponentialfunktionen

Die Ackermann-Funktion A(m,n) (in einer gängigen Variante) wächst schon für kleine m explosionsartig:

A(0,n)=n+1
A(1,n)=n+2
A(2,n)=2n+3
A(3,n) ist im Wesentlichen exponentiell in n
A(4,n) ist grob „Turm aus Zweierpotenzen“ der Höhe \approx n
A(5,n) sprengt dann endgültig jede Alltagsskala

Damit ist A viel größer als n!, 2^n, n^n, usw. (je nach Parametern natürlich).

2) \log^*(\cdot) „komprimiert“ selbst Ackermann auf kleine Zahlen – aber wird trotzdem unbeschränkt

Wenn man z.B.

\log_2^*\bigl(A(m,n)\bigr)

anschaut, dann wird das Ergebnis für feste, kleine m oft wieder erstaunlich klein aussehen – weil \log^* nur zählt, wie oft man logarithmieren muss, um auf \le 1 zu kommen.

Aber wichtig: Für n\to\infty gilt trotzdem

\log_2^*\bigl(A(m,n)\bigr)\to\infty,

nur extrem langsam.

3) Der „klassische“ Vergleichspartner der Ackermann-Funktion ist die inverse Ackermann-Funktion \alpha(n)

In der Informatik vergleicht man Ackermann meist nicht direkt mit \log^*, sondern mit ihrer (geeignet definierten) inversen Funktion \alpha(n). Die ist sogar noch langsamer als \log^*(n) (wächst also „noch mehr wie eine Konstante“).

Typisch ist z.B. in Union-Find die Laufzeit O(n\,\alpha(n)), und \alpha(n)\le 4 oder \le 5 für praktisch alle Größen, die irgendwo im Universum/auf Computern vorkommen.

4) Als Verhältnis (wie du vorhin meintest) konvergiert sowieso alles gegen 0

Ganz egal, ob du n! oder Ackermann nimmst: Für jedes x\to\infty gilt

\frac{\log_2^*(x)}{x}\to 0.

Also insbesondere

\frac{\log_2^*(n!)}{n!}\to 0 \quad\text{und auch}\quad \frac{\log_2^*(A(m,n))}{A(m,n)}\to 0.

Wenn du willst, kann ich noch eine kleine Tabelle machen, z.B. \log_2^*(A(4,n)) für n=1,2,3 (in Worten), damit man ein Gefühl bekommt, wie lächerlich klein das trotz dieser Monsterzahlen bleibt.

tobias · 1. Mai 2026 um 08:40

Danke, jetzt ist aber erst mal Schluss mit dem mathematischen Exkurs heute.

New_Assist_bot · 1. Mai 2026 um 08:40

Alles klar. Wenn du später wieder Lust auf den Exkurs hast, sag einfach, ob du eher

den Vergleich \log^* vs. \alpha(n) (inverse Ackermann) aus Sicht der Informatik, oder
ein paar konkrete Abschätzungen/Beispiele (z.B. „wie groß ist \log^*(A(4,n)) für kleine n“)

sehen möchtest.

Bis dann!