Verschoben! Wie lange braucht man um 2^3!^4! zu berechnen?

09.04.2013, 15:20

mr.eddi

Wie lange braucht man um 2^3!^4! zu berechnen?

Meine Frage:
Hallo,
es geht darum eine möglichst große Zahl zu erzeugen wenn man nur 2,3 und 4 benutzen darf. Ich dachte mir $\begin{eqnarray*} 2^{3!^{4!}} \end{eqnarray*}$ sollte groß genug sein (vllt sogar das maximal mögliche?). Da es schon mit 2^100000 schwierig wird, ist es mit ~ $\begin{eqnarray*} 2^{3\cdot 10^{18}} \end{eqnarray*}$ wohl unmöglich das noch in diesem Leben mit meinem Taschenrechner zu berechnen Big Laugh

Weiß jemand wie lange das auf einem Haushaltsüblichen PC dauern wird, oder brauch man schon einen PC um zu berechnen wie lange es dauern wird das zu berechnen? Big Laugh

Meine Ideen:
Bei CPUs gibt es ja den Begriff FLOPS, die aber nur Addition und Multiplikation pro Sekunde angeben (bei meiner CPU 90 GigaFLOPS). Keine Ahnung wie das mit Potenzen funktioniert...

10.04.2013, 00:24

subbero

Auf diesen Beitrag antworten »

RE: Wie lange braucht man um 2^3!^4! zu berechnen?
Hallo.

Ja, es ist so, dass Computer nur addieren.

Stichworte sind hier:

Binäre Logikoperatoren
Zweierkomplement usw.

Im Falle von Potenzen wird irgendwo eine Library des jeweiligen Betriebssystems genutzt oder auch externe gesondere Librarys, welche die Potenz als Programmfunktion bereitstellen.

Hier hängt es davon ab, wie diese Funktion realisiert wurde, welche Rechenschritte vorgenommen werden usw.

Leider kann man ohne Kenntnis dieser Funktion kaum eine Aussage darüber machen, wie schnell eine solche Berechnung gelöst wäre.

Im Allgemeinen nutzt man auch häufig ein eigenes Wissenschaftsgebiet, nämlich die Numerik.
Bei diesem Gebiet geht es darum, z.B große Zahlen mit bestimmten Algorithmen zu berechnen.

Leider ist beispielsweise bereits die Datenwortbreite der CPU (64 Bit, 32 usw.) ein limitierender Faktor, so dass man sich der Numerik bedient. Fließkommazahlen gibt es natürlich auch, welche aber in einem eigenständigen Rechenwerk bearbeitet werden. Dies ist die Floating Point Unit. Eine Erweiterung, welche bei modernen Prozessoren gleich miteingebaut ist.

Je nach Prozessor können auch mehrere Register verwendet werden um größere Zahlen darzustellen. Beispielsweise bei 32 Bit CPUs bis zu 128 Bit große Integerzahlen.

Leider kann ich so nicht direkt helfen. Insbesondere bei proprietärer Software, wie Windows und hier ggf. auch proprietären Mathematik Libarys hat man keine Einsicht in den Code. Man kann aber ggf. versuchen den Binärcode in einem Disassembler zu betrachten, aber man muss wissen, wo die entsprechende Funktion sich befindet.

Eine Betrachtung auf Maschinenebene ist auch viel eher geeignet Rechenzeiten für eine Funktion zu ermitteln.
Hier muss man aber auch wissen, wieviele Taktzyklen die jeweilige Instruktion benötigt.

Bei modernen CPUs kommt aber auch das Pipelining hinzu, so dass man keine 100 prozentige Aussage machen kann, wie dies sich in der Realität bemerkbar macht. Beispielsweise wenn Cache Misses auftreten usw.

10.04.2013, 00:25

subbero

Auf diesen Beitrag antworten »

RE: Wie lange braucht man um 2^3!^4! zu berechnen?
Kurzum:

Hängt von der Realisierung der Funktion ab, welche Potenzen berechnet
Von der CPU und somit auch insgesamt der Hardware ab.

11.04.2013, 18:11

maeries

Auf diesen Beitrag antworten »

Also ich versuche das jetzt einfach mal. Ich hab um 18:02 angefangen und melde mich, wenn der PC fertig ist. Ich habe einen Intel q6600 mit 2,4 GHz. Der Taschenrechner unterstützt aber nur einen Kern.
Ich habe mal 1000000! berechnet. Das hat 2Std gedauert.

Oder man benutzt nen Supercomputer, der das in wenigen sekunden schafft: Klick

11.04.2013, 18:33

HAL 9000

Auf diesen Beitrag antworten »

Es geht ja im Prinzip darum, die Zahl $\begin{eqnarray*} 2^m \end{eqnarray*}$ für riesige $\begin{eqnarray*} m \end{eqnarray*}$ ins Dezimalsystem zu konvertieren. Dazu dividiert man sukzessive mit Rest, d.h.

