9hoch9hoch9 - hohe Zahlen

[stoxx]

Zitat:

Nach 32 Minuten hatte ich immerhin schon 9^280.000 berechnet. Das Ergebnis ist im Anhang.

und jetzt bitte die Zahl noch aussprechen !! *g*

[sakura]

Update, da war noch ein Speicherleck nach der letzten Optimierung :oops: (Code ist oben neu enthalten)

...:cat:...

[Matze]

Stimmt deine Berechnung dann auch nicht? ;)

[sakura]

Zitat:

Zitat von Matze

Stimmt deine Berechnung dann auch nicht? ;)

Doch, nur der Speicherverbrauch war innerhalb der ersten 10 Sekunden höher als wirklich nötig 400 MB :shock:

...:cat:...

[Stanlay Hanks]

Mal ne Frage: Diese Zahl ist doch doppelt so lang wie 25 Seiten :gruebel: Also hast du eigentlich schon die doppelte Arbeit für deinen Lehrer gemacht :stupid: Das gibt bestimmt ne gute Note. :D

[dizzy]

Ich würds dem Lehrer nachher in Schriftgröße 24-36 oder so ausdrucken, und per Post zuschicken, mit dem netten kleinen Hinweis auf dem Brief: "Porto zahlt empfänger" :mrgreen:

[sakura]

Zitat:

Zitat von dizzy

Brief

Wohl eher eine Frachtsendung :roll: - Ich bin zur Zeit bei 9^470.000. Das ist eine ca. 450KB große Zahl ;-)

...:cat:...

P.S.: Das sind in Courier New (Größe 6pt) auf A4 32,2 Seiten ;-)

[-homer-]

hi,


lol???


-homer-

[Stanlay Hanks]

Zitat:

Zitat von -homer-

lol???

Glaubst du das nicht? Also ich kann mir das schon vorstellen :wink:

[Robert_G]

Oooch man, das läuft ja nicht unter .Net ... :cry:
Muss ich wohl doch noch das gute alte D7 anwefen. :wink:

[sakura]

Also, von ca. 9^380Mio bin ich nach 16 1/2 h bei 9^1,5Mio angekommen. Wen es interessiert, der möge sich die Lösung anschauen: 9^1.500.000.zip (ca. 659KB)

...:cat:...

[Matze]

Boah, das braucht ja ewig, bis es mal geöffnet ist.

Woher weiß ich, ob das Ergebnis auh stimmt? :stupid:

[MathiasH]

ohm 9^9^9 ist doch 9^(9^9), oder hab ich da in Mathe was falsch mitgekriegt? potentiert wird doch in umgekehrter Reihenfolge, oder? Dieses Zahl ist allerdings erheblich größer und der Integer Typ ist mit dem Ergebniss klar überfordert (9^387420489). Dafür braucht man dann wahrscheinlich nen Datentyp mit real und exponten teil, sonst dürfte die Sache verdammt groß und unpraktisch(langsam) werden (bereits 9^387420 hat mehr als 3k Stellen)

//edit verdammt hab übersehen dass das topic mehr als eine Seite hat

mahiasH

[sakura]

Zitat:

Zitat von MathiasH

(bereits 9^387420 hat mehr als 3k Stellen)

Hat ca. 350K Stellen ;-)

...:cat:...

[Stanlay Hanks]

Boah...Was hast du denn für nen PC? :shock: Das geht ja im Vergleich zu mir wirklich schnell!

[sakura]

Zitat:

Zitat von Stanlay Hanks

Boah...Was hast du denn für nen PC? :shock: Das geht ja im Vergleich zu mir wirklich schnell!

Hast Du Dein oder mein Programm genutzt?

...:cat:...

[Robert_G]

Also ich habe Gestern abend dein Programm laufen lassen, es war nach ca. 1h bei 9^700.000.
Das Problem ist halt, wenn man HT aktiviert, bekommt das Prog ja nur den halben Chip :wink:

[sakura]

Zitat:

Zitat von Robert_G

Also ich habe Gestern abend dein Programm laufen lassen, es war nach ca. 1h bei 9^700.000.

