Algorithmen basierend auf Zahlenbasissystemen? [geschlossen]

87

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.

templatetypedef
quelle
5
Ich mag die Frage auch, aber wie wählt man die "richtige" Antwort? Sollte dies ein Community-Wiki sein?
Vlad
14
Dies sollte Community-Wiki sein
BlueRaja - Danny Pflughoeft
18
@close voter: Wenn eine Frage zu Algorithmen bei SO nicht zum Thema gehört, weiß ich nicht, was hier zum Thema gehört. Idiotische Neulinge Fragen zu CSS? "Kann ich Regex Plzz Haz"? "PLZ E-Mail an den Codez 4 mi Hoemwok"?
MAK
2
Per Anhalter durch die Galaxis: Was ist die Antwort auf das Leben, das Universum und alles? Antwort von Deep Thought: 42. Die Erde als Maschine, um die Frage zu finden: Was ist 9 x 6? und deshalb ist alles so verdammt. Auf einem T-Shirt gesehen: 9 (Basis 13) x 6 (Basis 13) = 42 (Basis 13). QED.
Chris Walton
"Welche anderen Algorithmen gibt es, die ein cleveres Zahlensystem als Schlüsselschritt für ihre Intuition oder ihren Beweis verwenden?" Der Stapelüberlauf ist keine Empfehlungs-Engine , keine Liste aller Dinge oder eine Link-Farm . Algorithmen zur Lösung praktischer Programmierfragen, absolut. Clearinghäuser für clevere Algorithmen, nein. Vielleicht möchten Sie nach dem Meta der Mathematik fragen , ob sie dies möchten.

Antworten:

39

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:

  1. Positionsnummernsysteme
  2. Binärzahlen (Binäre Direktzugriffslisten, Nulllose Darstellungen, Faule Darstellungen, Segmentierte Darstellungen)
  3. Skew Binary Numbers (Skew Binary Random Access-Listen, Skew Binomial Heaps)
  4. Trinary und Quaternary Numbers

Einige der besten Tricks, destilliert:

  • Unterscheiden Sie zwischen dichten und spärlichen Darstellungen von Zahlen (normalerweise sehen Sie dies in Matrizen oder Grafiken, aber es gilt auch für Zahlen!)
  • Redundante Zahlensysteme (Systeme, die mehr als eine Darstellung einer Zahl haben) sind nützlich.
  • Wenn Sie die erste Ziffer so anordnen, dass sie nicht Null ist, oder eine nulllose Darstellung verwenden, kann das Abrufen des Kopfes der Datenstruktur effizient sein.
  • Vermeiden Sie kaskadierende Ausleihen (vom Ende der Liste) und Übertragungen (von der Aufnahme in die Liste) durch Segmentierung der Datenstruktur

Hier ist auch die Referenzliste für dieses Kapitel:

  • Guibas, McCreight, Plass und Roberts: Eine neue Darstellung für lineare Listen.
  • Myers: Ein anwendbarer Stapel mit wahlfreiem Zugriff
  • Carlsson, Munro, Poblete: Eine implizite Binomialwarteschlange mit konstanter Einfügezeit.
  • Kaplan, Tarjan: Rein funktionale Listen mit Verkettung durch rekursive Verlangsamung.
Edward Z. Yang
quelle
2
+1 Ich habe eine Kopie von Okasakis Buch ... Ich habe diese Kapitel geliebt und sie sind teilweise der Grund, warum ich diese Frage überhaupt gestellt habe (Binomialhaufen mit Bootstrap-Skew sind wirklich cool!). Ich habe sie jedoch nicht vollständig durchgelesen vielleicht sollte ich. Ich werde auch diese Referenzen überprüfen; Sie sehen großartig aus.
Templatetypedef
Die vollständige Arbeit von Okasaky ist online verfügbar: cs.cmu.edu/~rwh/theses/okasaki.pdf
Gigi
20

"Ternäre Zahlen können verwendet werden, um selbstähnliche Strukturen wie ein Sierpinski-Dreieck oder ein Cantor-Set bequem zu vermitteln." Quelle

"Bei der Darstellung von 2D-Hilbert-Kurven werden quaternäre Zahlen verwendet." Quelle

"Das quater-imaginäre Zahlensystem wurde erstmals 1955 von Donald Knuth vorgeschlagen, als er sich einer High-School-Suche nach wissenschaftlichen Talenten unterwarf. Es ist ein nicht standardmäßiges Positionszahlensystem, das die imaginäre Zahl 2i als Basis verwendet. Es ist in der Lage um jede komplexe Zahl nur mit den Ziffern 0, 1, 2 und 3 darzustellen. " Quelle

