Basis und Exponent zu Potenz finden

informatics_862de5 · 26. Dezember 2004 um 18:29

Hallo,
Ich möchte große Zahlen(ca. 300 Stellen) platzsparender darstellen
bzw. abspeichern. Weshalb ich diese nach Möglichkeit in der Form
basis^exponent oder basis^exponent + rest(bis zur darzustellenden
Zahl) abspeichern möchte. Jetzt wäre meine Frage an euch, wie ich am
geschicktesten aus einer Zahl n als Eingabe,die basis und den
exponenten berechne? Würde mich über Antworten und Tipps freuen.Ich
würde mich auch über andere Vorschläge zum platzsparendem abspeichen
von großen Zahlen freuen.Wünsche allen ein frohes Fest.

Viele Grüße

Informatics

krizzy_686081 · 26. Dezember 2004 um 18:36

Hi!
Seh ich das jetzt richtig, dass du sie schlichtweg im Grunde über die Primfaktorenzerlegung darstellen willst?
Bei 300 Stellen macht es wohl nicht mehr wirklich Spaß das noch im Kopf zu machen (zur Not gehts auch…), also schau doch mal, ob du vielleicht irgendwo MAPLE oder ähnliches findest, damit geht das recht fix… (obwohl ich mir bei 300 Stellen auch ned ganz sicher bin ob der das so ohne weiteres macht…)

Gruß
Christina

informatics_862de5 · 26. Dezember 2004 um 19:19

Hallo,
Danke für die Antwort.Na ja,es muss nicht umbedingt
Primfaktorzerlegung sein. Es geht darum… ich habe eine große Zahl
nehmen wir mal 184528125 als Beispiel. Ich kann die Zahl ausschreiben
dann hat sie 9 Stellen ich könnte sie aber auch mit 45^5
darstellen.Dies wird nicht mit jeder Zahl so funktionieren aber eine
Annährung würde mir auch schon reichen…z.B für 184528135 = 45^5 +
10. Ist Primfaktorzerlegung wirklich dafür geeignet?

Viele Grüße

Informatics

krizzy_686081 · 26. Dezember 2004 um 19:36

Hi!
Meiner Meinung nach ist nichts besser dafür geeignet als Primfaktorzerlegung (les grad mein neuestes Buch: „Die Musik der Primzahlen“ und bin ehrlichgesagt mal wieder total drauf, wenn mans so sagen will ).
Die Primfaktorzerlegung ist eindeutig (bis auf Einheiten), ich finde das spricht schonmal für sie. Da sich ja (wie du bereits erwähnt hast) nicht jede Zahl als „einelementige Primfaktorzerlegung“ (mich stört grad total die Schlampigkeit meiner Ausdrucksweise, aber ich weiß nicht, wie ich es sonst anders ausdrücken soll) darstellen lässt, ist die Primfaktorenzerlegung auch in der Hinsicht das Praktischste, weil sie wahrscheinlich noch einfacher zu finden ist als die nächste Zahl zu finden, die eben so eine „einelementige“ (au weia…) Darstellung hat…
Verstehst du, worauf ich hinaus will? :o)

Gruß
Christina

Johannes_N_le · 26. Dezember 2004 um 20:22

Hallo Christina

Mit der Primfaktorzerlegung könnte es aber Probleme geben, wenn die Zahl eine sehr lange Zerlegung hat (z.B. 15015 = 3*5*7*11*13) Das Beispiel ist jetzt natürlich konstruiert, aber du verstehst, was ich meine. In einem solchen Fall würde die Primfaktorzerlegung mehr Platz wegnehemen als die ursprüngliche Zahl. Und im Moment sehe ich keine gute Möglichkeit, aus der Primfaktorzerlegung der Zahl dann eine sinnvolle Näherung zu konstruieren.
Ich versuch mal, das Problem mathematisch exakt zu formulieren:
Das Problem wäre also, zu einer natürlichen Zahl n die Potenzdarstellung a^b, in der a und b natürliche Zahlen sind, zu finden, für die die Differenz |n - a^b| minimal wird. Der Trivialfall b=1 sei dabei ausgeschlossen.
Meiner Meinung nach kann das Problem kaum schneller als durch Ausprobieren aller Möglichkeiten gelöst werden. Da der Aufwand für das Lösen des Problems allerdings nur proportional zu n ist, wäre das wohl akzeptabel. Für ein n in der Größenordnung von 1.000.000.000 müsste das ein handelsüblicher PC noch recht schnell schaffen, glaube ich.