Nach einer Stunde war ich etwa auch so weit, nur dann wird es langsam... 18h10' ... 9^1.570.000

...:cat:...

[Robert_G]

Der Vorteil an HT ist aber, dass ich nebei noch Homeworld2 spielen konnte :twisted:

[Brainstalker]

Hi Leutz!

Ich hab mir mal das gesamte Thema durchgelesen. Is ja schon ganz lustig was da rauskommt. Zum Spaß hab ich mal überschlagsweise ausgerechnet wie lange man brauchen würde um diese Zahl komplett auszurechnen. Man bräuchte mit einem 2GHz Prozessor ca.:

600.000 entspricht 1 = 1 Stunde
1.200.000 entspricht 2 = 16 Stunden
1.800.000 entspricht 3 = 256 Stunden
.
.
.

Wenn die Zeit potenziell ansteigt, würde folgende Rechnung rauskommen:
16^(n-1)


Gehen wir von der Zahl 380.000.000 ausgehen müssen wir folgendes rechnen:
380.000.000 / 600.000 = 633 gerundet
16^(633-1) = 1,0088556685366825650009227055012e+761
Das entspricht einer Zahl mit 761 Ziffern.
Das Ergebnis ist in Stunden, also teilen wir das Ganze durch 24 für Tage und durch 365 für Jahre:
4,2035652855695106875038446062548e+759 Tage
1,1516617220738385445216012619876e+757 Jahre

Also kommen wir zum Ergebnis von:

1,1516617220738385445216012619876e+757 Jahre

Habe ich richtig gerechnet?


MfG Brainstalker

[Matze]

Hi!

Herzlich willkommen in der DP!

Boah, dass es so lange dauert hätt ich nicht gedach. :shock:

[-homer-]

hi,


wer hat denn jetzt mal die fertige Lösung???



-homer-

[Robert_G]

[ProllMode]
Kann ich ja heute Abend mit meinem neuen Prescott P4 ausprobieren.
Ich bin mir ziemlich sicher, bis Morgen früh habe ich dann nur 400.000 Jahre gebraucht :lol: :stupid:
[ProllMode]

[-homer-]

hi,


das wäre echt nett. Danke.


-homer-

[Brainstalker]

@ -homer-
Ich denke nicht, das du je eine Lösung bekommen wirst, da die Prozessoren der heutigen Generation vieeeeel zu langsam sind. Ich weiß nicht was Hochleistungsrechner schaffen, aber für mich scheint es (in den nächsten 20 Jahren) unmöglich. Ich glaube auch nicht, das dein Lehrer dir die Aufgabe gestellt hat, damit du ihm das ergebnis lieferst, sondern das du dich einmal richtig mit mathe beschäftigst.

Leute ich hatte mich verrechnet, das Ergebnis müsste folgendermaßen lauten, denn die Zeit müsste potenziell steigen, da die Zahl auch potenziell steigt:

Zitat:

Zitat von Brainstalker

Hi Leutz!

Ich hab mir mal das gesamte Thema durchgelesen. Is ja schon ganz lustig was da rauskommt. Zum Spaß hab ich mal überschlagsweise ausgerechnet wie lange man brauchen würde um diese Zahl komplett auszurechnen. Man bräuchte mit einem 2GHz Prozessor ca.:

600.000 entspricht 1 = 1 Stunde
1.200.000 entspricht 2 = 16 Stunden
1.800.000 entspricht 3 = 256 Stunden
.
.
.

Wenn die Zeit potenziell ansteigt, würde folgende Rechnung rauskommen:
16^(n-1)


Gehen wir von der Zahl 380.000.000 ausgehen müssen wir folgendes rechnen:
380.000.000 / 600.000 = 633 gerundet
16^(633-1) = 1,0088556685366825650009227055012e+761
Das entspricht einer Zahl mit 761 Ziffern.
Das Ergebnis ist in Stunden, also teilen wir das Ganze durch 24 für Tage und durch 365 für Jahre:
4,2035652855695106875038446062548e+759 Tage
1,1516617220738385445216012619876e+757 Jahre

Also kommen wir zum Ergebnis von:

1,1516617220738385445216012619876e+757 Jahre

Habe ich richtig gerechnet?