"Römische Ziffern sind ein biquinäres System." Quelle

"Senary kann bei der Untersuchung von Primzahlen als nützlich angesehen werden, da alle Primzahlen, ausgedrückt in Basis 6, außer 2 und 3, 1 oder 5 als letzte Ziffer haben." Quelle

"Sexagesimal (Basis 60) ist ein Zahlensystem mit sechzig als Basis. Es stammt aus den alten Sumerern im 3. Jahrtausend v. Chr., Wurde an die alten Babylonier weitergegeben und wird immer noch - in modifizierter Form - zum Messen verwendet Zeit, Winkel und die geografischen Koordinaten, die Winkel sind. " Quelle

etc...

Diese Liste ist ein guter Ausgangspunkt.

Benjamin
quelle
6
Keiner von diesen hat mit Algorithmen zu
tun
11
Sicher sind sie. Erstellen eines Sierpinski-Dreiecks-Dreiecks im Ternär oder Berechnen der geografischen Koordinaten im Sexagesimalbereich. Wie wäre es mit einem Algorithmus zur Umwandlung römischer Zahlen in Dezimalzahlen? Wie wäre es mit Algorithmen zur Suche nach Primzahlen, die auf dem Senary-System basieren?
Benjamin
9

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.

Ben Horner
quelle
3
Ich denke, das ist komplett von Templatetypedefs Post gestohlen, es muss in meinem Unterbewusstsein stecken geblieben sein. Ich habe es nur verlassen, weil es um mehr Basen als nur Binär geht.
Ben Horner
2
Dies generiert alle Partitionen mit höchstens p Partitionen und weist Redundanzen auf. Wie 111222unterscheidet sich von 222111?
Null Set
7

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.

templatetypedef
quelle
2
Dies ist der einfachste Weg, um Teilmengen zu generieren :)
st0le
Das ist die einfachste Art, in kombinatorischen Konzepten zu zählen.
Saeed Amiri
@ st0le- Ich denke, dass dies etwas kniffliger ist als die Standardversion, da hier die Sätze in lexikografischer Reihenfolge aufgelistet werden und nicht die normale Reihenfolge, die Sie durch die Eins-zu-Eins-Zuordnung zwischen Bits und Satzeinschluss erhalten.
Templatetypedef
6

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 .

mhum
quelle
6

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.

 n = Sum(i=1 --> l){ c_i * 2^{a_i} * 3 ^ {b_i}, where c in {-1,1}

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:

         / (I + A) * G(K, A^2)        , if N = 2K
G(N,A) = |
         \ I + (A + A^2) * G(K, A^2)  , if N = 2K + 1

ebenfalls,

         / (I + A + A^2) * G(K, A^3)           , if N = 3K
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3)     , if N = 3K + 1
         \ I + A * (A + A^2 + A^3) * G(K, A^3) , if N = 3K + 2

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:

         / (I + A + A^2) * G(K, A^3)       , if N = 0 or 3 mod 6
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3) , if N = 1 or 4 mod 6
         | (I + A) * G(3K + 1, A^2)        , if N = 2 mod 6
         \ I + (A + A^2) * G(3K + 2, A^2)  , if N = 5 mod 6

Schauen Sie sich den Artikel zur besseren Erklärung an, da ich kein Experte auf diesem Gebiet bin.

Egon
quelle
5

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).

Martin DeMello
quelle
Dies war ein großartiger Beitrag, und ich habe ihn schließlich in einem Vortrag mit dem Titel "Spaß mit Zahlensystemen" verwendet. Vielen Dank für die Veröffentlichung!
Templatetypedef
Willkommen und froh, dass Sie es nutzen konnten!
Martin DeMello
5

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:

'A'*b^3+'B'*b^2+'C'*b^1+'D'*b^0

Wenn Sie Zeichen durch ASCII-Werte ersetzen und b auf 256 setzen, wird dies:

65*256^3+66*256^2+67*256^1+68*256^0

In den meisten praktischen Anwendungen wird der resultierende Wert jedoch modulo mit einer angemessenen Größe angenommen, um das Ergebnis ausreichend klein zu halten.

MAK
quelle
4

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.

flolo
quelle
3

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.

Nullmenge
quelle
1

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).

ausreichend
quelle
1
Und jedes Kalendersystem - Maya, Mond, Babylonisch ... zusammen mit der englischen Währung vor 1971 (LSD). Wie Sie sagen, geht die Liste weiter.
Chris Walton
1

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.

Michael Anderson
quelle
0

Sein kann AKS ist der Fall.

Saeed Amiri
quelle