Speicherbedarf großer Zahlen durch Primfaktorzerlegung senken |
| 07.08.2008, 23:01 | ingo | Auf diesen Beitrag antworten » |
| Speicherbedarf großer Zahlen durch Primfaktorzerlegung senken es ist keine Frage aus dem Studium, mein Mathestudium habe ich nach 15 Semestern abgebrochen. 
Und zwar überlege ich, ob es möglich ist, den Speicherbedarf einer großen Zahl mithilfe von Primzahlzerlegung und Codierung zu verringern. Angenommen, wir haben eine große natürliche Zahl a. Deren Primfaktorzerlegung benötigt ja naturgemäß mindestens so viel Speicher wie a. Nun gibt es weniger Primzahlen < a als natürliche Zahlen < a. Wenn jeder Primfaktor von a durch seine Ordinalzahl in der Folge der Primzahlen dargestellt wird, verringert sich also der Speicherbedarf gegenüber der Zerlegung. Ist es möglich abzuschätzen, ob durch dieses Verfahren der Speicherbedarf gegenüber dem von a verringert werden kann? Vielleicht ein paar Beispiele (Die 1 wird als Primfaktor nicht berücksichtigt): 1.) Sei a = 100. Primfaktorzerlegung ist 2 · 2 · 5 · 5. Die Ordinalzahlen der Primfaktoren sind 1, 1, 3, 3. => 1,1,3,3 benötigt mehr Speicher als 100. => Hat nicht funktioniert. 2.) Sei a = 1997. a ist prim. 1997 ist die dreihundertzweite Primzahl. Es wird also 302 gespeichert. => 302 benötigt weniger Speicher als 1997. 3.) Sei a = 2230476576787. Primfaktorzerlegung ist 23 · 31667 · 3062407. Die Ordinalzahlen der Primfaktoren sind 9, 3407, 220967. => 9,3407,220967 hat ebensoviele Stellen (dezimal, Kommata als Trennzeichen mitgezählt) wie 2230476576787. Kein Gewinn. 4.) Sei a = 223047657676757687. Primfaktorzerlegung ist 53 · 7013 · 600092167583. Die Ordinalzahlen der Primfaktoren sind 16, 902, 786804. => 16,902,786804 benötigt deutlich weniger Speicher als a. Es ist wird deutlich, dass ein Vorteil nur bei großen Primfaktoren zu erwarten ist. Ist es möglich, noch genauere Aussagen über das Verfahren zu machen? Ihr seht, Benennungen und Folgerungen sind nicht sehr genau. Ich hoffe, es ist aber klar geworden, wie ich es meine und ihr verzeiht mir die umgangssprachliche Beschreibung. Alles Gute, bin auf eure Meinungen gespannt. Ingo |
||
| 07.08.2008, 23:21 | AD | Auf diesen Beitrag antworten » |
Interessante Idee, aber wenn du auf diese Weise ein Kompressionsverfahren entwickeln willst, das wirklich alle Zahlen bis zu einer gewissen Obergrenze (z.B. begrenzt wegen der Speicherbit-Anzahl) erfassen soll und jeweils kleinere Komprimate liefern soll, dann musst du zwangsläufig scheitern - das lässt sich sogar beweisen. 
Du hast da nämlich auch einige Dinge beim Zählen des Speicherbedarfs "vergessen": Die Informationen, wieviel Faktoren die Zerlegung hat, wieviel Bits du für jeden Primfaktor brauchst (die reinen Bits der Zahlen aneinandergeklebt liefern diese Info nämlich nicht!), und und und ... da kommt noch einiges zusammen. Was völlig anderes ist, wenn du dich von vornherein auf eine Teilmenge der Zahlen einschränkst: Z.B. nur Primzahlen, oder nur Zahlen mit maximal zwei Primfaktoren usw. - in dem Fall mag einiges drin sein. Aber ohne derartige Einschränkungen - da ist nix zu machen. Ich will jetzt gar nicht mit Informationsentropie anfangen, das sollte auch so klar sein. |
||
| 07.08.2008, 23:35 | ingo | Auf diesen Beitrag antworten » |
| noch ein paar Überlegungen... Nach dem Primzahlsatz nimmt ja der Unterschied zwischen Primzahl und ihrer Ordinalzahl in der Folge immer mehr zu. Kritisch sind also Zahlen, die sich nur aus sehr kleinen Primfaktoren zusammensetzen. Zumal ja für die Trennung der Faktoren zusätzlich Speicherplatz benötigt wird. Gäbe es für solche Fälle eine gute Speicherlösung? Etwa nach dem Prinzip: Wenn die Zahl sehr groß ist, gibt es entweder auch große Primfaktoren, die (vielleicht) durch die Codierung den größeren Speicherbedarf kompensieren, oder es muss genügend kleine Primfaktoren geben, um sie zusammenfassen zu können, etwa 12 · 5 + 4 · 7 + 11 · 13 + ... Oder man teilt die Faktoren in die Klasse derer, deren Ordinalzahl Speichergewinn bringen und alle anderen und speichert die einen in der obigen Form und die anderen unaufgelöst (als Produkt dieser Primfaktoren, bzw. als Rest). Ergibt das Sinn? Und dann noch: Gibt es Klassen von Zahlen oder Regelmäßigkeiten, nach denen die „Qualität“ der Primfaktoren (im Sinne der Aufgabe) einer Zahl erkannt werden kann? Ich hoffe, das hat jetzt nicht zu mehr Verwirrung beigetragen. Und sorry, dass die ganze Speichergeschichte so sehr Richtung Informatik geht.
Alles Gute Ingo |
||
| 07.08.2008, 23:54 | ingo | Auf diesen Beitrag antworten » |
Hey Arthur, das ging ja schnell. Vielen Dank schon mal für die Antwort. Mein zweiter Beitrag ging raus, bevor ich sie gelesen hatte.
Dass die Trennung der Faktoren mit abgespeichert werden muss, war mir schon klar. Auch wenn ich nicht genau weiß, wie das dann auf Bit-Ebene umgesetzt wird. Ich hab versucht, das mit Dezimalzahlen und den Kommata ungefähr zu umreißen. Das mit der Entropie hatte ich mir auch fast gedacht... Aber ich wollte auch nicht so recht daran glauben... 
Ja, der Plan war es, einen Komprimierungsalgorithmus zu entwerfen. Die Überlegung war, ob es nicht möglich wäre, durch die Regelhaftigkeit einer Beschreibung von Zahlen Informationen auszulagern. Etwa so, dass eine große Datei durch eine kleinere, der Datei spezifische, und einer allgemeingültigen Datei, nämlich einer großen Primzahlliste, beschrieben werden kann. So dass die kleinere Datei nur die Rechenvorschriften enthält, die sich auf die Primzahlliste beziehen und aus denen zusammen die Ursprungsdatei errechnet werden kann. Vielleicht entspricht das in etwa der Überlegung, ob der Vektor der Datei mit weniger Informationen auf der Basis der Primzahlen beschrieben werden kann, als auf der Basis der Potenzen der 2. Nun ja, das war jetzt mal ins blaue geschossen, die 2er-Potenzen sind ja gar nicht linear unabhängig. Hm.
Wenn man einfach sehr viel Stroh hätte, müsste es doch möglich sein, wenigstens ein klein wenig Gold daraus zu gewinnen... |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