MfG Brainstalker

[-homer-]

hi,

also mein Mathelehrer hat das Ergebnis auf seinem PC. Und der hat dafür kein Jahr gebraucht. Das Ergebnis soll ja auch eigentlich NUR 25Seiten lang sein. Dafür braucht man doch kein Jahr.



-homer-

[-homer-]

hi,

da ist mir noch eine Idee: Könnten wir nicht irgentwelche Mathe-Speed Units einbinden, die das errechnen der Zahl verschneller? Ich meine jetzt nicht so Units wie Math oder so, sondern eher welche, die wirklich NUR rechnen und sonst keinen weiteren Speicher verbrauchen.



-homer-

[negaH]

Zitat:

600.000 entspricht 1 = 1 Stunde
1.200.000 entspricht 2 = 16 Stunden
1.800.000 entspricht 3 = 256 Stunden

Also ich habe das auch mal ausgerechnet:

9^600.000 = 100ms
9^1.200.000 = 220ms
9^1.800.000 = 545ms

auf meinem P4 1.5GHz Rechner. Die benutzte Bibliothek findest du sogar hier im Forum.
Somit dürften die 256 Stunden enorm stark übertrieben sein.

Allerdings bei 9^387.420.489 dürften nicht das Problem die Berechnung an sich sein, sondern der enorm hohe Speicherverbrauch. Rein theoretisch kann man 9^387.420.489 in Big O = O(1) berechnen, also schneller als eine Addition. Dazu benötigt man eine Mathematische Bibliothek die die Zahlen intern zur Basis 9 darstellt. Bei solchen Zahlen müsste man nur an der Ziffernpossition 387.420.489 eine 1 setzen und fertig wäre die Berechnung. Als Beispiel: wir wollen 2^387.420.489 berechen mit Binärzahlen. Wir setzen dann einfach in einem Speicher aus lauter Nullen an der Bitposition 387.420.489 eine 1 und schon steht im Speicher 2^387.420.489. Exakt so kann man auch 9^387.420.489 berechnen falls die Zahlenbasis zu 9 ist. 2^387.420.489 benötigt 387.420.489/8 Bytes an Speicher , das sind 47Mb. 9^(9^9) käme auf ca. 240Mb in Binärdarstellung.

Allerdings: 9^9^9 = (9^9)^9 =
196 62705 04755 52913 61807 59085 26912 11628 31034 50944 21476 69273 15415 53796 63911 96809

in 0.02 ms berechnet. Punkt vor Strich ansonsten von links nach rechts.

Gruß Hagen

[-homer-]

hi,

ok, solange will ich nun auch nicht vor meinem Pc sitzen. Könnt ihr mir denn sagen, wieviele Spalten das sind?


-homer-

[negaH]

Ich habe mal die Berechnungen mit meiner Library hochgerechnet. Sie dauert ca. 5-6 Minuten, ABER !! sie benötigt zeitweise mehr als 900Mb Speicher. Nungut man könnte sagen bei 512Mb Hauotspeicher mache ich einfach die Auslagerungsdatei größer, Windows wird's schon richten. Geht aber nicht, die Performance sinkt dadurch auf 2 Prozent was die Berechnung erheblich verlangsammt.

Also, wenn einer eine Machine mit 1-2 GB Hauptspeicher hat, der soll sich melden und ich lasse ihm das Program zukommen.

Gruß Hagen

[sakura]

Zitat:

Zitat von negaH

Also, wenn einer eine Machine mit 1-2 GB Hauptspeicher hat, der soll sich melden und ich lasse ihm das Program zukommen.

*meld*

...:cat:...

[negaH]

anbei das Program.

Zuerst müsst ihr das Program auf eine Platte entpacken die mindestens 1Gb Platz hat. Dann startet ihr es und klickt im Menu auf "Estimate". Diese Funktion berechnet die nötige Zeit und die minimale Dateigröße der Dezimalen Zahl 9^9^9.

