Das Kefk Network Wiki befindet sich im Testbetrieb.
Finis-Normalform
Aus Kefk.
Inhaltsverzeichnis |
Herkunft & Verwendung
Die Finis-Normalform (FNF) wurde von dem Informatiker Jan Finis zur Beschreibung von großen ganzen Zahlen, bei denen jedoch die einzelnen Primfaktoren bekannt sind bzw. die aus Primfaktoren zusammengesetzt werden, entwickelt. Im Zuge seiner Forschung über die Kombinatorik bei Puzzlespielen wie Sudoku und anderen komplexen kombinatorischen Problemen birgt diese Form eine normierte Darstellung großer Zahlen.
Darstellung
Die FNF stellt eine Zahl als ein 5-Tupel ihrer einstelligen Primfaktoren und der restlichen Faktoren >9 dar. Dabei benutzt die Notation folgende Schreibweise:(x1,x2,x3,x4,x5)FNF entspricht der Zahl 2x1 · 3x2 · 5x3 · 7x4 · x5. So wäre die Notation (12,5,6,14,524287)FNF eine Darstellung der Zahl 212 · 35 · 56 · 714 · 524287
Erweiterte FNF
Da die FNF für Computer entwickelt wurde stellt sich eine Darstellung der einstelligen Primfaktoren im Dezimalsystem als suboptimal heraus. Deshalb verwendet man bei der Berechnung von Problemen mit Hilfe der FNF im Computer die erweiterte Finis-Normalform (eFNF). Diese benutzt anstatt eines 5-Tupels ein 7-Tupel und schließt somit die beiden im Hexadezimalsystem einstelligen Primfaktoren 11(B) und 13(D) mit ein. Die Zahlen werden hier auch im Hexadezimalsystem angegeben. So stünde die Zahl (1A,C,6,21,BB,11,7FFFF)eFNF für 21A · 3C · 56 · 721 · BBB · D11 · 7FFFF. Durch diese Form wird der Platz in binär arbeitenden Computern besser genutzt.
Klassifikation von Zahlen mit Hilfe der FNF
Zahlen können anhand ihres letzten Faktors x5 (bzw. x7 in der eFNF) in 3 Klassen eingeteilt werden:
1. FNF vollständige Zahlen: Ist der letzte Faktor gleich 1 bedeutet dies, dass die Zahl vollständig durch einstellige Primfaktoren darstellbar ist. Sie wird deshalb FNF vollständig genannt. Eine FNF vollständige Zahl wird auch nur als 4- bzw. 6-Tupel geschrieben, indem man den letzten Faktor (1) weglässt und somit nochmals Platz einspart.
2. FNF faktorielle Zahlen: Eine Zahl wird FNF faktoriell genannt, wenn der letzte Faktor eine Primzahl ist. Die Zahl besitzt dann also nur einen Primfaktor >9 (bzw. >15 bei der eFNF), nämlich den letzte Faktor.
3. FNF unvollständige Zahlen: Ist der letzte Faktor weder 1 noch eine Primzahl, ist die Zahl FNF unvollständig.
Ist eine Zahl FNF vollständig oder FNF faktoriell entspricht ihre FNF einer kanonischen Primfaktorzerlegung.
Dazu gilt offensichtlich folgender Satz:
Satz 1: Die Multiplikation zweier FNF vollständiger Zahlen ergibt wieder eine FNF vollständige Zahl. So ergibt 9! · 2254 auf jeden Fall wieder eine FNF vollständige Zahl.
Anwendung
1. Zur minimierten Darstellung großer Zahlen: Vor allem FNF vollständige Zahlen können durch die FNF mit minimalem Platzbedarf dargestellt werden. So verfügt die Zahl (2,34,73,43) ausgeschrieben über mehrere hundert Dezimalstellen, in der FNF jedoch über gerade einmal 7 Stellen.
2. Zum schnellen rechnen mit FNF Zahlen: 2 FNF vollständige Zahlen können einfach dividiert/multipliziert werden, indem man die einzelnen Stellen der FNF subtrahiert/addiert. Bei FNF faktoriellen und unvollständigen Zahlen muss noch der letzte Wert dividiert/multipliziert werden, da dieser jedoch in der Regel sehr viel kleiner ist als die Zahl selbst ist auch bei FNF unvollständigen Zahlen die Zeitersparnis bemerkenswert.
Einordnung einiger wichtiger Zahlen in die FNF
n!: Jede Fakultät kleiner 11 ergibt natürlich eine FNF vollständige Zahl, 11! und 12! eine FNF faktorielle, und jede Fakultät > 12! eine FNF unvollständige Zahl, da nun der letzte Faktor auf jeden Fall 11 · 13 enthält.
nm: Ist n eine FNF vollständige Zahl so ist die Potenz mit einer beliebigen natürlichen Zahl m auch wieder eine FNF vollständige Zahl.
10n: da jede volle Zehnerpotenz durch die Faktoren 2 und 5 (genauer 2n · 5n) darstellbar ist, ist sie FNF vollständig.
Allein durch diese Regeln zusammen mit Satz 1 ist man in der Lage viele kombinatorische Probleme wieder in die FNF einzuordnen, da hier oft eine Multiplikationen von Potenzen und Fakultäten vorliegt. Da ein Binomialkoeffizient eine Division von Fakultäten ist gelten natürlich auch hierfür diese Regeln.
 | Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Finis-Normalform, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation. |
