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

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

ü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

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

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

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.

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

primzahlen mit 10 Mio stellen zu finden?