Mit "Calculate" berechnet ihr diese Zahl, allerdings kann ich nicht sagen ob 1Gb Hauptspeicher auch tatsächlöich ausreicht. Die berechneten Zeiten beziehen siech auf einen Rechner mit ungegrenz großem Hauptspeicher.
Zuerst wird 9^9^9 als binäre Zahl berechnet und diese Zahl in die Datei "9x9x9.bin" gespeichert. Danach wird diese Zahl in eine Dezimalzahl umgewandelt, das kann nochmal einige Zeit in Anspruch nehmen. Deren Ausgabe wird in die Datei "9x9x9.txt" gespeichert. Diese Datei wird mit Sicherheit größer als 400Mb sein.

Ich hoffe das meine Aufwandsberechnungen richtig sind.

Gruß Hagen

[Robert_G]

*Meld*
Kann erst heute Abend testen (ich muss hier im Büro vorübergehend an 'nem AMD arbeiten :cry: )

[negaH]

Achso, ein Pentium 4 wäre anzuraten, da meine Funktionen intern SSE2 Assembler benutzen. Beim AMD wird dieser Befehlssatz nicht unterstützt und somit dürfte die Performace ca. 2 mal langsamer sein.

Gruß Hagen

[Robert_G]

Das Problem war mir bewusst, deshalb der Einwand mit dem AMD (Außerdem dürfte dein Algo von 800 Mhz FSB profitieren und ich kann den neuen PressKopf mal testen :wink: )

[nailor]

und wer kontrolliert hinterher, dass der Code von Hagen keine Zufallszahl liefert

ach ja: nein, ich hab mir das Archiv nicht runtergeladen und nach Quelltext geguckt, weil ich nicht zufällig nen Gig RAM hab

[sakura]

@Hagen: Geschätzt sind 4 Minuten. Nach knap 6 Minuten hat Dein Proggie die Datei 9x9x9.bin gespeichert - seit dem macht es weiter und weiter und weiter ... nur was :shock:

...:cat:...

[-homer-]

hi,

@Sakura: Vielleicht installiert dir das Prog ja gerade einen Wurm.^^



-homer-

[Stanlay Hanks]

Ich schätze mal, es rechnet :wink:
Jeder kann sich ja mal verrechnen *gg*
Man liest sich, Stanlay :hi:

[negaH]

Zitat:

@Hagen: Geschätzt sind 4 Minuten. Nach knap 6 Minuten hat Dein Proggie die Datei 9x9x9.bin gespeichert - seit dem macht es weiter und weiter und weiter ... nur was

Tja, es wandelt nun die errechnete Binärzahl von 9^(9^9) in einen Dezimal Zahlen String um. Dies wird mit Sicherheit länger dauern als die eigentliche Berechnung von 9^(9^9).

Bei der Berechnung von 9^(9^9) sind ausschließlich nur Multiplikationen und Quadrierungen nötig. Bei der Umwandlung in einen Dezimal-String sind aber zusätzlich Divisionen und String-Operationen nötig. Ich habe zwar für diesen Algo. wesentlich effizientere Methoden benutzt als Marcel Martin's Code, aber denoch must du bedenken das wir hier von einer rießigen Zahl reden.

Man könnte sich den ganzen Umrechnungs-quatsch sparen indem man nicht zur Zahlenbasis 2^32 sondern 10^9 rechnet. D.h. die Zahlen und alle Berechnungen intern werden auf Speicherstrukturen durchgeführt die kleine Happen zu 10^9 enthalten. Am Ende käme eine große Zahle raus die mit der Dezimaldarstellung identisch wäre. ABER! dadurch sinkt die Performance der eigentlichen Berechnung erheblich, und viel schlimmer noch: ich müsste meinen kompletten Code komplett neu schreiben. Die Anzeigen zu den Basen 2,4,8,16,32,64 ist dageben enorm schnell mit meiner Library, sowie auch Marcel's, da wir beide zur Zahlenbasis 2^32 arbeiten. 2^32 ist nur eine Potenz der Basis 2, d.h. im Grunde arbeiten beide Libraries mit echten Binärzahlen.

Ich bin aber noch am überlegen, denn wenn ich mich richtig erinnere gibt es bei Potenzen zu 9 ganz bestimmte Tricks wie man ohne aufwendige Berechnungen das Resultat erzielen kann.

Gruß Hagen