TI-57 Fakultäten - Teil 3
Stirling-Formel
Zur ungefähren Ermittlung des Werts großer Fakultäten, deren exakte schrittweise Bestimmung zu langwierig wäre, bedient man sich einer geeigneten Näherung. Am bekanntesten ist die Stirling-Formel:
n! ~ (2 \pi n)^1/2 × (n/e)^n
Ihr Wert kommt dem der Fakultät n! mit wachsendem n immer näher. Eine modifizierte Form stellt eine genauere Approximation dar, die sich gut zur Auswertung mittels Taschenrechner eignet:
n! ~ (2 \pi n)^1/2 × (n/e)^n × e^1/(12n)
Anstelle von n-1 Multiplikationen zur Berechnung von n! ist nur ein gutes Dutzend arithmetischer Operationen auszuführen; ein Vorteil, der für große n schwer wiegt.
Die Grenzen des Zahlenbereichs lassen sich auch hier leicht überwinden, indem Mantisse und Exponent in zwei Gleitkommazahlen vorgehalten werden. Der Einfachheit halber wird dazu die Normierungsroutine (SBR 0) aus Teil 2 wiederverwendet. Den größten Faktor schreibt man zweckmäßig um:
(n/e)^n = 10^(n × log(n/e))
= 10^FRAC(n × log(n/e)) × 10^INT(n × log(n/e))
= 10^[n × log(n/e) - INT(n × log(n/e))] × 10^INT(n × log(n/e))
= Mantisse × 10^Exponent
Das Programm berechnet die Mantisse als AOS-Ausdruck, während es den Exponenten separat in Register 7 speichert bzw. per Registerarithmetik mit der Anweisung 'SUM 7' bilanziert.
Ein so simpler Algorithmus spart zwar Programmspeicher, glänzt dafür weniger in puncto Präzision. Aus dem Ausdruck n × log(n/e) in Gl. 3 kommen von den 11 Stellen der Gleitkommazahl für die Mantisse nur die Nachkommastellen zum Tragen. In der letzten Stelle laufen Rundungsfehler auf, d.h. sie ist als unsicher anzusehen, evtl. auch die vorletzte Stelle. Um mindestens eine sichere Stelle zu bestimmen, dürfen höchstens 9 Vorkammastellen vorhanden sein. Damit ist n zumindest beschränkt auf:
INT(n × log(n/e)) < 10^9, d.h.
n < 130 202 808
Tatsächlich liefert das Programm schon für n > 1E8 infolge von Rundungsfehlern keine verläßlichen Werte. Eine weitere Fehlerabschätzung erbringt max. 8 Stellen Genauigkeit für zweistellige n und durchgängig mindestens 5 genaue Stellen sind im Bereich 7 < n < 200 000 zu erwarten.
Programm: Stirling-Formel
n < 1E8
LRN (bei Neubeginn) oder:
GTO 2nd 09 LRN (Überschreiben des Programms aus Teil 2)
Programmschritt
| Anzeige
| | Anweisung
| | | Bemerkung
| | | |
00 86 0 2nd Lbl 0 **Unterprogramm Normierung
01 45 ÷
02 18 2nd log
03 49 2nd Int Größenordnung
04 34 7 SUM 7 Exponent erhöhen
05 -18 2nd INV log Divisor zur Normierung der Mantisse
06 85 = normierte Mantisse
07 -42 INV EE Aufhebung der Gleitkommadarstellung
08 -61 INV SBR Rücksprung
09 86 1 2nd Lbl 1 **Programm Stirling
10 32 0 STO 0 Sichern von n
11 45 ÷
12 01 1
13 -13 INV lnx exp(1)
14 85 =
15 18 2nd log
16 55 ×
17 33 0 RCL 0 n
18 65 -
19 49 2nd Int
20 32 7 STO 7 Startwert Exponent
21 85 = FRAC
22 -18 2nd INV log Mantisse
23 55 ×
24 43 (
25 02 2
26 55 ×
27 30 2nd \pi
28 55 ×
29 33 0 RCL 0 n
30 44 )
31 24 √x
32 55 ×
33 43 (
34 33 0 RCL 0 n
35 55 ×
36 01 1
37 02 2
38 44 )
39 25 1/x
40 -13 INV lnx exp( 1/(12n))
41 85 =
42 61 0 SBR 0 Normierung zur Ausgabe
43 -61 INV SBR Ende Stirling
LRN (Ende der Programmeingabe)Beispiel 69!
69 SBR 1
Ergebnis nach 5 Sekunden Rechenzeit:
1.7112245
Wechsel auf Anzeige des Exponenten mit x<->t:
98.
Also:
1.7112245 E98
Alle 11 Stellen der Mantisse ausgelesen:
1.7112245018 E98
8 genaue Stellen
Vergleich
Nun interessiert vor allem, wie sich die Methode aus Teil 2 (schrittweise Multiplikation von Gleitkommazahlen) gegen die Stirling-Formel behauptet. Stellen wir also ein paar Rechenergebnisse gegenüber:
| n | n! (n-1 Multiplikationen) |
f~n! (modifizierte Stirling-Formel) |
Genaue Stellen |
|---|---|---|---|
| 69 | 1.7112245227 E98 (1m45s) | 1.7112245018 E98 (5s) | 9 / 8 |
| 100 | 9.3326215296 E157 (2m40s) | 9.3326217873 E157 (5s) | 8 / 6 |
| 253 | 5.17346097 E499 (7m) | 5.1734604418 E499 (5s) | 8 / 7 |
| 449 | 3.8519304876 E997 (12m15s) | 3.8519301084 E997 (5s) | 7 / 7 |
| 1000 | 4.023872524 E2567 (27m) | 4.0238735516 E2567 (5s) | 7 / 7 |
| 5000 | 4.2285775164 E16325 (5h17m) | 4.2285665889 E16325 (5s) | 7 / 5 |
| 10 000 |
- | 2.8462664450 E35659 | - / 6 |
| 100 000 |
- | 2.8242315197 E456573 | - / 5 |
| 1 000 000 |
- | 8.263993567 E5565708 | - / 5 |
| 10 000 000 |
- | 1.2025134351 E65657059 | - / 4 |
| 100 000 000 |
- | 1.6184151472 E756570556 | - / 3 |
(Rechenzeiten in Klammern)
Im direkten Vergleich fällt die von Anfang an langsam abnehmende Genauigkeit der schrittweisen Berechnung auf, eine Folge zunehmender Rundungsfehler. Mit der modifizierten Stirling-Formel hingegen gewinnt man bis etwa n=1000 an Genauigkeit, wie erwartet geht sie aber auf Grund des einfachen Auswertungsverfahrens für größere Werte wieder verloren. Stellt man keine zu hohen Anforderungen an die Genauigkeit, so liefert die Stirling-Formel brauchbare Näherungswerte für n! bis etwa n = 1E8.
Danke für's Interesse an großen Zahlen im kleinen Rechner TI-57!
Gruß
Thorsten
