Große integers

[the_undertaker]

Hallo,

ich lerne seit ein paar Wochen C++ und möchte ein Programm schreiben, mit dem ich mit Integerzahlen bis 11^1000 rechnen kann. Da unsigned int ja nur bis 4 Millionen nochwas geht reicht das nicht ganz(die Zahl hat 1042 Stellen )
Wie kann man solche Zahlen erzeugen und mit ihnen rechnen?

Vielen Dank für Antworten im Voraus, the_undertaker

 

[Turri]

Hallo,

Versuch anstatt int mal _int64

MfG Turri

 

[Thomas Darimont]

Hallo,

ich denke da wirst du wohl auf Thirdparty Bibliotheken zurückgreifen müssen:
http://www.google.de/search?hl=de&q=c+++big+integer&btnG=Google-Suche&meta=

Gruß Tom

 

[Online-Skater]

Sowas geht doch garnicht mit einem herkömmlichen Rechner ? 1042 Stellen ?

 

[Turri]

Frag mich eh was er ausrechnen will ;-)

 

[the_undertaker]

Hallo,

Danke erstmal für die vielen Antworten!

@Turri: __int64 reicht lange nicht, ich habs ausprobiert. Ich will für 2<=m<=11 und 1<=n<=1000 die Paare m und n herausfinden, für die m^n+n^m eine Primzahl ist.

@Online-Skater: Das passt schon auf einen normalen Rechner, es sind ca. 1KB

@Tom: Ich probiers mal aus und melde mich dann irgendwann mal.

mfG, the_undertaker

 

[kle-ben]

Hi,
also ich glaube du bist dir den Größenordnugen
mit denen du da rechnen willst nicht ganz bewust.

Du hast da im Worstcase 11^1000 + 1000 ^ 11
das ist verdammt viel
Das ist mehr als ein Googol

Und um zu berechnen ob das eine Primzahl ist brauchst
du alle Primzahlen bis Sqrt( 11^1000 + 1000 ^ 11 ).

Egal was du für ein Rechner hast mit dem Zahlenbereich
wist du das nie errechnen.

Für was brauchst du denn sone große Zahl überhaupt

Gruß Benny

 

[Matthias Reitinger]

Und um zu berechnen ob das eine Primzahl ist brauchst
du alle Primzahlen bis Sqrt( 11^1000 + 1000 ^ 11 ).

Zumindest beim naiven Algorithmus. Bei Zahlen dieser Größenordnung empfiehlt sich allerdings ein auf ECPP basierender Ansatz.

Egal was du für ein Rechner hast mit dem Zahlenbereich
wist du das nie errechnen.

Die größte Zahl dieser Form, deren Primalität rechnergestützt bestätigt wurde, ist 4405^2638 + 2638^4405. Also muss es wohl doch irgendwie machbar sein, nicht?

<edit>

@Online-Skater: Das passt schon auf einen normalen Rechner, es sind ca. 1KB

Wenn man die Zahl nicht Stelle für Stelle speichert, sondern als Integer, kommt man sogar nur auf 433 Bytes. Als BCD wären es 521 Bytes.
</edit>


Grüße,
Matthias

 

[the_undertaker]

Hi,
also ich glaube du bist dir den Größenordnugen
mit denen du da rechnen willst nicht ganz bewust.

Du hast da im Worstcase 11^1000 + 1000 ^ 11
das ist verdammt viel
Das ist mehr als ein Googol

Ich bin mir diesen großen Zahlen schon bewusst(ich hab' ja schon geschrieben, dass meine Zahlen bis zu 1042 Stellen haben )

Gruß, the_undertaker

 

[Online-Skater]

Hallo ich habe mich mit meiner Aussage eigentlich auf den Datentyp bezogen den er dafür sucht
Deswegen muss man wie Matthias schon gesagt hat, andere Methoden benutzen um soetwas zu realisieren, eben wegen der Speicherstruktur.

@Gogol schon alleine diese Zahl übersteigt schätzungsweise die Elementarteilchen des Universums