$\begin{eqnarray*} q_0 = 2^m \end{eqnarray*}$

und dann

$\begin{eqnarray*} r_n = q_n \bmod 10,\quad q_{n+1} = q_n \operatorname{div} 10 \end{eqnarray*}$ (d.h. Ganzzahldivision)

Der Aufwand für diese Division mit Rest ist proportional zur "Länge" der Zahl (in Ziffern), also $\begin{eqnarray*} O(m) \end{eqnarray*}$ . Man benötigt etwa $\begin{eqnarray*} m\lg(2) \end{eqnarray*}$ solche Divisionen, um die gesamte Dezimaldarstellung zu bekommen, also $\begin{eqnarray*} O(m) \end{eqnarray*}$ Operationen.

Macht also insgesamt quadratischen Aufwand $\begin{eqnarray*} O(m^2) \end{eqnarray*}$ . Jetzt kannst du mal einen Algorithmus für "moderates" $\begin{eqnarray*} m \end{eqnarray*}$ (sagen wir mal $\begin{eqnarray*} m=10^8 \end{eqnarray*}$ ) schreiben, die Zeit stoppen und dann mal hochrechnen - wobei wir annehmen, dass es dir dann mal gelingt, den nötigen RAM für das Zwischenspeichern der $\begin{eqnarray*} 3\cdot 10^{18} \end{eqnarray*}$ Bits aufzutreiben. Aber das ist wahrscheinlich die geringere Sorge im Vergleich zu der Rechenzeit. Big Laugh

P.S.: Ja, ich weiß - prinzipiell sind auch andere Verfahren denkbar. Aber unter Aufwand $\begin{eqnarray*} O(m^2) \end{eqnarray*}$ dürfte wohl keine der Alternativen zu drücken sein. Augenzwinkern

11.04.2013, 19:02

chrizke

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Macht also insgesamt quadratischen Aufwand $\begin{eqnarray*} O(m^2) \end{eqnarray*}$ . Jetzt kannst du mal einen Algorithmus für "moderates" $\begin{eqnarray*} m \end{eqnarray*}$ (sagen wir mal $\begin{eqnarray*} m=10^8 \end{eqnarray*}$ ) schreiben, die Zeit stoppen und dann mal hochrechnen - wobei wir annehmen, dass es dir dann mal gelingt, den nötigen RAM für das Zwischenspeichern der $\begin{eqnarray*} 3\cdot 10^{18} \end{eqnarray*}$ Bits aufzutreiben. Aber das ist wahrscheinlich die geringere Sorge im Vergleich zu der Rechenzeit. Big Laugh

Ich hab mal versucht die oben genannte Zahl mit python zu berechnen, um zu sehen, wie viel Speicher dafür benötigt wird.
Nach wenigen Minuten habe ich bei 12GB im RAM abgebrochen.

11.04.2013, 19:21

HAL 9000

Auf diesen Beitrag antworten »

Das kann man ganz genau sagen: Die Zahl benötigt bei effizienter binärer Speicherung

$\begin{eqnarray*} \frac{3!^{4!}}{8} = 592297667290202112~\mbox{Byte} \approx 592298~\mbox{TeraByte} \end{eqnarray*}$

um mal rechts eine gegenwärtig übliche Maßeinheit zu verwenden.

11.04.2013, 20:35

subbero

Auf diesen Beitrag antworten »

Re
Und eine Fehlerfreiheit für die gespeicherten Daten zu gewährleisten müsste ebenfalls noch etwas mehr Speicher zur Verfügung stehen.

Bei modernen Solid-State RAMs genügt bereits die natürliche Radioaktivität um hin und wieder Fehler zu produzieren.

11.04.2013, 22:38

maeries

Auf diesen Beitrag antworten »

Mein PC ist bis jetzt zu keinem Ergebnis gekommen

12.04.2013, 10:00

mr.eddi

Auf diesen Beitrag antworten »

Ok danke schon mal für die ganzen Antworten!

Zitat:

Mein PC ist bis jetzt zu keinem Ergebnis gekommen

"Nach wenigen Minuten habe ich bei 12GB im RAM abgebrochen"
"592298 TeraByte"

Angenommen da wird wirklich theoretisch immer weiter reingeschrieben bis der Speicher bei ~600000 TB angelangt ist, dann würde er pro Jahr etwa 1000 TB schreiben (wenn 12GB in ~6 Min geschrieben werden) und insgesamt etwa 600 Jahre brauchen.

Sebst wenn es 100 mal schneller ginge würde ich es nicht ausrechnen wollen, geschweige denn können. Naja mir reicht die Erkentniss, dass der versuch es ausrechnen zu wollen sehr naiv war Big Laugh

Neue Frage »

Antworten »

Verschoben! Wie lange braucht man um 2^3!^4! zu berechnen?

Verwandte Themen