Zahl mit 10 mio-ziffern in c\c++

Seite 1 von 8 - Forum: Coding Stuff auf overclockers.at

URL: https://www.overclockers.at/coding-stuff/zahl_mit_10_mio-ziffern_in_cc_103331/page_1 - zur Vollversion wechseln!

muss eine zahl mit 10 mio ziffern in c\c++ darstellen
klar so einen datentyp gibt es nicht darauf hin habe ich mit einem freund zum diskutieren angefangen und er hat mal folgendes lösung erarbeitet könntet ihr des bitte mal überprüfen?

in einem byte(sind 8bits) kann man eine zahl mit einem wert von 256 speichern
2 bytes - 65536
3 bytes - 16777216
4 bytes - 4294967296
5 bytes - 1099511627776
.......................
128 bytes(immerhin schon 1024bits) kann eine zahl mit dem wertebereich bis 2 hoch 1024 gespeichert werden. das auszurechnen sprengt beinen taschenrechner so wie meinen kopf aber ihr könnt mir glauben
die zahl ist verdammt groß und hat glaub ich 320 stellen...
bei 65536byte könnten wir ein zahl mit 20480 zeichen darstellen...(als string zumindest *g*(freak))


ja genau auf die 33554432bytes den dann können wir eine zahl mit 10485760 zeichen darstellen(jaja als string nur)

damit haben wir eine 268435456bit zahl entdeckt mit der wir sogar mit 485760 zeichen über unser ziel hinausgesprungen sind!

um diese zahl zu speichern brauchen wir nur noch einen speicher von schlappen

33554432bytes(weil ein zeichen=ein byte) oder
32768kb oder
genau 32mb

wie ihr wahrscheinlich schon mitbekommen habt wird das ganze als string dargestellt

10 mio dezimalziffern = 10^10000001 - 1 als größten wert

der logaritmus dualis davon wird durch acht dividiert und aufgerundet, schon hast du deinen speicherbedarf.

edit: wenn ich mich nicht grob vertan hab sollts so ausschaun:

ln(10^10000001 - 1)/ln(2) = ca. = ln(10^10000001)/ln(2) = 10000001 * ln(10)/ln(2) = 33219284 bit = ca. 4MB

edit2: wenn du für jede ziffer ein zeichen (sprich: ein byte) nimmst, so wirst du bei 10000000 ziffern wohl 10000000 bytes brauchen )

übrigens,
2^1024 = 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216

sind 309 stellen

daher kannst du mit 65536byte 158208 stellen darstellen
somit solltest du nach meiner rechnung mit 32mb bereits auf 81002496 =~ 81mio stellen kommen

dh für 10 mio ziffern brauchst eh nur lächerliche 4 mb (oder 3 disketten )

edith: thx manalishi für die ownung, aber bestätigung meines ergebnisses. sein fehler im ansatz war bei der einfachen schlussrechnung

edith2: nö, mathematica ownung

[x] vote "Frys_Assassin" for Derive-0wner ;P

scnr

ja ok so weit die theorie nur soll ich ja damit rechen können und wie wende ich auf einem string den log an?

Zitat von fresserettich

ja ok so weit die theorie nur soll ich ja damit rechen können und wie wende ich auf einem string den log an?

auf bcd zahlen kannst du afaik keine echten mathematischen funktionen anwenden... nimm z.b. 0 + 1 ... du wirst 0 und 1 als ascii-code bytes im speicher haben, da kannst du nicht einfach die zwei chars addieren. da irgendwie fast alles auf verketteten additionen basiert, wirds logaritmieren nicht spielen imho

edit: wenn du meine rechnung nachvollziehst kommst du auf 3,96MB

eben genau das ist der punkt
ich muss das ganze als string darstellen, die grundrechnungsarten als für einen string sind schnell geschrieben
deine rechnung stimmt keine frage aber nur wenn ich des ganze als int/float habe und den log anwenden kann
wieviel wird der string brauchen? oder reden wir jetzt völlig aneinander vorbei?

schau, du musst so gut wie alles neu schreiben. wenn du z.b. eine klasse hast, die die zahl als bcd-zahl implementiert, dann braucht eine instanz davon nur für die zahl 10 millionen bytes.

dann werden die algoritmen implementiert.

so geht z.b. eine bcd addition (mit weniger stellen, eh klar)

25642
+
84647

das lsB (least significant byte) des ersten summanden muss mit dem des zweiten addiert werden. wenn dabei etwas größer 9 herauskommt, so muss eins als übertrag für die nächste stelle mitgegeben werden. in der digitaltechnik wird das als carry bezeichnet.
unter berücksichtigung des carrys wird dann das zweitletzte byte addiert usw.

ich hab sowas btw. in java schon fixfertig als bigint gesehen

ja ist mir schon klar
aber wieviel speicherbedarf wird jetzt der string verschlingen?

GNU Multiprecision Library kann das auch (gmp).

Speicher wird halt so viel verbraucht wie intuitiv eh klar ist (nach manalishis Formel) für jeden Operanden + Ergebnis.

die einzige anwendung die ich gesehen hab, die tatsächlich 10 mio stellen braucht, war die suche nach primzahlen...

die derzeit größte bekannte primzahl (M40) hat 6.320.430 stellen (base=10), für die erste primzahl mit 10 mio stellen gibts einen preis zu gewinnen (USD 100.000). http://www.eff.org/awards/coop.html

übrigens: um die primalität der M40 zu prüfen, brauch ein P4 2ghz ca 20 tage.

Und da werden keine Kindergartenalgorithmen verwendet, sonst wären sie nämlich noch lang nicht so weit.

hehe da atrox hat mich durschaut den mods auf oc.at kann man auch nix verheimlichen
@Ringding habe gerade einen link offen bezüglich der library die du meinst mal schauen vielleicht hilft uns das weiter
ps fyi die letzte primzahl also mit 6 mio stellen hat ein chemie-student geknackt
um was geht es?
also:
ich hatte eine idee und habe einen freund um rat gefragt der sofort interesse zeigte, daraufhin hat sich ein weiter freund hinzugesellt
also wir 3 wollen einfach ein kleines projekt machen und spielen uns halt gern damit und haben halt eine kranke idee

primzahlen mit 10 Mio stellen zu finden?

overclockers.at v4.thecommunity
© all rights reserved by overclockers.at 2000-2025