Gruß
Johannes Nüßle

informatics_862de5 · 26. Dezember 2004 um 20:16

Hallo,
Gut dann eben Primfaktorzerlegung…dann muss ich aber fragen(du
scheinst dich ja gut in der Thematik auszukennen),wie ich am
schnellsten eine Zahl in ihre Primfaktoren zerlege, die 300 Stellen
hat?Da gibt es Restsiebe oder ähnliches nicht?Sind die mittlerweile
gut genug,um es in einer angemessnen Zeit zutun?Könntest du
vielleicht kurz beschreiben, wie du dir den Ablauf vorstellst der
nötig ist um eine Zahl n in basis^exponent + rest(bis n) zu zerlegen
mit Primfaktorzerlegung? Wäre wirklich super nett

Viele Grüße

Informatics

krizzy_686081 · 26. Dezember 2004 um 20:37

Hallo nochmal!
Wie gesagt: Ich würde es mit MAPLE oder einem ähnlichem Programm machen bei solchen Zahlen. Ansonsten gibt es eben schon das „Sieb“: Erst schaun, ob es durch 2 teilbar ist, dann nochmal und nochmal bis die Zahl nicht mehr durch 2 teilbar ist. Dann mit 3 weitermachen, dann mit 7 etc. etc. Ist aber schon recht aufwendig. Hab es grade mal mit Maple ausprobiert. Weiß nicht, wie viele Stellen ich eingegeben hab, einfach mal wild drauflos getippt. Da kam dann eine Zerlegung, bei der ich mir nich vorstellen kann, dass es wirklich die gewünschte Zerlegung war, weil eine Primzahl dabei war, die bestimmt 30 Stellen umfasst hat (kann mir nicht vorstellen, dass es wirklich eine Primzahl war. Oder ich hab eben verdammt gut getippt ). Bei drei Zeilen voller Ziffern hab ich nach 10 Sekunden abgebrochen, da kämpft das Programm schon ein bisschen.
Hab grad überlegt, ob man das nicht auch evtl. modular angehen könnte. Aber da muss ich nochmal drüber nachdenken. Da hast du mich mit dem Rest drauf gebracht… Da denk ich nochmal drüber nach.

Hast schon gemerkt: Mit dem Thema hast du mich an nem wunden Punkt getroffen. Da würd ich am liebsten gar ned mehr aufhören… :o)

Viele grüße zurück!
Christina

krizzy_686081 · 26. Dezember 2004 um 20:40

Hi!
Naja, die Wahrscheinlichkeit, dass die Zahl „ohne Potenzen“ in Primfaktoren zerlegt wird ist aber schon relativ gering. Klar kann sie länger sein, aber ich denke, grade in der Informatik ist es so eher übersichtlich als eine 300stellige Zahl…
Die Problemstellung, die d dort geschildert hast find ich so auch interessant. Wie in meinem anderen Eintrag schon: Vielleicht über Modul-Strukturen?
Mist, da habt ihr mir jetzt wieder was gesagt. Werd heut Nacht scher wieder nicht schlafen…

Gruß
Christina

Karl_H_Sch_nfeld · 26. Dezember 2004 um 21:25

Hallo,
wenn Du schon mit einer Annäherung zufrieden bist : wie genau soll’s denn sein (prozentual, Anzahl der Stellen) ?
Und wär’s indiskret, nach der Praxisanwendung zu fragen ?
Hatte vor vielen Jahren auf einem der ersten PCs das Problem, umfangreichere Preislisten angesichts sehr begrenzter Speicherkapazitäten zu speichern. Behelf war, in die (automatisch) 12 Stellen jeder Zahl, die auf das Mini-Tape geschrieben wurden, zusätzliche Infos (z.B. prozentuale Preisabweichungen in den letzten 3 Jahren) hinzubringen. Das war ohne weiteres möglich, da die Preise aus maximal drei Stellen bestanden. Mit der Zehnerpotenz dazu als vierter Stelle blieben mit den 3x2 Stellen für die prozentuale Veränderung sogar noch zwei Stellen für Zusatzinfos übrig.
Entscheidend ist , wie genau die Ergebnisse aus den Abbildungsverfahren wirklich sein müssen.
Gruß
Karl

