Ich habe kürzlich festgestellt, dass es sehr viele Algorithmen gibt, die ganz oder teilweise auf der geschickten Verwendung von Zahlen in kreativen Grundlagen basieren. Beispielsweise:
- Binomial-Heaps basieren auf Binärzahlen, und die komplexeren Skeom-Binomial-Heaps basieren auf Skew-Binärzahlen.
- Einige Algorithmen zur Erzeugung lexikographisch geordneter Permutationen basieren auf dem faktoradischen Zahlensystem.
- Versuche können als Bäume betrachtet werden, die jeweils eine Ziffer der Zeichenfolge nach einer geeigneten Basis durchsuchen.
- Huffman-Codierungsbäume sind so konzipiert, dass jede Kante im Baum eine Null oder Eins in einer binären Darstellung codiert.
- Die Fibonacci-Codierung wird bei der Fibonacci-Suche und zum Invertieren bestimmter Arten von Logarithmen verwendet.
Meine Frage ist: Welche anderen Algorithmen gibt es, die ein cleveres Zahlensystem als Schlüsselschritt für ihre Intuition oder ihren Beweis verwenden? . Ich denke darüber nach, einen Vortrag zu diesem Thema zusammenzustellen. Je mehr Beispiele ich heranziehen muss, desto besser.
algorithm
math
data-structures
numbers
number-systems
templatetypedef
quelle
quelle
Antworten:
Chris Okasaki hat ein sehr gutes Kapitel in seinem Buch Rein funktionale Datenstrukturen , in dem es um "Numerische Darstellungen" geht: Nehmen Sie im Wesentlichen eine Darstellung einer Zahl und konvertieren Sie sie in eine Datenstruktur. Um einen Vorgeschmack zu geben, hier die Abschnitte dieses Kapitels:
Einige der besten Tricks, destilliert:
Hier ist auch die Referenzliste für dieses Kapitel:
quelle
etc...
Diese Liste ist ein guter Ausgangspunkt.
quelle
Ich habe neulich Ihre Frage gelesen und war heute mit einem Problem konfrontiert: Wie generiere ich alle Partitionen eines Sets? Die Lösung, die mir einfiel und die ich verwendete (möglicherweise aufgrund des Lesens Ihrer Frage), war folgende:
Für eine Menge mit (n) Elementen, für die ich (p) Partitionen benötige, zählen Sie alle (n) Ziffern in Basis (p) durch.
Jede Nummer entspricht einer Partitionierung. Jede Ziffer entspricht einem Element in der Menge, und der Wert der Ziffer gibt an, in welche Partition das Element eingefügt werden soll.
Es ist nicht erstaunlich, aber es ist ordentlich. Es ist vollständig, verursacht keine Redundanz und verwendet beliebige Basen. Die von Ihnen verwendete Basis hängt vom jeweiligen Partitionierungsproblem ab.
quelle
111222
unterscheidet sich von222111
?Ich bin kürzlich auf einen coolen Algorithmus gestoßen, mit dem Teilmengen in lexikografischer Reihenfolge basierend auf den binären Darstellungen der Zahlen zwischen 0 und 2 n - 1 generiert werden können. Er verwendet die Bits der Zahlen, um zu bestimmen, welche Elemente für die Menge ausgewählt werden sollen, und um sie lokal neu anzuordnen die generierten Mengen, um sie in lexikografische Reihenfolge zu bringen. Wenn Sie neugierig sind, habe ich eine Zuschreibung gepostet hier .
Viele Algorithmen basieren auch auf Skalierung (z. B. eine schwach polynomielle Version des Ford-Fulkerson-Max-Flow-Algorithmus), bei der die binäre Darstellung der Zahlen im Eingabeproblem verwendet wird, um eine grobe Annäherung schrittweise zu einer vollständigen Lösung zu verfeinern.
quelle
Nicht gerade ein cleveres Basissystem, aber eine clevere Verwendung des Basissystems: Van-der-Corput- Sequenzen sind Sequenzen mit geringer Diskrepanz, die durch Umkehren der Basis-n-Darstellung von Zahlen gebildet werden. Sie sind die 2-d zu konstruieren Halton - Sequenzen , welche Art aussehen von wie diese .
quelle
Ich erinnere mich vage an etwas über Doppelbasissysteme, um die Matrixmultiplikation zu beschleunigen.
Double Base System ist ein redundantes System, das zwei Basen für eine Nummer verwendet.
Redundant bedeutet, dass eine Nummer auf viele Arten angegeben werden kann.
Sie können nach dem Artikel "Hybridalgorithmus zur Berechnung des Matrixpolynoms" von Vassil Dimitrov, Todor Cooklev, suchen.
Ich versuche, den besten kurzen Überblick zu geben, den ich kann.
Sie versuchten, ein Matrixpolynom zu berechnen
G(N,A) = I + A + ... + A^{N-1}
.Die Annahme, dass N zusammengesetzt ist
G(N,A) = G(J,A) * G(K, A^J)
, wenn wir J = 2 beantragen, erhalten wir:ebenfalls,
Da es (im Scherz) "offensichtlich" ist, dass einige dieser Gleichungen im ersten System schnell und andere im zweiten besser sind, ist es eine gute Idee, die besten davon abhängig zu wählen
N
. Dies würde jedoch einen schnellen Modulo-Betrieb für 2 und 3 erfordern. Hier ist der Grund, warum die doppelte Basis eingeführt wird. Grundsätzlich können Sie den Modulo-Betrieb für beide schnell ausführen, wodurch Sie ein kombiniertes System erhalten:Schauen Sie sich den Artikel zur besseren Erklärung an, da ich kein Experte auf diesem Gebiet bin.
quelle
RadixSort kann verschiedene Zahlenbasen verwenden. http://en.wikipedia.org/wiki/Radix_sort Ziemlich interessante Implementierung eines BucketSort.
quelle
Hier ist ein guter Beitrag zur Verwendung ternärer Zahlen zur Lösung des Problems der "gefälschten Münze" (bei dem Sie eine einzelne gefälschte Münze in einem Beutel mit regulären Münzen erkennen müssen, wobei Sie so oft wie möglich eine Waage verwenden müssen).
quelle
Hashing-Strings (z. B. im Rabin-Karp- Algorithmus) bewerten den String häufig als Basis-b-Zahl, die aus n Ziffern besteht (wobei n die Länge des Strings ist und b eine ausgewählte Basis ist, die groß genug ist). Zum Beispiel kann die Zeichenfolge "ABCD" wie folgt gehasht werden:
Wenn Sie Zeichen durch ASCII-Werte ersetzen und b auf 256 setzen, wird dies:
In den meisten praktischen Anwendungen wird der resultierende Wert jedoch modulo mit einer angemessenen Größe angenommen, um das Ergebnis ausreichend klein zu halten.
quelle
Die Exponentiation durch Quadrieren basiert auf der binären Darstellung des Exponenten.
quelle
Im
Hackers Delight
(einem Buch, das jeder Programmierer in meinen Augen kennen sollte) gibt es ein vollständiges Kapitel über ungewöhnliche Basen, wie -2 als Basis (ja, rechts negative Basen) oder -1 + i (i als imaginäre Einheit sqrt (-1)) als Base. Auch ich rechne gut, was die beste Basis ist (in Bezug auf das Hardware-Design für alle, die es nicht lesen wollen: Die Lösung der Gleichung ist e, also kann man mit 2 oder 3 gehen, 3 wäre etwas besser (Faktor) 1,056 mal besser als 2) - ist aber technisch praktischer).Andere Dinge, die mir in den Sinn kommen, sind der graue Zähler (wenn Sie in diesem System nur 1-Bit-Änderungen zählen, verwenden Sie diese Eigenschaft häufig im Hardware-Design, um Metastabilitätsprobleme zu reduzieren) oder die Verallgemeinerung der bereits erwähnten Huffmann-Codierung - der arithmetischen Codierung.
quelle
Die Kryptographie verwendet in großem Umfang ganzzahlige Ringe (modulare Arithmetik) und auch endliche Felder, deren Operationen intuitiv auf dem Verhalten von Polynomen mit ganzzahligen Koeffizienten basieren.
quelle
Ich mag dieses Modell wirklich, um Binärzahlen in Gray-Codes umzuwandeln: http://www.matrixlab-examples.com/gray-code.html
quelle
Gute Frage. Die Liste ist in der Tat lang. Die Erzählzeit ist ein einfaches Beispiel für gemischte Basen (Tage | Stunden | Minuten | Sekunden | Uhr / Uhr).
Ich habe ein Meta-Basis-Enumerations-N-Tupel-Framework erstellt, wenn Sie daran interessiert sind, davon zu hören. Es ist ein sehr süßer syntaktischer Zucker für Basisnummerierungssysteme. Es ist noch nicht veröffentlicht. E-Mail meinen Benutzernamen (bei Google Mail).
quelle
Einer meiner Favoriten bei Basis 2 ist die arithmetische Codierung . Es ist ungewöhnlich, weil der Kern des Algorithmus Darstellungen von Zahlen zwischen 0 und 1 in Binärform verwendet.
quelle
Sein kann AKS ist der Fall.
quelle