Dieser Artikel lautet:
Jede Primzahl kann wie folgt ausgedrückt werden
30k±1,30k±7,30k±11oder30k±13für einigek. Das heißt, wir können acht Bits pro verwenden dreißig Zahlen, um alle zu speichern Primzahlen; eine Million Primzahlen können sein komprimiert auf 33.334 Bytes
"Das bedeutet, dass wir acht Bits pro dreißig Zahlen verwenden können, um alle Primzahlen zu speichern"
Diese "acht Bits pro dreißig Zahlen" wären für k , richtig? Aber jeder k Wert wird nicht notwendigerweise nur ein Bit aufnehmen. Sollte es nicht stattdessen acht k Werte sein?
"eine Million Primzahlen können auf 33.334 Bytes komprimiert werden"
Ich bin mir nicht sicher, wie das stimmt.
Wir müssen zwei Dinge angeben:
WERT von k (kann beliebig groß sein)
STATE aus einem der acht Zustände (-13,-11,-7,-1,1,7,11,13)
Ich folge nicht, wie "33.334 Bytes" bei erreicht wurden, aber ich kann eins sagen: Wenn die Primzahlen immer größer werden, brauchen wir mehr Platz, um den Wert zu speichern von k .
Wie können wir es dann bei "33.334 Bytes" korrigieren?
Sie müssen nicht jeden Wert von k speichern. Wenn Sie die Primzahlen unter 1 Million speichern wollen, verwenden Sie 33.334 Bytes - das erste Byte entspricht k = 0, das zweite auf k = 1 usw. Verwenden Sie dann in jedem Byte 1 Bit, um "prime" oder "composite" anzuzeigen "für 30k + 1, 30k + 7 usw.
Der Artikel ist ein bisschen irreführend: Wir können keine 1 Million Primzahlen speichern, aber wir können alle Primzahlen unter 1 Million speichern.
Der Wert von k ergibt sich aus seiner Position in der Liste. Wir brauchen nur 1 Bit für jede dieser 8 Permutationen (-13, -11 .., 11,13)
Mit anderen Worten, wir verwenden 8 Bits zum Speichern für k = 0, 8 zum Speichern für k = 1, 8 zum Speichern für k = 2 usw. Indem wir diese sequentiell folgen lassen, brauchen wir das nicht Geben Sie den Wert von k für jeweils 8 Bits an - es ist einfach der Wert für die vorherigen 8 Bits + 1.
Da 1.000.000 / 30 = 33.333 1/3, können wir 33.334 dieser 8-Bit-Sequenzen speichern, um darzustellen, welche Werte unter 1 Million Primzahlen sind, da wir alle Werte k abdecken können, ohne dass 30k-13 die Grenze von überschreitet 1 Million.
Es ist eine Bitmaske - ein Bit für jeden der 8 Werte von 30, die prim sein könnten, also 8 Bits pro 30 Zahlen. Um alle Primzahlen bis zu 10 ^ 6 zu tabellieren, benötigen Sie also 8 * 10 ^ 6/30 = 2666667 Bits = 33334 Bytes.
Um zu erklären, warum dies ein guter Weg ist, müssen Sie die offensichtlichen Alternativen betrachten.
Eine naivere Methode wäre es, eine Bitmaske zu verwenden. Sie benötigen eine Million Bits, 125000 Bytes.
Sie können die Werte der Primzahlen auch selbst speichern. Bis zu 1000000 passen die Werte in 20 Bits, und es gibt 78498 Primzahlen, also ergibt dies enttäuschende 1569960 Bits (196245 Bytes).
Ein anderer Weg - wenn auch weniger nützlich für das Nachschlagen von Primzahlen - ist es, die Unterschiede zwischen jeder Primzahl und der nächsten zu speichern. Unter einer Million passt dies in 6 Bits (solange Sie sich erinnern, dass die Primzahlen an diesem Punkt alle ungerade sind, so dass Sie nur gerade Differenzen speichern müssen und somit das niedrigste Bit wegwerfen können), für 470998 Bits == 58874 Bytes . (Sie könnten noch ein bisschen abrasieren, indem Sie zählen, wie viele Mod-30-Slots Sie springen mussten.)
Nun, es gibt nichts besonders Besonderes an 30, außer dass 30 = 2 * 3 * 5, so dass diese Suche dich durch eine Bitmasken-Darstellung des Sievers von Eratosthanes führt, nachdem du angefangen hast. Sie könnten stattdessen 2 * 3 * 5 * 7 = 210 verwenden, und dann müssten Sie + - 1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, für 48 Werte. Wenn du das mit 7 Blöcken zu 30 machst, würdest du 7 * 8 = 56 Bits brauchen, also ist das eine leichte Verbesserung, aber hm ... den Aufwand kaum wert.
Das ist also einer der besseren Tricks, um relativ kleine Primzahlen kompakt zu speichern.
(PS Es ist interessant zu bemerken, dass, wenn Primzahlen zufällig auftraten (aber die gleiche Zahl erschien bis zu 1000000, wie tatsächlich erscheint), die Menge der Information, die in der Primzahl einer Zahl zwischen 1 und 10 ^ 6 gespeichert ist, ~ 0,397 Bits pro ist Also, unter naiven informationstheoretischen Annahmen, würden Sie denken, dass das Beste, was Sie möglicherweise tun könnten, um die erste Million Primzahlen zu speichern, 1000000 * 0,397 Bits oder 49609 Bytes ist.)
Tags und Links algorithm compression storage primes