Omar_Abo_Namous · 26. Dezember 2004 um 21:38

Hallo,

ich fand den Ansatz sehr interessant. Es wäre dasselbe wie die Exponentialschreibweise (oder Gleitkommazahlen), wobei aber die Basis auch variabel ist. Damit kann man bei grossen Zahl bestimmt Platz sparen.

Die Frage wäre (wie bei der Exponentialschreibweise), ob Fehler zulässig sind und in welchem Rahmen sie sich bewegen sollen. Denn soviel dazu: solange man ganzzahlige Basen und Exponenten benutzt, beläuft sich der Fehler auf 10%. Das ist bei einer 300-stelligen Ausgangszahl immerhin eine 299-stellige Zahl. Besimmt kann man mehr erreichen, wenn man kleinere Abtastschritte wählt und auch nachkommabehaftete Exponenten wählt. Damit alle meinen Ansatz haben, hier der matlab-Quelltext:

clear all
x=[2:1001];
z=210354034\*10^100;
warning off;
for i=1:1000
 y(i)=log(z)/log(x(i));
end
plot(y)
hold on;
for i=1:1000
 wert(i)=abs(z-(i-1)^round(y(i)))/z;
end
plot(wert,'g:');
hold off;
min(wert)

Zur Ausgabe: Es wird in Blau die Ergebnis-Funktion für die Zahl z (oben) ausgegeben. x-Achse ist die Basis, y-Achse ist der Exponent.
In Grün wird der relative Fehler ausgegeben.

Gruss, Omar Abo-Namous

Omar_Abo_Namous · 26. Dezember 2004 um 22:07

oops, kleiner Fehler in der Berechnung des relativen Fehlers:

wert(i)=abs(z-(i+1)^round(y(i)))/z;

muss es heissen…

Gruss, Omar Abo-Namous

Johannes_N_le · 26. Dezember 2004 um 22:37

Entschuldigung, aber der Fehler von maximal 10%, gibt es da einen Beweis, oder ist das ein Erfahrungswert?
Vieleicht steh ich ja auf dem Schlauch, aber mir erschließt sich das nicht so einfach.

informatics_862de5 · 26. Dezember 2004 um 23:01

Hallo,
eine Ungenauigkeit von 10% ist nicht sehr gut Wenn man statt 300
Stellen, eine Zahl mit 299 Stellen speichern muss bedeutet dies
höchstens eine Ersparnis von 1 bis 2 Byte.Könnte man es mit
Kommazahlen vielleicht genauer machen? Also z.B 2.4^3.4 + Rest ?

Viele Grüße

informatics

Omar_Abo_Namous · 26. Dezember 2004 um 22:49

Hallo,

ich würde es noch nicht einmal Erfahrungswert nennen. Ich hatte mit dem gegebenen script getestet und kam auf Werte unterhalb von 10%. Natürlich kann man diesen Wert noch weiter herunterschrauben, indem man grössere Bereiche (für Basis und Exponent) ausprobiert.

Nun bin ich soweit, dass ich einen maximalen relativen Fehler von 0.00001 erreichen kann, allein dadurch, dass ich eine Nachkommastelle sowohl bei der Basis als auch beim Exponenten nehme.

Wer matlab hat, kann folgendes ausprobieren (sollte auch so in etwa in scilab funktionieren…):

clear all
close all
%z=4.5484\*10^30;
z=input('Geben Sie die gesuchte Zahl ein: ');
ende=0;
tol=0.00001;
i=1;
while(ende==0)
 i=i+0.1;
 index=round(i\*10);
 y(index)=log(z)/log(i);
 ry(index)=round(y(index)\*10)/10;
 wert(index)=abs((z-i^ry(index)))/z;
 rest(index)=z-i^ry(index);
 if wert(index)

Gruss, Omar Abo-Namous


> <small>[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]</small>

Omar_Abo_Namous · 26. Dezember 2004 um 23:28

Hallo,

wie ist es denn mit dem anderen script? Dort kannst du direkt angeben, welche Toleranzgrenze für dich noch akzeptabel ist. (Werte um 0.00000001 sind noch angemessen) und auch wieviele Nachkommastellen du beim Exponenten oder bei der Basis maximal haben willst.
Problematisch ist meines Wissens, dass Computer höchstens mit Gleitkommazahlen rechnen können. Und die an sich haben einen Fehler ‚integriert‘. Deshalb kann man nur sehr schwer den Algorithmus mit einer 300-stelligen Zahl ausprobieren…
Ausserdem musst du schon sagen, ob du mit einem Restfehler arbeiten willst (ok, 10% war sehr viel, aber wie wärs mit 0.01 promille?), oder ob du den Wert genau angeben willst. Denn der genaue Wert ist meist sehr schwierig anzugeben (Da meist Nachkommastellen hinzukommen, kann die errechnete Zahl samt Rest länger sein als die Ursprungszahl).

Gruss, Omar Abo-Namous

informatics_862de5 · 27. Dezember 2004 um 01:12

Hallo,
Ich kann das Script leider nicht ausprobieren.Habe Mathlab nicht auf
dem Computer. Das Problem mit den Gleitkommazahlen wird kein Problem
sein…es gibt Programmbibliotheken, die mit beliebiger Genauigkeit
rechnen Selbst Kommazahlen mit 300 Stellen werden keine Fehler
beinhalten. Habe ich es richtig verstanden,dass die Fehlerrate der
Rest ist, bis zu der Zahl, die wir damit „komprimiert“ haben? Ich bin
mir nicht sicher, wie Fehlertolerant ich sein kann… Ein Beispiel ich
habe eine Zahl mit 507 Stellen, diese benötigt 211 Byte Speicher.
Wenn ich diese Zahl in 180 Byte oder 190 Byte speichern könnte wäre
ich „schon“ zufrieden

Viele Grüße

informatics

informatics_862de5 · 27. Dezember 2004 um 01:34

Hallo,
Also mit Primzahlenfaktorisierung wird es wohl nicht funktionieren

lange lange Zeit. Was meinst du mit modular angehen?

Viele Grüße

Informatics

informatics_862de5 · 27. Dezember 2004 um 01:39

Hallo,
Nun ja,wie bereits oben geschrieben sind die Zahlen extrem groß ca.
300 bis 500 Stellen. Wenn man sich auf ein paar Milliarden der Zahl
nähren könnte und nur diese Abweichung abspeichern müsste und man
somit z.B den Speicherbedarf von 210 auf 190 Byte senken könnte,
würde mir das genügen.

Viele Grüße

informatics

krizzy_686081 · 27. Dezember 2004 um 01:49

Naja, es geht. So lange dauert es vielleicht gar nicht. Wenn man das Verfahren betrachtet…
Mir graust es übrigens, wenn ich die Diskussion weiter oben durchlese. Diese Fehlerrechnung ist mir ein Greuel. Numerik ist zwar mein zweies Fach, aber bei sowas, wo es nun auch präziser ginge theoretisch find ichs fuchtbar!

informatics_862de5 · 27. Dezember 2004 um 21:16

Hallo,
Na ja, ich finde die Lösung von oben garnicht so schlecht…aber ich
verstehe sie noch nicht so wirklich Kann sie auch nicht
ausprobieren,weil ich kein MathLab habe.Glaubst du man könnte damit
wenigstens kleinere Zahlen, so im Bereich von 1000000000000 in basis
und exponent + rest zerlegen um etwas Platz zu sparen? Man könnte ja
z.B eine 500 stellige Zahl aufspalten und z.B erst die ersten 12
Stellen mit dem Verfahren komprimieren,dann die nächsten 12 Stellen
komprimieren usw. und es dann beim „decoden“ wieder zusammen setzen
damit man wieder auf die 500 stellige Zahl kommt. Meinst du es würde
funktionieren?

Viele Grüße

Informatics