PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : 9^(9^9)


Seiten : 1 [2]

BubbleBoy
2004-07-07, 18:29:58
Original geschrieben von Gast
hm aber es muss ja ne 1 mit 387420489 rauskommen...
also 10^387420489 stimmt? bin nich so gut in 10erpotenzen, kann ja sein dass es 10^387420488 sein muss oder so damits stimmt...
Nee,

<dezimalmodus>

10^2 = 100 (eine '1' mit zwei Nullen)

</dezimalmodus>

;D

BubbleBoy
2004-07-07, 18:34:30
Original geschrieben von Gast_ich
sollte man die 387420489 nich konsequenter weise auch im 9er-system schreiben? also 10^1000000000
Och man, das wird zu kompliziert.

@Threadstarter
Bleibe bei der Version mit 9^387420489 im Dezimalsystem entspräche einer '1' mit 387420489 Nullen im System zur Basis 9.

liquid
2004-07-07, 20:42:17
{
o3uint32 iters = 0;

// create big integers
mpz_t result;
mpz_t nine_pow_nine;
mpz_t a;
mpz_t b;
mpz_t temp;

// init big integers
mpz_init(result);
mpz_init(nine_pow_nine);
mpz_init(a);
mpz_init(b);
mpz_init(temp);

// set values
mpz_ui_pow_ui(nine_pow_nine, 9, 9);
mpz_set_ui(result, 1);

// a = 9
// b = 9^9

mpz_set_ui(a, 9);
mpz_set(b, nine_pow_nine);

while (mpz_cmp_ui(b, 0) > 0)
{
std::cout << "iteration begin\n";
std::cout << "iter: " << iters << std::endl;
++iters;

// temp = b MOD 2
mpz_mod_ui(temp, b, 2);

// if (temp != 0)
if (mpz_cmp_ui(temp, 0) != 0)
{
// result *= a
mpz_mul(result, result, a);
}

// b /= 2
mpz_divexact_ui(b, b, 2);

// a = a*a
mpz_mul(a, a, a);

std::cout << "iteration end\n";
}

// output to file
FILE* outputfile = std::fopen("math.result", "wb");
mpz_out_str(outputfile, 10, result);
std::fclose(outputfile);
}

Ich hab mich mal hingesetzt und entsprechenden Code mit Verwendung der GMP Library (GNU BigNum) geschrieben.
Es scheitert allerdings an zuwenig Speicher.

Also wer den Source benutzen will der kanns gerne tun.
Ich glaube bei mir isser bis zur 27. Iteration gekommen oder so in den Bereich.

Die GMP müsst ihr dann allerdings mit malloc-reentrant als alloca(tor) compilen, da man mit dem standard alloca nicht sehr weit kommt (wird nur für relativ geringe Zahlenlängen empfohlen).

cya
liquid

del_4901
2004-07-08, 02:02:49
Original geschrieben von mrdigital
bischen wirr, zuviel von deinem Avatar gehabt? ;)
Man kann die Ergebnisse Problemlos wieder aus dem GraKa Speicher auslesen, und die GraKa ist auch nicht ein paar Berechnungen weiter, da sie nicht selbständig irgendwas macht, sondern erst dann, wenn sie vom Hostrechner dazu "aufgefordert" wird. Man kann das also schon synchronisieren.
Die Graka ist ja auch nicht weiter sondern die CPU füttert schonwieder Frames die ca. 3 frrames vor dem gerade von der Graka ausgespuckten Bild liegen.

Ok, es war ein bissel wirr, aber soviel konnte man rauslesen, wenn man genauer geschaut hätt.

mrdigital
2004-07-08, 10:41:35
Ich bin mir nicht sicher, ob ich dein Problem hier richtig verstehe, aber man kann doch noch bevor man die GraKa weiter füttert die Ergebnisse erstmal abholen. Das wird man eh häufig so machen, da man diese Zwischenergebnisse braucht, um die nächsten Rechenschritte anzustossen.

del_4901
2004-07-08, 14:47:10
Original geschrieben von mrdigital
Ich bin mir nicht sicher, ob ich dein Problem hier richtig verstehe, aber man kann doch noch bevor man die GraKa weiter füttert die Ergebnisse erstmal abholen. Das wird man eh häufig so machen, da man diese Zwischenergebnisse braucht, um die nächsten Rechenschritte anzustossen.
toll, dann bringt mir die ganze rechenpower der Graka nicht's, weil ich 2/3 ins Klo kipp.

Dj-Atzy
2004-07-08, 14:48:04
Bei mir bringt Excel das raus:
196.627.050.475.553.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000. 000.000.000.000.000.000,000000000000000000000000000000

Gast
2004-07-08, 14:49:21
Original geschrieben von Dj-Atzy
Bei mir bringt Excel das raus:
196.627.050.475.553.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000. 000.000.000.000.000.000,000000000000000000000000000000

Bei was?

Dj-Atzy
2004-07-08, 14:54:58
9^81

Dj-Atzy
2004-07-08, 14:57:47
Oh kleiner Rechenfehler man muss ja 9^387420489 und dann kommt bei Excel ZAHL! raus

BubbleBoy
2004-07-08, 15:46:22
Original geschrieben von Dj-Atzy
Bei mir bringt Excel das raus:
196.627.050.475.553.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000. 000.000.000.000.000.000,0
Original geschrieben von Dj-Atzy
9^81
Kannste mal sehen, wie besch..eiden Excel ist. Mein Taschenrechner sagt:

196627050475552913618075908526912116283103450944214766927315415537966391196809 ;D


Desweiteren hättest du ruhig die ersten Postings lesen können, da wurde das bereits eindringlichst geklärt, daß 9^9^9 != 9^81 ist.

Edit: Unkorrektheit beseitigt ;(

Gast
2004-07-08, 17:37:32
Original geschrieben von BubbleBoy
Desweiteren hättest du ruhig die ersten Postings lesen können, da wurde das bereits eindringlichst geklärt, daß 9^(9^9) != 9^9^9 = 9^81 ist. Falsch: a^b^c = a^(b^c) != (a^b)^c = a^(bc)

mrdigital
2004-07-08, 17:44:44
Original geschrieben von AlphaTier
toll, dann bringt mir die ganze rechenpower der Graka nicht's, weil ich 2/3 ins Klo kipp.
Hu wieso das denn? Die GraKa wird in diesem Fall wie ein Coprozessor verwendet, da wird dann doch auch nichts ins Klo geschmissen. Aber wenn du nochmal deine Idee erläuterst, dann wirds vielleicht klarer.

BubbleBoy
2004-07-08, 18:11:08
Original geschrieben von Gast
Falsch: a^b^c = a^(b^c) != (a^b)^c = a^(bc)
Hast ja recht, denke aber, daß es rüber gekommen ist was ich sagen wollte.

del_4901
2004-07-08, 19:42:14
Original geschrieben von mrdigital
Hu wieso das denn? Die GraKa wird in diesem Fall wie ein Coprozessor verwendet, da wird dann doch auch nichts ins Klo geschmissen. Aber wenn du nochmal deine Idee erläuterst, dann wirds vielleicht klarer.
Die CPU wartet auf die Graka (die braucht ca. die zeit von 3 frames um das durchzuwürgen), dann wartet die Graka auf die CPU, bis das Bild aus dem Framebuffer abgeholt wurde, und die nächste Itteration von der CPU gestartet wird. Die sind also beide Größtenteils mit warten beschäftigt, u.a auch weil der AGP so langsam ist. (kann man mit der Verbindung zw. CPU und FPU nicht vergleichen)
Während der eine arbeitet, kann der andere auch nicht schon weiterrechnen, weil die Ergebnisse voneinander abhänig sind.

del_4901
2004-07-08, 19:43:54
Was haltet ihr vom NewtonTangenten Annäherungsverfahren ?? Das müsste doch schnell genug sein, oder? x^x^x als funktion darstellen, ableiten und dann zur 9 abschätzen ;)

BubbleBoy
2004-07-08, 20:33:40
Original geschrieben von AlphaTier
Was haltet ihr vom NewtonTangenten Annäherungsverfahren ?? Das müsste doch schnell genug sein, oder? x^x^x als funktion darstellen, ableiten und dann zur 9 abschätzen ;)

Das Verfahren sagt mir im Moment erstmal nichts, aber "Annäherung" und "abschätzen" hören sich nicht so gut an, als daß du am Ende genau 9^9^9 angeben könntest. Bestenfalls bekommst du eine Näherung (die uns aber nicht weiter bringt).

pajofego
2004-07-08, 20:58:10
Um zu Überlegen, ob die Sache von der Grafikkarte gelöst werden kann, bräuchte ich eine Art Pseudo-Code von der Rechenvorschrift. Ist das möglich hier mal kurz zu posten?

Das Tangentenverfahren von Newton ist dazu da, um Nullstellen oder Schnittpunkte von Funktionen zu berechnen. Hier wird ja die ganze Zeit versucht ein Funktionwert zu berechnen (f(x=9) = x^(x^x)), s.d. das o.g. Verfahren nicht viel nützen wird.

Gruss pajofego

del_4901
2004-07-08, 21:00:45
Original geschrieben von BubbleBoy
Das Verfahren sagt mir im Moment erstmal nichts, aber "Annäherung" und "abschätzen" hören sich nicht so gut an, als daß du am Ende genau 9^9^9 angeben könntest. Bestenfalls bekommst du eine Näherung (die uns aber nicht weiter bringt).

Ähm, wenn du darüber was genauers wissen willst, dann meld dich nochmal und ich schau in meine schlauen Mathebücher.

Es handelt sich hierbei wirklich nur um eine Annäherung, man kann das ergebnis, der ersten Iteration, aber wieder in die 2te Iteration (usw. usw.) einsetzen, und das ergebniss nähert sich immer mehr dem echten ergebniss an.

Jeh nachdem wie genau du das ergebiss haben möchtest, wählst du die Anzahl der Itterationen.

del_4901
2004-07-08, 21:03:14
Original geschrieben von pajofego
Um zu Überlegen, ob die Sache von der Grafikkarte gelöst werden kann, bräuchte ich eine Art Pseudo-Code von der Rechenvorschrift. Ist das möglich hier mal kurz zu posten?

Das Tangentenverfahren von Newton ist dazu da, um Nullstellen oder Schnittpunkte von Funktionen zu berechnen. Hier wird ja die ganze Zeit versucht ein Funktionwert zu berechnen (f(x=9) = x^(x^x)), s.d. das o.g. Verfahren nicht viel nützen wird.

Gruss pajofego

mhm, jetzt wo du's sagst könntest du sogar recht haben, mhm dann muss man halt dafür sorgen das dort die Nullstelle liegt ... das geht bestimmt Mathematiker machen doch alles gern linear und sonnstwas ...

del_4901
2004-07-08, 21:14:03
Newton war ja auch Falsch.

ich meinte den guten Taylor mit seiner Reihe und dem dazugehörigen Annäherungsverfahren :)
http://www.mathe.braunling.de/Taylor.htm

BubbleBoy
2004-07-08, 21:27:49
Original geschrieben von AlphaTier
Newton war ja auch Falsch.

ich meinte den guten Taylor mit seiner Reihe und dem dazugehörigen Annäherungsverfahren :)
http://www.mathe.braunling.de/Taylor.htm
*Hüstel*

Satz von Taylor: Ist eine Funktion f in einem Intervall I (Teilmenge von) R beliebig oft differenzierbar ...

Frank
2004-07-08, 21:29:49
Original geschrieben von BubbleBoy
Das Verfahren sagt mir im Moment erstmal nichts, aber "Annäherung" und "abschätzen" hören sich nicht so gut an, als daß du am Ende genau 9^9^9 angeben könntest. Bestenfalls bekommst du eine Näherung (die uns aber nicht weiter bringt). Du glaubst gar nicht wie man Numerik bis zum Exzess betreiben kann, um wirklich genaue Ergebnisse zu haben. Und wenn sie nicht genau sind, dann weißt du aber die Fehlabweichung und und ... bla. :)

Frank
2004-07-08, 21:34:14
Original geschrieben von BubbleBoy
*Hüstel* Und ist dass bei x^x^x ein Problem? Aussderm entwickelst du die Taylorreihe auch nur bis zum einem gewissen Glied. Halt ich aber hier für nicht praktikabel...

del_4901
2004-07-08, 21:36:57
Original geschrieben von BubbleBoy
*Hüstel*

Na das geht doch noch, ich würde mir eher sorgen machen wie ich x^x^x ableiten soll, bzw. ich würde mir da keine sorgen machen ... aber es ist aufwändig, und ich will grad nicht überlegen ;)
differenzierbar ist der Misst grarantiert (da keine Ecken und Kanten vorhanden :) )

BubbleBoy
2004-07-08, 21:38:58
Original geschrieben von Frank
Du glaubst gar nicht wie man Numerik bis zum Exzess betreiben kann, um wirklich genaue Ergebnisse zu haben. Und wenn sie nicht genau sind, dann weißt du aber die Fehlabweichung und und ... bla. :)
Auch mal gehabt :( (vor langer Zeit - nichts hängen geblieben ;(). Habe aber auch keine Lust mich da jetzt wieder reinzulesen :D.


Also:
Es gilt 9^387420489 im Dezimalsystem zu berechnen. Mach einen Vorschlag ;D.

del_4901
2004-07-08, 21:39:36
Original geschrieben von Frank
Und ist dass bei x^x^x ein Problem? Aussderm entwickelst du die Taylorreihe auch nur bis zum einem gewissen Glied. Halt ich aber hier für nicht praktikabel...

Schlag was anderes vor, 9^9^9 auszurechnen ist unpraktikabler ... . Ich hab noch nicht soviele Numerische Annäherungsmethoden gehabt, da unser Studiengang so geil ist das man Numerik(musste ich knicken) und Analysis im gleichen Semester hatte ... aber egal.

BubbleBoy
2004-07-08, 21:43:18
Original geschrieben von Frank
Und ist dass bei x^x^x ein Problem?
Ich will's nicht machen :(.

Original geschrieben von Frank
Aussderm entwickelst du die Taylorreihe auch nur bis zum einem gewissen Glied. Halt ich aber hier für nicht praktikabel...
Wie schnell nähert die sich dem entsprechenden Wert an?

del_4901
2004-07-08, 21:47:45
Original geschrieben von BubbleBoy
Ich will's nicht machen :(.


Wie schnell nähert die sich dem entsprechenden Wert an?

Kommt drauf an, wie genau du's haben willst.

ich nenne da mal ein Bsp aus der Hardwareindustrie:
Ati berrechnet den SinCos mithilfe einer Taylorreihe in 8 Schritten, und das ist für die genau genug.

BubbleBoy
2004-07-08, 21:59:08
9^9^9 ist eine Zahl mit ~360-370 Mio. Stellen. Ich (und andere) möchten jede einzelne davon. D.h. wenn sich deine Taylor-Reihe nicht irsinnig schnell an diese Zahl annähert, bist du mit den Divisionen, Fakultäten und Potenzen warscheinlich nicht wirklich schneller als mit einem klassischen Ausmultiplizieren.

Frank
2004-07-08, 22:46:45
Original geschrieben von BubbleBoy
9^9^9 ist eine Zahl mit ~360-370 Mio. Stellen. Ich (und andere) möchten jede einzelne davon. D.h. wenn sich deine Taylor-Reihe nicht irsinnig schnell an diese Zahl annähert, bist du mit den Divisionen, Fakultäten und Potenzen warscheinlich nicht wirklich schneller als mit einem klassischen Ausmultiplizieren. Genau das ist doch das Problem. Das Handling mit den großen Zahlen wird einem durch irgendwelche numerische Verfahren nicht erspart - es verschlimmert sich eher noch.

Das einzigste was hilft, wäre eine Aufsplittung derart: 9^387420489 in 9^(387420489/81+387420489/81+...) umschreiben. x=9^387420489/81 ist noch innerhalb einer Minute per Maple ausrechenbar - darüber reicht dann langsam das Zahlensystem nicht mehr aus. dann x*x*x*... 81 mal. Alles aufsplitten. Nebenbei noch eine schnelle Multiplikation à la Karatsuba verwenden ... und dann dürfts nach Zeit y ja mal rauskommen. Evtl wurde das auch schon weiter oben erzählt - bin aber grad zu bequem, den Thread nochmal durchzustöbern.

Zool
2004-07-09, 13:12:13
Es ist kein Probleme die Funktion y=f(x)=x^(x^x) im Punkt X0=9 in eine Taylorreihe zu enwickeln da die Fkt. ohne weiteres beliebig oft differenzierbar ist.
Aber eben halt nur analytisch. Numerisch ist es genauso so schwer (oder schwerer) wie 9^(9^9) direkt zu berechnen, weil man die großen Zahlen so schwer handhaben kann.

In der Analysis wird das Problem einfach erschlagen in dem man eine unendliche Taylor-Summe aufschreibt (ev. nach Vereinfachungen sucht) und das ganze so wie es ist stehen lässt.

In der Analysis zeigt man nur Rechenwege und Lösungen auf. Das Ausrechnen des nummerischen Wertes interessiert den Mathematiker wenig. Er freut sich wenn er zeigt, daß die Lösung existiert und und zudem noch eindeutig ist. Fertig.

Frank
2004-07-09, 13:16:15
Original geschrieben von Zool
Er freut sich wenn er zeigt, daß die Lösung existiert und und zudem noch eindeutig ist. Fertig. Genau deswegen mach ich diese letztendlich triviale Aufgabe nicht. :D

mrdigital
2004-07-09, 13:36:25
Original geschrieben von AlphaTier
Die CPU wartet auf die Graka (die braucht ca. die zeit von 3 frames um das durchzuwürgen), dann wartet die Graka auf die CPU, bis das Bild aus dem Framebuffer abgeholt wurde, und die nächste Itteration von der CPU gestartet wird. Die sind also beide Größtenteils mit warten beschäftigt, u.a auch weil der AGP so langsam ist. (kann man mit der Verbindung zw. CPU und FPU nicht vergleichen)
Während der eine arbeitet, kann der andere auch nicht schon weiterrechnen, weil die Ergebnisse voneinander abhänig sind.
Wieso 3 Frames? Es werden da keine "Frames" mehr berechnet. Das die CPU dabei wartet, nimmt man doch in Kauf, wenn dieses spezielle Problem vom Coprozessor (hier die GraKa) schneller als mit der CPU direkt gelöst werden kann. Das der AGP zu langsam ist, wage ich mal zu bezweifeln.

Dj-Atzy
2004-07-09, 13:42:05
Hi
Hier: http://mathforum.org/library/drmath/view/61451.html

Wurde das Problem auch schon mal behandelt: Da hat einer
196,627,050,475,552,913,618,075,908,526,912,116,283,103,450,944,214,76
6,927,315,415,537,966,391,196,809

Die Seite ist auf Englisch, daher die Kommas

Gast
2004-07-09, 13:55:03
Original geschrieben von Dj-Atzy
Hi
Hier: http://mathforum.org/library/drmath/view/61451.html

Wurde das Problem auch schon mal behandelt: Da hat einer
196,627,050,475,552,913,618,075,908,526,912,116,283,103,450,944,214,76
6,927,315,415,537,966,391,196,809

Die Seite ist auf Englisch, daher die Kommas
und täglich grüßt das murmeltier... :D :D
arbeitet eigentlich wer an einem programm das die graka rechnen lässt? oder an andern programmen?
und erklärt mir nochmal wer das neuner-system, warum wird da aus 9^9^9 10^9^9 und nicht 10^10^10 ?(
und wie weit seits ihr mit "neun" schon? ich bin erst bei 294000 potenzen = 0.0008% :freak2:

BubbleBoy
2004-07-09, 14:37:21
Original geschrieben von Dj-Atzy
Hi
Hier: http://mathforum.org/library/drmath/view/61451.html

Wurde das Problem auch schon mal behandelt: Da hat einer
196,627,050,475,552,913,618,075,908,526,912,116,283,103,450,944,214,76
6,927,315,415,537,966,391,196,809

Die Seite ist auf Englisch, daher die Kommas
Dein Interesse in allen Ehren, aber ich glaube, du peilst das nicht ...

Nachdem du hier (http://www.forum-3dcenter.org/vbulletin/showthread.php?postid=1995064#post1995064) bereits Excels Näherung an diese Zahl erwähnt hast, hier (http://www.forum-3dcenter.org/vbulletin/showthread.php?postid=1995092#post1995092) meintest es wäre die Darstellung von 9^81 und ein Post weiter (http://www.forum-3dcenter.org/vbulletin/showthread.php?postid=1995105#post1995105) dann selbst (?) gemerkt hast, daß wir 9^387420489 suchen (es dir zwischendurch auch nochmal gesagt wurde), kommst du jetzt wieder mit 9^81 an.

Ich fasse das langsam als :spam: auf!

BubbleBoy
2004-07-09, 14:41:41
Original geschrieben von Frank
Genau deswegen mach ich diese letztendlich triviale Aufgabe nicht. :D
Du bist Mathematiker?

Frank
2004-07-09, 15:11:53
Original geschrieben von BubbleBoy
Du bist Mathematiker? Wenn ich meine Diplomarbeit im nächsten halben Jahr noch fertig schreibe... ja. :D

BubbleBoy
2004-07-09, 15:53:09
Original geschrieben von Frank
Wenn ich meine Diplomarbeit im nächsten halben Jahr noch fertig schreibe... ja. :D
<OT>
Au Backe, ich weiß, das hast du bestimmt schon (zu) oft gehört, aber ... was macht man als Mathematiker (außerhalb von Universitäten und Geheimdiensten)? :kratz2:
</OT>

Ganon
2004-07-09, 17:38:51
Original geschrieben von BubbleBoy
<OT>
Au Backe, ich weiß, das hast du bestimmt schon (zu) oft gehört, aber ... was macht man als Mathematiker (außerhalb von Universitäten und Geheimdiensten)? :kratz2:
</OT>

9^(9^9) schriftlich ausrechnen. ;)

Gast
2004-07-10, 13:33:07
will mir nich nochmal wer das 9er-system erklären? ich verstehs noch ned so ganz warum dann 10^387420489 rauskommt ?(

BubbleBoy
2004-07-10, 15:37:21
Original geschrieben von Gast
will mir nich nochmal wer das 9er-system erklären? ich verstehs noch ned so ganz warum dann 10^387420489 rauskommt ?(
Also, erstmal dezimal:

1234 zur Basis 10 setzt sich wie folgt zusammen:

1*10^3 + 2*10^2 + 3*10^1 + 4*10^0 = 1234


Wenn 1234 zur Basis 9 dezimal dargestellt werden soll, wird halt:

1*9^3 + 2*9^2 + 3*9^1 + 4*9^0 = 1234(_9) = 922 (dezimal)



Wenn ich nun umgekehrt z.B. 9^3=729 (dezimal) im Neunersystem darstellen will, kommt raus:

1*9^3 + 0*9^2 + 0*9^1 + 0*9^0 = 1000(_9)

Gast
2004-07-10, 16:08:32
Original geschrieben von BubbleBoy
Also, erstmal dezimal:

1234 zur Basis 10 setzt sich wie folgt zusammen:

1*10^3 + 2*10^2 + 3*10^1 + 4*10^0 = 1234


Wenn 1234 zur Basis 9 dezimal dargestellt werden soll, wird halt:

1*9^3 + 2*9^2 + 3*9^1 + 4*9^0 = 1234(_9) = 922 (dezimal)



Wenn ich nun umgekehrt z.B. 9^3=729 (dezimal) im Neunersystem darstellen will, kommt raus:

1*9^3 + 0*9^2 + 0*9^1 + 0*9^0 = 1000(_9)
*räusper*
das ist so aber falsch...
1234 zur Basis 10 ist, wie du richtig gesagt hast
1*10^3 + 2*10^2 + 3*10^1 + 4*10^0

die selbe Zahl zur Basis neun ist dann aber:

1 * 9^3 + 6 * 9^2 + 2 * 9^1 + 1 * 9^0 = 1621 (zur Basis 9!)

du hast 1234 zur Basis 9 nach dezimal 922 umgerechnet ;)

mrdigital
2004-07-10, 16:08:58
Original geschrieben von BubbleBoy
Also, erstmal dezimal:

1234 zur Basis 10 setzt sich wie folgt zusammen:

1*10^3 + 2*10^2 + 3*10^1 + 4*10^0 = 1234


Wenn 1234 zur Basis 9 dezimal dargestellt werden soll, wird halt:

1*9^3 + 2*9^2 + 3*9^1 + 4*9^0 = 1234(_9) = 922 (dezimal)



Wenn ich nun umgekehrt z.B. 9^3=729 (dezimal) im Neunersystem darstellen will, kommt raus:

1*9^3 + 0*9^2 + 0*9^1 + 0*9^0 = 1000(_9)
*räusper*
das ist so aber falsch...
1234 zur Basis 10 ist, wie du richtig gesagt hast
1*10^3 + 2*10^2 + 3*10^1 + 4*10^0

die selbe Zahl zur Basis neun ist dann aber:

1 * 9^3 + 6 * 9^2 + 2 * 9^1 + 1 * 9^0 = 1621 (zur Basis 9!)

du hast 1234 zur Basis 9 nach dezimal 922 umgerechnet ;)

Gast
2004-07-10, 16:46:51
Original geschrieben von BubbleBoy
Also, erstmal dezimal:

1234 zur Basis 10 setzt sich wie folgt zusammen:

1*10^3 + 2*10^2 + 3*10^1 + 4*10^0 = 1234


Wenn 1234 zur Basis 9 dezimal dargestellt werden soll, wird halt:

1*9^3 + 2*9^2 + 3*9^1 + 4*9^0 = 1234(_9) = 922 (dezimal)



Wenn ich nun umgekehrt z.B. 9^3=729 (dezimal) im Neunersystem darstellen will, kommt raus:

1*9^3 + 0*9^2 + 0*9^1 + 0*9^0 = 1000(_9)
ich checks immer noch ned so wirklich... :freak2:

BubbleBoy
2004-07-10, 18:17:16
Original geschrieben von Gast
ich checks immer noch ned so wirklich... :freak2:
Na dann noch ein Versuch.

Wenn du im Dezimalsystem (das zur Basis 10 und mit dem wir normalerweise im täglichen Leben umgehen) eine Zahl wie 1234 hast, dann ist die Schreibweise "1234" nur eine Abkürzung für:


1*10^3 (tausender)
+ 2*10^2 (hunderter)
+ 3*10^1 (zehner)
+ 4*10^0 (einer)
---------
= 1234


Ist das bis hier her einzusehen?

Wenn ich also die Zahl 10^5 dezimal darstellen will, dann ex. diese 10^5 direkt als "Grundeinheit":


10^5 10^4 10^3 10^2 10^1 10^0
----------------------------------
1 0 0 0 0 0

Wie du siehst, ist 10^5 im Dezimalsystem eine '1' mit 5 Nullen.

Wenn wir jetzt die dem Dezimalsystem zugrundeliegende Basis wechseln, nehmen wir z.B. statt der 10 die 9, dann existiert z.B. für 9^5 eine "Grundeinheit":

9^5 9^4 9^3 9^2 9^1 9^0
----------------------------------
1 0 0 0 0 0

Genauso ex. auch für 9^387420489 eine solche "Grundeinheit, was dann in einer '1' mit 387420489 Nullen resultieren würde.

BubbleBoy
2004-07-10, 18:23:21
Original geschrieben von mrdigital
*räusper*
das ist so aber falsch...
zeig mir wo :)
Original geschrieben von mrdigital
1234 zur Basis 10 ist, wie du richtig gesagt hast
1*10^3 + 2*10^2 + 3*10^1 + 4*10^0
ok


Original geschrieben von mrdigital
die selbe Zahl zur Basis neun ist dann aber:

1 * 9^3 + 6 * 9^2 + 2 * 9^1 + 1 * 9^0 = 1621 (zur Basis 9!)

richtig, wobei ich die dezimale Zahl '1234' nirgends in das System zur Basis 9 umgerechnet habe ;)
Original geschrieben von BubbleBoy
Wenn 1234 zur Basis 9 dezimal dargestellt werden soll, wird halt:

1*9^3 + 2*9^2 + 3*9^1 + 4*9^0 = 1234(_9) = 922 (dezimal)




Original geschrieben von mrdigital
du hast 1234 zur Basis 9 nach dezimal 922 umgerechnet ;)
richtig, steht ja auch da (s.o.)

Gast
2004-07-10, 20:37:56
Original geschrieben von BubbleBoy
Na dann noch ein Versuch.

Wenn du im Dezimalsystem (das zur Basis 10 und mit dem wir normalerweise im täglichen Leben umgehen) eine Zahl wie 1234 hast, dann ist die Schreibweise "1234" nur eine Abkürzung für:


1*10^3 (tausender)
+ 2*10^2 (hunderter)
+ 3*10^1 (zehner)
+ 4*10^0 (einer)
---------
= 1234


Ist das bis hier her einzusehen?
ja :)

Original geschrieben von BubbleBoy Wenn ich also die Zahl 10^5 dezimal darstellen will, dann ex. diese 10^5 direkt als "Grundeinheit":


10^5 10^4 10^3 10^2 10^1 10^0
----------------------------------
1 0 0 0 0 0

Wie du siehst, ist 10^5 im Dezimalsystem eine '1' mit 5 Nullen.

Wenn wir jetzt die dem Dezimalsystem zugrundeliegende Basis wechseln, nehmen wir z.B. statt der 10 die 9, dann existiert z.B. für 9^5 eine "Grundeinheit":

9^5 9^4 9^3 9^2 9^1 9^0
----------------------------------
1 0 0 0 0 0

Genauso ex. auch für 9^387420489 eine solche "Grundeinheit, was dann in einer '1' mit 387420489 Nullen resultieren würde.
also 10^5 [dez] = 9^5 [9er] versteh ich ja.
aber 9^387420489 [dez] = 10^387420489 [9er]?
entweder da isn wurm drin oder ich checks immer noch ned ?(
des beißt sich doch irgendwo ?(

BubbleBoy
2004-07-10, 21:21:27
Original geschrieben von Gast
also 10^5 [dez] = 9^5 [9er] versteh ich ja.

Ächts, wenn du das so verstehst, daß das beides unterschiedliche Zahlen sind und sich nur in Bezug auf ihr jeweiliges Zahlensystem gleichen, dann ja. Muß mich hier aber auch nochmal korrigieren (s.u.).
Original geschrieben von Gast
aber 9^387420489 [dez] = 10^387420489 [9er]?
entweder da isn wurm drin oder ich checks immer noch ned ?(
des beißt sich doch irgendwo ?(
Richtig, da wird ein Wurm drinne sein. Würde mitlerweile sagen, daß es richtig so lauten müßte:

9^387.420.489 [dez] = 10^1.000.000.000 [9er]

(Es ist auch zu beachten, daß es im Neunersystem nur die Ziffern 0..8 gibt, die dezimale '9' eintspricht '10' im Neunersystem (1*9^1 + 0*9^0 = 10 [9er]).)

Gast
2004-07-10, 21:34:27
Original geschrieben von BubbleBoy
Ächts, wenn du das so verstehst, daß das beides unterschiedliche Zahlen sind und sich nur in Bezug auf ihr jeweiliges Zahlensystem gleichen, dann ja. Muß mich hier aber auch nochmal korrigieren (s.u.).

Richtig, da wird ein Wurm drinne sein. Würde mitlerweile sagen, daß es richtig so lauten müßte:

9^387.420.489 [dez] = 10^1.000.000.000 [9er]

(Es ist auch zu beachten, daß es im Neunersystem nur die Ziffern 0..8 gibt, die dezimale '9' eintspricht '10' im Neunersystem (1*9^1 + 0*9^0 = 10 [9er]).)
nich 10^10.000.000.000? aber soweit hatt ichs auch grad rausgefunden dass es 10^387420489 ned sein kann :)
so langsam check ichs glaub ich :)

BubbleBoy
2004-07-10, 21:57:28
Original geschrieben von Gast
nich 10^10.000.000.000?

Naja, da 9^9 [dez] im Neunersys. eine '1' mit neun Nullen sein sollte, wäre meine 10^1.000.000.000 schon richtig :).

govou
2004-07-11, 01:51:25
Original geschrieben von BubbleBoy
Naja, da 9^9 [dez] im Neunersys. eine '1' mit neun Nullen sein sollte, wäre meine 10^1.000.000.000 schon richtig :).
Oder gleich eine "1" mit einer Milliarde Nullen. Ich wäre so frech und würde ein schwarzes Blatt Papier abliefern, wo oben links eine kleine 1 auf weißem Hintergrund steht. Von wegen "zählen sie nach" ;)

Gast
2004-07-11, 10:47:11
Original geschrieben von BubbleBoy
Naja, da 9^9 [dez] im Neunersys. eine '1' mit neun Nullen sein sollte, wäre meine 10^1.000.000.000 schon richtig :).
ich dachte weil 9^9^9 [dez] = 10^10^10 [9er]
und 10^10 is doch 10.000.000.000, also 10^10.000.000.000 oder?

BubbleBoy
2004-07-11, 12:18:03
Original geschrieben von Gast
ich dachte weil 9^9^9 [dez] = 10^10^10 [9er]
und 10^10 is doch 10.000.000.000, also 10^10.000.000.000 oder?
Nein, liegt an den unterschiedlichen Systemen.


Neunersystem
============

10^10 10^8 10^7 10^6 10^5 10^4 10^3 10^2 10^1 10^0
-----------------------------------------------------------
1 0 0 0 0 0 0 0 0 0


Wobei natürlich gilt, daß 9^9 [d] = 10^10 [9].

BubbleBoy
2004-07-11, 12:21:39
Original geschrieben von Beh
Oder gleich eine "1" mit einer Milliarde Nullen. Ich wäre so frech und würde ein schwarzes Blatt Papier abliefern, wo oben links eine kleine 1 auf weißem Hintergrund steht. Von wegen "zählen sie nach" ;)
Nein, "nur" 387420489 Nullen - aber das dürfte auch reichen ;D.
(Die 10^1.000.000.000 war im Neunersystem und entspricht der hier die ganze Zeit diskutierten 9^9^9 = 9^387420489 im Dezimalsystem.)

Wurde übrigens auch schon erwähnt: Du könntest dir auch das System zu Basis 9^387420489 nehmen. Dann bräuchtest du nur 10 auf das Blatt schreiben und die Sache wäre erledigt. ;D


Edit: Rechtschreibung ;(

mrdigital
2004-07-11, 12:31:58
@BubbleBoy: So wie du das formuliert hast, hatte ich das schon so verstanden, dass du 1234 (Basis10) in einem 9er System darstellen wolltest. ;)

@Gast: In einem neuner System gibt es die Ziffer "9" nicht! D.h. auf einer Stelle / Ziffer kannst du von 0..8 zählen. In einem 16er System kannst du auf einer Stelle von 0..15 zählen (dazu braucht man dann eben noch "neue" Zahlzeichen, üblicherweise nimmt man A..F, so dass man von 0..F zählen kann). Im Binärsystem kann man eben nur von 0..1 zählen.

BubbleBoy
2004-07-12, 19:35:44
Alles geklärt hier? :kratz2:


@threadstarter
Hast du die "Nummer" :D mitlerweile durchgezogen?

Gandharva
2004-07-12, 20:22:43
4.2812477317574704803698711593056352133905548224144351417475372305352388747173
504835319366529943203337506041753364763100078032613904733860832080206037470612
809165574132086446019861999614520310524428581489598115147194935176779655930215
939338501502396942623105296758165694333346314749255384948593377812087624957216
504195220601804571301517864051014594079041948663327336671830654410760234823633
427933884734491714907139283876367034707332216158426388470264465058580355824823
115778277866180114720994362906904734383664886646950233817353314932888115176124
859712015335756443987605995621733954850395053696554453295547762183338179903753
742986603617541076696090471833992393314534254702269833306512825870352073623634
333080916193999239914353995174262626192250444914889355346296338764247108036190
948328339353383268116816840967521737160227124038642410944863124167336163160258
473857727316993387556729418877537923876279151815197169574861839692092170993607
80264476440839592643445485180078094839593328539827016475025109538*10^369693099

BubbleBoy
2004-07-12, 20:36:12
Womit hast du das gerechnet? Wie groß ist die Warscheinlichkeit, daß diese ersten Stellen richtg sind?

mf_2
2004-07-12, 22:02:39
Hallo,
neun rechnet jetzt schon ca. 2 tage bei mir auf m 24/7 server (1.2 ghz ), kann aber noch n bisschen dauern bis es fertig ist.
Ich melde mich dann nochmal

BubbleBoy
2004-07-12, 23:45:06
Wie weit bist du?

threadstarter
2004-07-13, 13:31:11
weit kannst ja da noch ned sein mf_2... :freak2:
"neun" rechnet afais nich sehr schnell, ich hab ein andres programm das rechnet wesentlich schneller. allerdings kann es ned aus gespeicherten dateien wieder anfangen :freak2:
also ich hab heut mal die wette verfestigt, er hat sich gewunden wie ein wurm aber hat nich recht was genutzt weil er halt definitiv mit der wette angefangen hat und der restliche kurs ihn auch dran erinnert hat :D
allerdings soll ich jetz dem ganzen kurs ne kugel eis spendiern wenn ichs ned schaff... mal sehn was sich da noch raushandeln lässt :D
die neuner-system-nummer werd ich dann mal probiern; is is definitiv 10^1.000.000.000, was eine 1 mit 387420489 nullen is? dann werd ich ihm das mal erzählen :)
ahja noch was wichtiges: es hat nich zufällig wer einen mögichste schnellen 64bit-rechner rumstehn den er mal für 2-3 wochen opfern könnte dafür? das wäre anscheinend genial viel schneller weil sonst immer 64bit erst in 2x32bit umgerechent werden muss :)
@striper: sry, aber das hilft ned so recht weiter, sin etwas zu wenig stellen ;)
nehm mal an mit derive gerechnet oder?

BubbleBoy
2004-07-13, 13:46:34
Original geschrieben von threadstarter
die neuner-system-nummer werd ich dann mal probiern; is is definitiv 10^1.000.000.000, was eine 1 mit 387420489 nullen is? dann werd ich ihm das mal erzählen :)
Haben da ja in den vergangenen Tagen alle Umrechnungsfehler ausgemerzt, sollte also richtig sein. :)
Original geschrieben von threadstarter
ahja noch was wichtiges: es hat nich zufällig wer einen mögichste schnellen 64bit-rechner rumstehn den er mal für 2-3 wochen opfern könnte dafür? das wäre anscheinend genial viel schneller weil sonst immer 64bit erst in 2x32bit umgerechent werden muss :)
Erklär das mal etwas näher :) ...

Gast
2004-07-13, 15:37:11
Original geschrieben von BubbleBoy
Haben da ja in den vergangenen Tagen alle Umrechnungsfehler ausgemerzt, sollte also richtig sein. :)

Erklär das mal etwas näher :) ...
kann ich leider ned :D
hab ich nur gesagt bekommen ;)

BubbleBoy
2004-07-13, 16:25:13
Also ich wüßte im Moment keinen Grund, warum ein 64-Bit-Rechner signifikante Vorteile gegenüber einem 32-Bit-Rechner haben sollte (von zusätzlichen Registern, möglicherweise mehr Arbeitsspeicher und dem integrierten MC mal abgesehen).

Gast
2004-07-13, 21:06:32
wahrscheinlich ist das in ein paar jahren DER benchmark...
--> mein neuer rechn0r schafft 9^9^9 in 53sek :O :freak:

BubbleBoy
2004-07-13, 21:10:23
Original geschrieben von Gast
wahrscheinlich ist das in ein paar jahren DER benchmark...
--> mein neuer rechn0r schafft 9^9^9 in 53sek :O :freak:
:lolaway: ;D

mrdigital
2004-07-13, 21:39:58
Original geschrieben von BubbleBoy
Also ich wüßte im Moment keinen Grund, warum ein 64-Bit-Rechner signifikante Vorteile gegenüber einem 32-Bit-Rechner haben sollte (von zusätzlichen Registern, möglicherweise mehr Arbeitsspeicher und dem integrierten MC mal abgesehen).
Wesentlich schnellere Multiplikation....hier würde man ca Faktor 4 mit nem 64bitter gewinnen, ich finde das ist doch was ;)

BubbleBoy
2004-07-13, 21:59:18
Original geschrieben von mrdigital
Wesentlich schnellere Multiplikation....hier würde man ca Faktor 4 mit nem 64bitter gewinnen, ich finde das ist doch was ;)
Und welchen Teil der Zahl zerlegst du in die 64 Bit, damit die Multiplikationen schneller ausgeführt werden?
Hängt also stark vom verwendeten Datentyp und Programm ab.

Gandharva
2004-07-13, 22:07:47
Original geschrieben von BubbleBoy
Womit hast du das gerechnet? Wie groß ist die Warscheinlichkeit, daß diese ersten Stellen richtg sind?

mit mathematica auf 1000 stellen genau. wie viele stellen hat die zahl nochmal ca.?

bei mir scheiterts nur am ram. wenn ich aber mal 50gb als auslagerungsdatei einstelle, könnts klappen.

mrdigital
2004-07-13, 22:14:14
Original geschrieben von BubbleBoy
Und welchen Teil der Zahl zerlegst du in die 64 Bit, damit die Multiplikationen schneller ausgeführt werden?
Hängt also stark vom verwendeten Datentyp und Programm ab.
das 64bitter nicht per se das schneller machen ist mir klar, aber wenn ich ein BigNum Problem lösen will, dann passe ich meine Datentypen an die Problemstellung an und mache mir Gedanken über meine Architektur. Ich habe das auch machen müssen als ich einen RSA Algo auf nem 16bitter implementiert hab, da musste auch sehr grosse Zahlen multiplizieren, wofür es keine "Standartdatentypen" gibt.

HellHorse
2004-07-19, 15:04:27
Ok, anstatt was Sinnvolles zu machen, habe ich weiter daran gebastelt ;)

Was ist neu:

abschaltbare "Fortschrittsanzeige" (bringt nicht viel, da es ab 9^(2^26) verdammt lange geht)
multithreaded Version
optimierte Version, die r (siehe hier (http://www.forum-3dcenter.org/vbulletin/showthread.php?s=&postid=1983457#post1983457)), getrennt berechnet und dadurch schneller ist (siehe weiter unten)
pyunit Tests die erfolgreich sind (um mich zu überzeugen, dass der Scheiss läuft)
benchmark Möglichkeit


Allgeimeine Notiz:
Python 2.3 ist _viel_ schneller als python 2.2

verbose = True

def info(message):
if verbose: print message

def to_boolean_list(number):
if number < 0:
raise Exception, "number below 0"
boollist = []
while number:
div, rest = divmod(number, 2)
boollist.append(rest)
number = div
return boollist

def biggest_power_of_2(border):
exp = 0
current = 1
while current < border:
exp = exp + 1
current = current * 2
if current == border:
return exp
else:
return exp - 1

def ones(boollist):
count = 0
for next in boollist:
if next:
count = count + 1
return count

def write_to_file(n, filename='9pow9pow9.txt', timeMessage=None):
conservion_timer = Timer()
conservion_timer.start()
info("converting")
s = str(n)
conservion_timer.stop()
info("conversion done, time used: %s" % conservion_timer)

info("writing to file")
f = open(filename, 'w')
f.write("amount of places: %s \n" % len(s))
f.write(s)
if timeMessage:
f.write("\ntime used: %s" % timeMessage)
f.close()
info("done")

class PythonPowerComputer:
def power(self, base, exp):
return base ** exp

class OptimizedMultPowerComputer:
def power(self, base, exp):
biggest_power = biggest_power_of_2(exp)
rest = to_boolean_list(exp - (2 ** biggest_power))
rest.extend((biggest_power - len(rest) + 1) * [False])
saved = []
local_timer = Timer()
local_timer.start()

n = base
if rest[0]:
saved.append(base)

info("staring run 1")

for i in xrange(1, biggest_power + 1):
n = n * n
if rest[i]:
saved.append(n)
info("%05.2f %s" % (100.0 * i / biggest_power, "% done"))

local_timer.stop()
info("run 1 done, time used: %s \n" % local_timer)
local_timer.reset()
local_timer.start()
info("starting run2")

r = 1
for i in xrange(len(saved)):
r = r * saved[i]
info("%05.2f %s" % (100.0 * (i + 1) / len(saved), "% done"))

local_timer.stop()
info("run 2 done, time used: %s" % local_timer)
local_timer.reset()
local_timer.start()
info ("doing last big muliplication")
n = n * r
local_timer.stop()
info ("last muliplication done, time used: %s" % local_timer)
return n

from threading import Lock
from threading import Condition
from threading import Thread

class ConcurrentPowerComputer:

def power(self, base, exp):
biggest_power = biggest_power_of_2(exp)
rest = to_boolean_list(exp - 2**biggest_power)
rest.extend((biggest_power - len(rest) + 1) * [False])
lock = Lock()
signal = Condition(lock)
max = ones(rest)
saved = []
restcomputer = RestComputer(signal, max, saved)
restthread = Thread(target=restcomputer.run, name="rest-computer-thread")

n = base
if rest[0]:
saved.append(base)

restthread.start()

for i in xrange(1, biggest_power + 1):
n = n * n
if rest[i]:
signal.acquire()
saved.append(n)
signal.notify()
signal.release()
info("main-thread: %05.2f %s" % (100.0 * i / biggest_power, "% done"))

restthread.join()
info("doing last muliplication")
n = n * restcomputer.result

info("done")
return n

class RestComputer:
def __init__(self, signal, max, numbers):
self.signal = signal
self.numbers = numbers
self.max = max

def run(self):
r = 1
processed = 0
while processed < self.max:
self.signal.acquire()
if len(self.numbers) <= processed:
self.signal.wait()
next = self.numbers[processed]
self.signal.release()
r = r * next
processed = processed + 1
info("helper-thread: %05.2f %s" % (100.0 * processed / self.max, "% done"))
info("helper-thread done")
self.result = r

class PythonMultiplier:
def mult(self, a, b):
return a * b

from time import time
def bench():
globals()["verbose"] = False
base = 9
exp = 5000000
opt_mult_computer = OptimizedMultPowerComputer()
concurrent_computer = ConcurrentPowerComputer()

start_time = time()
python_result = base**exp
end_time = time()
python_time = end_time - start_time

start_time = time()
optmult_result = opt_mult_computer.power(base, exp)
end_time = time()
optmult_time = end_time - start_time

start_time = time()
concurrent_result = concurrent_computer.power(base, exp)
end_time = time()
concurrent_time = end_time - start_time


print "time for python power: %s seconds" % python_time
print "time for optimized multiplication power: %s seconds" % optmult_time
print "time for concurrent multiplication power: %s seconds" % concurrent_time
if python_result == optmult_result:
print "optimized multiplication power was correct"
else:
print "optimized multiplication power was incorrect"
if python_result == concurrent_result:
print "concurrent multiplication power was correct"
else:
print "concurrent multiplication power was incorrect"

from datetime import timedelta

class Timer:
def __init__(self):
self.reset()

def start(self):
self.starttime = time()

def stop(self):
self.stoptime = time()

def reset(self):
self.starttime = 0
self.stoptime = 0

def __str__(self):
diff_seconds = self.stoptime - self.starttime
diff_delta = timedelta(seconds=diff_seconds)
minutes, seconds = divmod(diff_delta.seconds, 60)
hours, minutes = divmod(minutes, 60)
buff = ""
if diff_delta.days:
if diffdelta - 1:
buff = "%s days " % diff_delta.days
else:
buff = "1 day "
if hours:
if hours - 1:
buff = "%s%s hours " % (buff, hours)
else:
buff = "%s 1 hour " % buff
if minutes:
if minutes - 1:
buff = "%s%s minutes " % (buff, minutes)
else:
buff = "%s1 minute " % buff
if seconds:
if seconds - 1:
buff = "%s%s seconds" % (buff, seconds)
else:
buff = "%s1 second" % buff
if not buff:
buff = "less than 1 second"
return buff

import unittest
class PythonPowerTest(unittest.TestCase):
def setUp(self):
self.computer = PythonPowerComputer()

def test9pow9(self):
n = self.computer.power(9, 9)
self.assertEqual(n, 9**9)

def test12pow12(self):
n = self.computer.power(12, 12)
self.assertEqual(n, 12**12)

def test2pow100000(self):
n = self.computer.power(2, 100000)
self.assertEqual(n, 2**100000)

def test9pow57831(self):
n = self.computer.power(9, 57831)
self.assertEqual(n, 9**57831)

class MultPowerTest(PythonPowerTest):
def setUp(self):
self.computer = MultPowerComputer()

class ConcurrentPowerTest(PythonPowerTest):
def setUp(self):
self.computer = ConcurrentPowerComputer()

class OptimizedMultPowerTest(PythonPowerTest):
def setUp(self):
self.computer = OptimizedMultPowerComputer()

def test():
globals()["verbose"] = False
del argv[-1]
unittest.main()

def run(concurrent):
if concurrent:
computer = ConcurrentPowerComputer()
else:
computer = OptimizedMultPowerComputer()
global_timer = Timer()
global_timer.start()
exp = 9**9
base = 9
n = computer.power(base, exp)
global_timer.stop()
write_to_file(n, "neun.txt", global_timer)

def usage():
print """-t to test
-b to bench
-c concurrent
-n normal, default"""

if __name__ == "__main__":
from sys import argv
if len(argv) > 2:
usage()
elif "-b" in argv:
bench()
elif "-c" in argv:
run(True)
elif ("-n" in argv) or (len(argv) == 1):
run(False)
elif "-t" in argv:
test()
else:
usage()

Es gibt folgende optionen

-b für's benchen
-t für's testen
-c berechnet 9^(9^9) im normalen Modus
-n berechnet 9^(9^9) im multithread Modus, default


Und noch ein kleiner Benchmark :D
Zeit zur Benechung von 9^5000000 (5 Millionen)
http://web.green.ch/marschall/pics/9mark.png
Beobachtungen:

Multithreading bringt wie nicht anders zu erwarten auf single CPU Systemen keine Verbesserung, auch nicht mit HTT. In diesem Fall aber zum Glück auch keine Verschlechterung.
Der P4 braucht unter Windows etwa 55% länger als der Athlon mit gleicher python Version (fand im BIOS die Option nicht, um HTT abzuschalten). Die Auslastung für jede der beiden virtuellen CP's schwankte immer um die 50% Prozent.
der Athlon profitiert minimal vom Umstieg auf Linux, währed der P4 dadruch schneller als der Athlon wird
Die optimierte und die multithread Version sind praktisch gleich schnell wie wenn python es selbst macht.


Wenn jemand ein 2 CPU System, Zeit und Lust hat, wäre ich sehr an Vergleichsdaten interessiert.

update:
knoppix Werte hinzugefügt

mrdigital
2004-07-19, 15:55:53
WOW das der Athlon hier so gut gegen den P4 anstinken kann hätte ich nicht gedacht...

littlejam
2004-07-19, 17:04:49
Stell mal eine bench und nicht-bench Version online. Für die (=ich) die kein Python haben.

Gruß

HellHorse
2004-07-19, 17:10:30
Original geschrieben von mrdigital
WOW das der Athlon hier so gut gegen den P4 anstinken kann hätte ich nicht gedacht...
Liegt entweder an Windows oder der Windows Version von python.
Habe die Knoppix Werte hinzugefügt und da ist er minimal schneller als der Athlon.

HellHorse
2004-07-19, 18:20:15
Original geschrieben von littlejam
Stell mal eine bench und nicht-bench Version online. Für die (=ich) die kein Python haben.

Gruß
Habs gerade ein bisschen vereinfacht. Ohne python geht's leider nicht:( Dafür ist es mit python trotzdem einfach :)

Ich gehe mal davon aus, du hast Windows
Python kriegst du hier (http://python.org/download/). Das lässt sich ganz normal installieren, wie ein Programm.
Dann erstellst du irgend einem Verzeichnis eine Datei mit der Endung .py (z.b neun.py). Als Inhalt fügst du meinen Code ein.
Denn wechselst du in der Kommandozeile in das Verzeichnis wo du die Datei erstellt hast.
Dann gibst du den Namen der Datei ein, gefolgt von einem Leerschlag und -b und drückst Enter. Also z.B:
neun.py -b
Das Ganze kann einen Moment dauern. Beim P4 waren es z.B ungefähr 10 Minuten. Während dieser Zeit wird nichts angezeigt.

littlejam
2004-07-20, 16:12:31
Löft gut :)

Benchmarks(HT on, P4 2,8GHz/800FSB)
python 139,2s
multiplication power 156,4s
concurrent multiplication power 139,2s
optimized multiplication power 139,2s

*edit
Mit ohne (;D) HT läufts fast genauso, ca. 1 Sekunde langsamer.

Gruß

HellHorse
2004-07-20, 19:54:02
Danke, ich nehme mal an, du hast Windows. Dann würden sich die Werte ins Gesamtbild einfügen und meine Messungen bestätigen.
Irgend etwas an python, Windows und P4 mag sich nicht...

Habe auch probiert in Java 9^5000000 zu berechnen. Quick and Dirty Code ohne repeated squaring.

public class Neun {
public static void main(String[] args) {
BigInteger nine = new BigInteger("9");
long starttime = System.currentTimeMillis();
BigInteger result = nine.pow(5000000);
long endtime = System.currentTimeMillis();
double usedtime = (endtime - starttime) / 1000.0;
System.out.println("used time: " + usedtime + " seconds");
}
}

und hatte etwa 40 min. :(

Schritt 1 (9^(2^28) berechnen und das Speichern der Zwischenresultate) braucht etwa 15 Stunden.
Schritt 2 (Berechnung des letzten Faktors) dauert etwa 3 Studen. Jetzt fehlt noch die letzte Muliplikation...

littlejam
2004-07-21, 08:58:04
Hm 2 Cpu System ist ja kein Problem, nur will ich da kein Python installieren :(
Ich bräuchte ne exe dann würd ichs mal probieren.
Bin zwar in c/c++ ein wenig bewandert, aber Multithreading und so große Zahlen beherrsche ich dann doch nicht.

Ach ja ist n WinXP gewesen.

Gruß

Freakazoid
2004-07-26, 17:01:52
ist irgendwie in vergessenheit geraten
wartet, ich schiebs mal nac oben
*push*

HellHorse
2004-07-26, 17:40:23
Ich habe meinen Code mal auf einem Celeron 1.2 und Linux (siehe Diagramm) laufen lassen, mit folgendem Ergebnis:

15 h für den ersten Schritt
3 h für den zweiten Schritt
20 h für die letzte Multiplikation

Die guten Nachrichten:
Die Zahl lässt sich in zwei Tagen brechenen.
Der Speicherverbrauch pendelt sich bei etwa 256 MB ein, übersteigt diesen Wert aber auch nicht.

Die schlechten Nachrichten:
Die Konservion einen String (s = str(n)) war auch nach zwei Tagen nicht fertig und so sah ich mich gezwungen abzubrechen. Ich kann also nicht sagen, wie die Zahl aussieht.
Das Potential für Parallelisierung bei meiner Version ist gering.
Ersetzen der Multiplikation mit Shifts und Additionen ist viel langsamer, allerdings ist der entsprchende Code noch nicht ganz fertig optimiert.
Alle anderen von getesteten Implementationen (Scheme, Smalltalk, Java) scheinen viel länger zu brauchen. Ich verwendete allerdings nirgends repeated squaring.

Änderungen, die ich noch am Code voregenommen habe:
ein Fix in der Fortschrittsanzeige
explizite Zeitmessung für die einzelnen Schritte
python 2.4 aplha1 für Windows hinzugefügt
alte Version gekickt

HellHorse
2004-08-16, 16:12:20
Scheme hat einfach nach einem zweiten Versuch geschriehen. Also habe ich den python Code mehr oder weniger 1:1 portiert. Und siehe da statt 145s mit python für 9^5000000 sind es noch 23s.

Die Scheme Implentierung ist drscheme (gibt schnellere) und das System ist der Celeron 1.2 GHz.


(define (^ base exp)
(power-t base exp 1))

(define (power-t base exp rest)
(cond ((zero? exp) 1)
((= 1 exp) (* base rest))
(else
(power-t base (- exp 1) (* base rest))
)))

(define (divmod x y)
(let* (
(mod (modulo x y))
(div (/ (- x mod) y)))
(cons div mod)))

(define (to-boolean-list x l)
(if (zero? x)
l
(let (
(y (divmod x 2)))
(to-boolean-list (car y) (append l (list
(not (zero? (cdr y)))
)))
)))

(define (biggest-power-of-2 x)
(biggest-power-h 1 0 x))

(define (biggest-power-h current exp border)
(cond
((eq? current border) exp)
((> current border) (- exp 1))
(else
(biggest-power-h (* current 2) (+ exp 1) border)
)))

(define (extend l target-length value)
(if (>= (length l) target-length)
l
(extend (append l (list value)) target-length value)))

(define (power-r base exp)
(let* (
(biggest-power (biggest-power-of-2 exp))
(should-save-t (to-boolean-list (- exp (^ 2 biggest-power)) '()))
(should-save (extend should-save-t (+ biggest-power 1) #f))
(saved (if (car should-save)
(list base)
'())))
(step-1 base biggest-power (cdr should-save) saved)
))

(define (step-1 acc steps should-save saved)
(if (zero? steps)
(step-2 acc saved)
(let (
(next-acc (* acc acc))
(save-this? (car should-save)))
(step-1 next-acc (- steps 1) (cdr should-save) (if
save-this?
(append saved (list next-acc))
saved))
)))

(define (step-2 acc saved)
(* acc (apply * saved)))

(define result #f)
(define (bench)
(time
(set! result (power-r 9 5000000))))

Ja, alle rekursive Funktionsaufrufe sind tail-rekursiv und alle Scheme Implementierungen müssen sie wegoptimieren.

Jetzt fehlt noch die "Fortschritssanzeige" und der Fileoutput.

Gast
2004-08-17, 18:38:44
Die Konservion einen String (s = str(n)) war auch nach zwei Tagen nicht fertig (Bug?) und so sah ich mich gezwungen abzubrechen. Ich kann also nicht sagen, wie die Zahl aussieht.

Zum Konvertieren ins Dezimalsystem werden sehr viele zeitaufwändige Divisionen gebraucht.

HellHorse
2004-08-17, 19:15:53
Zum Konvertieren ins Dezimalsystem werden sehr viele zeitaufwändige Divisionen gebraucht.
So siehts leider aus. Bei 9^500000 nimmt die Konversion bedeutend mehr Zeit in Anspruch als das ausrechnen. Von daher ist das grössere Problem 9^(9^9) als String darzustellen.

PrakashKC
2004-08-18, 00:13:22
Ich glaube ich habe eine recht schnelle Methode gefunden, um die Zahl auszurechnen, die nur mit Summation auskommt:

Sei n=9^9

Wir wollen 9^n ausrechnen. Ich schreibe das als (10-1)^n und benutzte die Formel für Binomialreihe:

(10-1)^n=\Sum_k=0^n (n über k) 10^k (-1)^(n-k)

Es müssen also "nur" 9^9 Faktoren addiert werden. Das Problem reduziert sich im wesentlichen darauf (n über k) zu bestimmen, den der Rest ist trivial. Nun im ersten Semester Mathe lernt man, daß (n über k) sich über das Pascal'sche Dreieck berechnen läßt. WIeder nur Summation. Mittles Gaußscher Summenformel können wir den Aufwand abschätzen, wenn wir annehmen, daß die eine SUmmenbildung in O(1) ausgeführt werden kann (was natürlich nicht stimmt.): n*(n+1)/2, also O(n^2). Realistischer kann man annehmen, daß die Summation in Zeit O(n) ausgeführt wird, dann haben wir O(n^3).

Das Problem ist nur, daß wir ziemlich viele Faktoren uns merken müssen, nämlich n Faktoren. So geht das nciht gut... Ich denke aber, daß wir es auch mit nur einigen wenigen Faktoren hinbekommen, beim Pascallschen Dreicke und der Anwendung der Summe, wenn man das Dreieck so DFS-like berechnet statt Ebene für Ebene.

Alles verstanden? :D Wenn doch, sollte jemand einen schnellen Alg schreiben können. Ich habe leider erst im Oktober Zeit, mich hieran zu versuchen.

Nur denke ich, daß die 9^9 Passes durch die Zahl (sei es im Dreieck oder Aussummieren des Ergebnisses) zuviel Zeit kosten werden, wenn man das nicht im RAM erledigen kann. Wenn man mit der Festplatte arbeitet und für jeden Pass 1 Minute veranschlagt, sind 9^9 Minuten doch etwas viel Zeit...

Hmm, selbst wenn ein Pass 1 sec bracuht, bräuchte man 12 Jahre, wenn ich richtig gerechnet habe... Schade eigentlich. :(

HellHorse
2004-08-18, 12:52:23
Hmm?

(define fac-n 1)

(define (fac n)
(fac-h n 1))

(define (fac-h n acc)
(if (zero? n)
acc
(fac-h (- n 1) (* n acc))
))

(define (binom-coeff n k)
(if (or
(zero? k)
(eq? n k))
1
(/ fac-n (* (fac k) (fac (- n k))))
))

(define (power-9 n)
(set! fac-n (fac n))
(sum-10 n (- n 1) 1 (if (even? n)
1
-1)))

(define (sum-10 n k last-factor acc)
(let (
(next-factor (* 10 last-factor)))
(cond
((zero? k) (+ acc next-factor))
((even? k)
(sum-10 n (- k 1) next-factor (+ acc (* (binom-coeff n k) next-factor))))
(else (sum-10 n (- k 1) next-factor (- acc (* (binom-coeff n k) next-factor))))
)))

(define result #f)
(define (bench)
(time
(set! result (power-9 2000))))

Ist weit davon entfernt perfekt zu sein. So wird z.B. (n über k) und (n über (n - k)) berechnet.
Aber selbst wenn die die Zeit theoretsich halbiert, ist es immer noch viel langsamer.
Für 9^2000

cpu time: 85070 real time: 96188 gc time: 52453

(Angaben in Millisektunden)
Insbesondere geht verdammt viel Zeit für garbage collection drauf. Die andere Lösung von mir hat selbst bei 9^5000000 gc time: 0.

PrakashKC
2004-08-19, 23:21:17
Da ich aus deinem code nciht schlau werde (Java? Kenn ich nücht..). Machst du das direkt oder übr Summation, wie beschrieben? Ich bin am überlegen, ob man das auch direkt schneller hinbekommen könnte, aber bin mir nicht sicher.

(n über k) ist ja auch n!/ ((n-k)!* k!) und Fakultäten sind ja bekanntlich sehr häßlich.... Ausgeschrieben muß man allerdings "nur"

(n über k) = (n*(n-1)*(n-2)*..*(n-k+1))/k! rechnen.

Naja ich denke am schnellsten wird doch die direkteste multiplikative Methode sein. Da muß man 36 Multiplikationen ausführen, um an das Ziel zu kommen:

9^3*9^3*9^3 =9^9
Damit:
9^9*9^9*9^9 = 9^27
damit:
9^27*9^27*9^27 = 9^81

und noch weitere 15 Mal.

etc bis man 9^(9^9) hat. So muß man nur pro Schritt 2 große Zahlen + aktuelles Ergebnis auf Platte bzw im SPeicher halten, also wenn man pro byte nur eine Ziffer benuzt, bräuchte man etwas mehr als 1GB Speicher. Schlauer kodiert könnte man ein nibble für eine Ziffer benutzen, also bcd Kodierung und es paßt sicher in den Speicher. Wenn man assembler kann, kann man sogar mit bcd direkt rechnen...

Hmm, habe mir mal gerade überlegt, daß man so ziemlich genau >0.3 bis 0.5*n^2 mit n=9^9,also insgesamt etwa 0.4*9^18 durch die Zahlenkolonne muß, wenn man nach Schulmethode multiplitziert (n^2 Aufwand). DAs dauert wohl auch seeeehr lange, sogar mehr als oben??? Mann, schon spät, Hirn will nciht mehr. ;)

(Hintergrund: Wir wissen, ja daß sich mit jeder Mult. die Stellen schlimmstenfalls verdoppeln. Wir gehen davon aus, daß das Endergebnis 9^9=n Stellen hat. In dem Schema oben muß also im letzten Schritt eine zahl^3 genommen werde, die n/3 Stellen hat. Das Zwsichenergebnis hat 2*n/3 Stellen, dh. es muß n/3 * n/3 +2*n/3 *n/3 = = 0.333*n^2)

Gehen wir also von 10^16 Dutchgängen aus, mit 1sec/Durchgang (seeehr optimistisch :D) Das werden doch etwas zuviel Jahre sein, die es brauchen wird... DA erscheint mir das Summationsschema doch vielversprechender...und das braucht schon lange...

Habe ich mich verschätzt?

HellHorse
2004-08-20, 00:50:43
Da ich aus deinem code nciht schlau werde (Java? Kenn ich nücht..).
:biggrin: nee Klammernwald -> LISP. Konkret ist es Scheme (habe ich eigentlich geschrieben).

Machst du das direkt oder übr Summation, wie beschrieben? Ich bin am überlegen, ob man das auch direkt schneller hinbekommen könnte, aber bin mir nicht sicher.
Ja es ist einfach Summation der Glieder der Binomialreihe. Allerdings mit ein paar kleineren Optimierungen. Es wird nicht (-1)^k gerechnet, sondern geschaut ob k ungerade ist und in diesem Fall des Glied von der Teilsumme subtrahiert, sonst addiert. Auch wird nicht 10^(n-k) gerechnet, sondern der letzte Wert von 10^x mit 10 multipliziert.

(n über k) ist ja auch n!/ ((n-k)!* k!) und Fakultäten sind ja bekanntlich sehr häßlich.... Ausgeschrieben muß man allerdings "nur"

(n über k) = (n*(n-1)*(n-2)*..*(n-k+1))/k! rechnen.
Im Moment berchene ich (n über k) direkt d.h n!/(k!*(n-k)!) allerdings berechne ich n! nur einmal, das es nie ändert. Von da her glaube ich, dass es schneller ist, müsste es aber mal ausprobieren.
Zudem berchene ich sowohl (n über k) wie (n über (n - k)) obwohl sie gleich sind.

Naja ich denke am schnellsten wird doch die direkteste multiplikative Methode sein. Da muß man 36 Multiplikationen ausführen, um an das Ziel zu kommen:

9^3*9^3*9^3 =9^9
Damit:
9^9*9^9*9^9 = 9^27
damit:
9^27*9^27*9^27 = 9^81

und noch weitere 15 Mal.

Repeated squaring:
http://www.forum-3dcenter.org/vbulletin/showpost.php?p=1983457&postcount=180
28 Muliplikationen von denen die letzten lange gehen. Etwa 15 (IIRC) die recht schnell gehen und eine grosse, die länger als die ersten 28 dauert.


Habe ich mich verschätzt?

Speicherverbrauch während dem ausrechnen sollte kein Problem sein. Meine python Methode brauchte etwa 256 MB.
Das Problem bei der bionmial Methode ist aus meiner Sicht, die vielen Glieder die weggeschmissen werden müssen. Zumindest bei meiner Version und drscheme kostet das mehr Zeit als das eigentliche Ausrechenen.
Zeit zum Ausrechnen ist nicht wirklich ein Problem. Mein popeliger Celeron 1.2 GHz hatte es in zwei Tagen, die scheme Version ist vermutlich schneller.
Das wirkliche Problem ist die ausgerechnete Zahl in einen String zu konvertieren um in sie ein File zu schreiben. Das wird auch den Speicherverbrauch in die Höhe treiben.

Auf der positiven Seite:
die binomial Methode eignet sich gut zur Parallelisierung

PrakashKC
2004-08-20, 10:46:45
* Das wirkliche Problem ist die ausgerechnete Zahl in einen String zu konvertieren um in sie ein File zu schreiben. Das wird auch den Speicherverbrauch in die Höhe treiben.


Ach du rechnest binär? Naja, dann ist Speicher kein Problem (eta 100MB für die Zahl, nehme ich mal an), aber bei der Umwandlung mußt du in der Tat ja mind. drei große Zahlen im Speicher haben. Vorteil wäre aber, daß du hier nur #"benötigter bit" Mal durch die große string Zahl gehen müßtest. Hmm, klingt eigentlich danach, daß es zu packen wäre. (edit) Ach ich Trottel, #"benötigter bit" ist doch sehr groß (nämlich so ziemlich 9^9 :D) also wird das Problem nicht wirklich kleiner...

Hast du mit deinem Schema 9^9^9 nun komplett ausgerechnet und es hat nur 2 Tage gebraucht? Binär oder Dezimalergebnis?

Ach, wenn man binär rechnet, und es binomial machen möchte, sollte man evtl eher (8+1)^(9^9) betrachten...

HellHorse
2004-08-20, 11:17:37
Ach du rechnest binär?
Nöö dezimal, warum?


Hast du mit deinem Schema 9^9^9 nun komplett ausgerechnet und es hat nur 2 Tage gebraucht? Binär oder Dezimalergebnis?
Dezimal. Aber nur im Speicher, nicht ein einem File.

Steht eigentlich alles hier:
http://www.forum-3dcenter.org/vbulletin/showpost.php?p=2060332&postcount=332

PrakashKC
2004-08-20, 11:59:33
# Die Konservion einen String (s = str(n)) war auch nach zwei Tagen nicht fertig und so sah ich mich gezwungen abzubrechen. Ich kann also nicht sagen, wie die Zahl aussieht.

Wenn du doch dezimal rechnest, dann mußt du doch nciht konvertieren, oder? Also rechnest du doch binär, oder habe ich etwas nciht verstanden? :confused:

HellHorse
2004-08-20, 12:14:50
Sicher muss ich es konvertieren, um es in ein File zu schreiben.

write(str)
Write a string to the file. There is no return value. Due to buffering, the string may not actually show up in the file until the flush() or close() method is called.

http://docs.python.org/lib/bltin-file-objects.html
Ob das intern wie in Scheme oder explizit wie in python geschieht, macht keinen Unterschied. Es muss trotzdem gemacht werden.

Beispiel:
Du hast einen integer mit dem Wert 123. Wenn du den einfach so ein ein File schreibst ist dort vermutlich (falls die Sprache nicht automatisch konvertiert) bloss ein character mit dem ASCII Wert 123. Das ist aber nicht was wir sollen. Wir wollen nämlich die 3 characters '1', '2' und '3'. Ergo müssten wir den integer in einen String kovertieren.

PrakashKC
2004-08-20, 12:50:21
Tja, dann hast du mich nciht verstanden. Dann rechnest du binär. :)

Wenn du nämlich im String (also dezimal) rechnest, brauchst du die Konversion nciht, bzw mußt nur trivial konvertieren, dh. wen du etwa ein byte pro Ziffer benutzt und die Werte 0-9 für die Ziffer verwendest, muß man bei Schreiben nur den byte-Wert+acsii-Wert(0) schreiben für jede Ziffer. Wenn man dagegen binär rechnet, muß man von Zahlen zur Basis 2 zur Basis 10 wechseln.

So wird etwa die Zahl 16 als int (also binär) wie du ja weißt als 0001 0000 gespeichert und muß erst in die augenfreundliche 16 umgerechnet werden. Das entfällt größtenteils, wenn du die Zahl binär etwa so speicherst: 0000 0001 0000 0110, also "dezimal" bzw im "verschwenderischen" bcd Format speicherst. Das ist ja sehr einfach umzuwandeln. Und geht in einem Durchgang (O(n)). Bei deiner Speicehrweise mußt du ja erst mal die 2er Potenzen bestimmen und immer gucken, ob die in deinem Ergebnis enthalten sind und die enthaltenen aufsummieren. <=viel Arbeit (O(n^2))

Darauf wollte ich letztendlich hinaus. Die Konvertierung von Baiss 2 nach 10 ist ja letztlich genauso schwierig, wie das Problem an sich, weswegen deine Lösung (binär) nur die Halbe Miete ist. Ein Scherzkeks gab ja die Lösung zur Basis 9 bereits an...

HellHorse
2004-08-20, 16:32:13
Jetzt sehe ich, was du meinst.
edit:
Eigentlich habe ich keine Ahnung wie jenseits von 32 resp. 64 bit gerechnet wird. Ich vermute mal es ist binär. Da ich faul bin, habe ich einfach die eingebauten Datentypen verwendet.

PrakashKC
2004-08-21, 00:40:43
Tja, ich habe mal angefangen das in c++ zu koden, aber wird wohl zu lange dauern, darum verschiebe ich das doch. Besonders auf Division habe ich keinen Bock, da ich schon genug Probleme mit der einfachen Addition habe...

HellHorse
2004-08-24, 09:49:20
Wenn ich das ganze so durchdenke, läuft es darauf hinaus, dass man eigentlich nach jeder Multiplikation eine Konversion ins Dezimalsystem macht. Anstatt nur am Ende. Dadruch gewinnen wir nichts, im Gegenteil.
Habe ich einen Denkfehler gemacht?

Arithmos
2004-08-24, 13:09:24
Hallo,

ich bin zufällig über diese Diskussion gestolpert und denke, dass ich vielleicht beim Konvertieren der Zahl ins Dezimalsystem helfen kann. Ich habe eine C++-Bibliothek zum Rechnen mit großen Zahlen geschrieben und habe die Konvertierung in einen String folgendermaßen deutlich beschleunigt (kleiner, leicht modifizierter Quelltextausschnitt):
// base ist die Zahlbasis zur Ausgabe; baseMinusOne ist die interne Zahlbasis minus 1 (auf 32-Bit-Systemen: 2^32-1)

// statt n mod base wird n mod base^x betrachtet, sodass n <= N::baseMinusOne und somit in ein N::digit (= Datentyp für ein Prozessorregister) passt
// dadurch erspart man sich viele Divisionen mit N (= die Klasse für die großen Zahlen)
ulong maxAccumulatedDigits = ulong(log((double)baseMinusOne)/log((double)base));
digit base_k = power(base, maxAccumulatedDigits);
assert(base_k > 1);

string s;
digit d;
N n, nn = *this;
do {
div_mod(nn, base_k, n, d); // n = nn / base_k; d = nn % base_k;
if (n.isZero())
break;
for (ulong i = 0; i < maxAccumulatedDigits; ++i) {
s += digit2char(d % base);
d /= base;
}
nn = n;
} while (true);
do { // bei letzter Ziffer keine führenden Nullen!
s += digit2char(d % base);
d /= base;
} while (d != 0);

reverse(s.begin(), s.end());

BubbleBoy
2004-08-24, 13:42:12
Ein Scherzkeks gab ja die Lösung zur Basis 9 bereits an...
:uconf3:
Zügel deine Ausdrucksweise mal bitte etwas und lies dir ggf. nochmal durch, aufgrund welcher Problematik dieser Thread entstanden ist. Deshalb ist die Angabe des Ergebnisses zur Basis 9 kein Scherz sondern die korrekte Lösung des Ursprungsproblems.

PrakashKC
2004-08-25, 00:14:32
Naja, aber sonderlich schwierig war die ja nicht anzugeben. ;)

10^10^10 kann man wohl auch leicht angeben im Dezimalsystem, oder?

Reagierst etwas allergisch, was?

@Hellhorse

Wie man es sieht. Letztendlich läuft es daraufhin hinaus eine Recheneinheit zu simulieren, die im Dezimalsystem arbeitet. Addieren kannst du zum Bsp. ohne große Konversion durchführen, kannst ganz normal mit einem carry arbeiten -so wie es binär auch geschieht - nur daß du ihn bei >9 auf 1 setzt.

BubbleBoy
2004-08-25, 14:15:37
Naja, aber sonderlich schwierig war die ja nicht anzugeben. ;)

10^10^10 kann man wohl auch leicht angeben im Dezimalsystem, oder?

Reagierst etwas allergisch, was?
Stimmt schon, daß das nicht schwierig war, aber es war die korrekte Lösung des gestellten Problemes (was wohl aus der Wette geworden ist?). Die Lösung stammte nicht von mir, ich habe nur die Zahl generieren lassen aber sonst auch einige Stunden der dezimalen Darstellung gewidmet.

Allergiker bin ich nicht, nur mißfällt mir die Formulierung "Scherzkeks" in diesem Zusammenhang.

:)

PrakashKC
2004-08-25, 14:17:10
Naja, als Mathematiker findet man so eine Lösung schon belustigend, insofern dachte ich, der, der die angegeben hatte, wollte einen joke reißen, von daher Scherzkeks. ;)

Threadstarter
2004-08-25, 16:05:36
was wohl aus der Wette geworden ist?
sind grad sommerferien, 3 wochen noch... 8) den lehrer hab ich nächstes jahr zwar nicht mehr, wäre aber trotzdem kein problem ihm die zahl zu servieren. fänds echt ziemlich geil, wenn ihr des hinkriegts (y) :)
hab einen alten rechner mal bis ~9^630000 rechnen lasen, aber es ging dann immer langsamer (~1d für 1000 potenzen O_o; lag aber wohl auch am rechner :D), deswegen hab ich das beendet. wenn wer was mit der zahl anfangen kann, kann ich sie euch als textdatei hier verlinken.
also ich hoff mal ihr tuts noch ein bisschen weiterprogrammieren und kriegts des hin (y) :)

tombman
2004-09-01, 04:01:37
nur mal so na Frage: hat schon wer diese Methode probiert?

Einfach so rechnen lassen wie man per Hand rechnen würde?
Dabei entstehen nämlich nur ganz kleine Zahlen!

zb:

1234 * 9
_______
11106

Also einfach so rechnen lassen: 9 mal 4 ist 36 bleibt 3, 9 mal 3 ist 27 plus 3 ist 30 bleibt 3, 9 mal 2 ist 18 plus 3 ist 21 bleibt 2, 9 mal 1 ist 9 plus 2 ist 11

So bleibt das ganze innerhalb vom kleinen 1 mal 1 und man kann so gut wie unendlich große Zahlen rechnen lassen. Das Programm muß dann nur noch die einzelnen Zifferm in ein Array schreibem, welches eben ca 300 Millionen Stellen hat. Falls das für ein Array zu groß ist, dann wird eben aufgeteilt an der Array Grenze und etwaige Reste ("bleibt x") werden einfach an das Array mit der nächsthöheren Nummer übergeben.

Die größte Berechnung innerhalb dieser dann 300 Millionen Stellen langen Wurst, die dann noch vorkommen kann wäre diese:

999 * 9
_____
8991

Also: 9 mal 9 ist 81 bleibt 8, 9 mal 9 ist 81 plus 8 ist 89 BLEIBT WIEDER 8 usw .... dann wenn immer 8 bleibt entstehen nur 9er, solange eben bis 9 mit kleineren Werten multipliziert wird, dann bleibt aber auch weniger und wir bleiben immer unter 100.

Das solllte dann auch nicht lang dauern, denn für jede neue Ziffer würde nur eine Multiplikation + eine Addition + eine "üBergabe" an Last anfallen.

Laut Gauss wären das bei ca 300 Mille Stellen ca 301 Mille * 300/2 Mille Minirechnungen (mul + add + übergabe), also 301m*150m = 45*10^14 Berechnungen, welche aber seeeehr schnell von einem PC ausgeführt werden können.
(9^45000 macht mein Rechner in lockeren 2 Sekunden)

Ich hab jetzt nur geschätzt, es sind noch ein bisschen mehr, da es ja nicht 300mille sondern 387.420.489 sind.

Bitte nicht hauen wenn ich nur shit rede ;)

littlejam
2004-09-01, 09:36:36
Die Methode ist eine der ersten in diesem Thread gewesen.

So wie du dir das denkst gehts aber nicht/nicht schnell genug.
Es ist ja nicht 300mio * 9 zu berechnen, sondern 9*9*9...
Die Zahlen werden somit immer größer und länger zu berechnen.
Probier es aus: einmal 9^50000 und dann 9^100000, die Zeit wird sich mehr als verdoppeln.

Gruß

BubbleBoy
2004-09-01, 11:04:12
Die Methode ist eine der ersten in diesem Thread gewesen.

So wie du dir das denkst gehts aber nicht/nicht schnell genug.
Es ist ja nicht 300mio * 9 zu berechnen, sondern 9*9*9...
Die Zahlen werden somit immer größer und länger zu berechnen.
Probier es aus: einmal 9^50000 und dann 9^100000, die Zeit wird sich mehr als verdoppeln.

genau, "neun" rechnet so und die Geschwindigkeit ist, gelinde gesagt, bescheiden :D

anorakker
2004-09-01, 20:31:28
edit : gelöscht wg. doofer idee ;)

Brillus
2004-11-23, 17:38:45
Nur so ne Hypotesche frage wie schnell rechent ein Rechner daran 9^(9^9)² wenn 9^(9^9) bekant wäre (allsi alle soundsoviel Millionen stellen).

Da mit dem passenden Algoryhmus maximal die 60 fache Zeit bräuchte, sprich er müsste maximal 2*29 Multiplikationen mit so riesen Zahlen machen und sonst wären es noch 29 bitshift und 28 vergleiche mit binaären & Verglecihe auf 9^9.

Jo ich hatte heute in der schule nciht viel zu tun da ist mri dieser Thread wieder eingefallen.

HellHorse
2006-05-22, 10:17:49
Jetzt seht nur was ihr angerichtet habt:
#include <stdlib.h>
#include <stdio.h>
#include "gmp.h"

int compute() {
// initialize
mpz_t result;
int status, written;
unsigned long int base = 9;
unsigned long int exp = 387420489; // 9^9
FILE *file;
mpz_init(result);

// compute 9^9^9
printf("computing 9^9^9 ...");
fflush(stdout);
mpz_ui_pow_ui(result, base, exp);
printf(" done\n");
fflush(stdout);

// save raw
printf("saving raw data...");
fflush(stdout);
file = fopen("999.raw", "w");
if (file != NULL) {
written = mpz_out_raw(file, result);
fclose(file);
printf(" done\n");
fflush(stdout);
status = written != 0 ? 0 : 1;
} else {
printf(" failed\n");
fflush(stdout);
status = 1;
}

// save formatted
if (status == 0) {
printf("formatted raw data...");
fflush(stdout);
file = fopen("999.txt", "w");
if (file != NULL) {
written = mpz_out_str(file, 10, result);
fclose(file);
printf(" done\n");
fflush(stdout);
status = written != 0 ? 0 : 1;
} else {
printf(" failed\n");
fflush(stdout);
status = 1;
}
}

// clean up
mpz_clear(result);
return status;
}

int main(int argc, char *argv[]) {
return compute() == 0 ? EXIT_SUCCESS : EXIT_FAILURE;
}


Damit lässt sich auf meiner Möhre 9^(9^9) in etwa 5 Minuten berechnen (vorausgesetzt ich habe keine Fehler gemacht). Ein 64bit Athlon64/Opterton System sollte signifikant schneller sein.
Die Zahl roh zu speichern dauert etwa eine halbe Stunde. Die Datei ist 153'511'741 Bytes gross.
Die Zahl im Zehnersytem formattiert abzuspeichern dauert wesentlich länger, ist aber innerhalb einer Nacht machbar. Datei ist 369'693'100 Bytes gross d.h die Zahl wird wohl ebensoviele Stellen haben.

Zum Speicherverbrauch: 384 MB RAM reichen zum berechnen locker. Bei der Ausgabe wurde dann hin und wieder mal geswap. Es artete aber nicht in einer Swappingorgie aus.

Krieg' ich jetzt 'was? ;D

tombman
2006-05-22, 10:58:36
BubbleBoy[/POST]']genau, "neun" rechnet so und die Geschwindigkeit ist, gelinde gesagt, bescheiden :D
Hmm, also funken tut es auf jeden Fall so, nur isses wahrscheinlich langsam.

Aber ich hab ne andere Idee ;)

Einfach 387 Millionen mal die Rechnung MAL 10 MINUS DER ZAHL DAVOR ausführen ;)

Der Anfang wäre so:

9*9= 81 | erwartet

9*10 = 90 -> -9 = 81 |stimmt

81*9 = 729 | erwartet

81*10= 810 -> -81 = 729 | stimmt :cool:

Die Rechenaufgabe [* 10 - vorige Zahl] sollte für eine CPU doch Kinderkacke sein, das geht superschnell :cool:

Was sagt ihr dazu? ;)

p.s: oder man könnte das ganze binär machen und so byte-shift ausnutzen, jedenfalls irgendwas was total einfach für einen CPU ist.... MAL ZEHN hab ich jetzt nur als Beispiel genommen, weil es für MENSCHEN einfach ist, nämlich nur eine 0 hintendran... aber die Idee sollte klar sein ;)

Coda
2006-05-22, 11:13:47
HellHorse[/POST]']Jetzt seht nur was ihr angerichtet habt:
GMP ist einfach toll :D

Allerdings bekomm ich nen Speicherzugriffsfehler wenn ich das bei mir laufen lass :|

_CaBaL_
2006-05-22, 11:59:11
Hmm wieso macht ihr das eigentlich so kompliziert :|


9^9 = 387420489

Also

X = 9

for i = 1 to 387420489
X = X * 9
next i

debug.print x

so das mach ich jetzt mal, VBA ich komme ^^


[edit]
fu überlauf :redface:

Chris Lux
2006-05-22, 12:29:24
_CaBaL_[/POST]']
[edit]
fu überlauf :redface:
LOOOOOOL

*scnr*

#44
2006-05-22, 13:33:17
_CaBaL_[/POST]']Hmm wieso macht ihr das eigentlich so kompliziert :|

ich glaube die idee war, das ergebniss noch zu lebzeiten des aktuellen systems zu bekommen ^__^

9*9 = schnell berechnet
zahl mit 360 MIO stellen * 9 = nicht so schnell berechnet (ein schelm wer meint ich untertreibe;))

_CaBaL_
2006-05-22, 13:41:51
Ach man und ich dachte ich kann da mit meinem X2 hier auf Arbeit was reißen :D

Coda
2006-05-22, 13:47:49
Für VBA hilft dir Dual Core rein gar nichts.

Ganon
2006-05-22, 14:08:49
Coda[/POST]']Allerdings bekomm ich nen Speicherzugriffsfehler wenn ich das bei mir laufen lass :|

GMP reagiert sehr empfindlich auf Compiler und ihre Optionen. Hast du das schon mal geprüft?

_CaBaL_
2006-05-22, 14:10:57
Coda[/POST]']Für VBA hilft dir Dual Core rein gar nichts.

Weiß ich ;), aber was anderes steht mir hier nich zuv Verfügung. Obwohl reines VB hätt ich noch rumzuliegen.

Oder ich quäle mein Linux Notebook, aber das Prob is ja jetzt eh schon durch, ich glaube eh nicht dass man das mit VB lösen kann.

Coda
2006-05-22, 14:25:34
Ganon[/POST]']GMP reagiert sehr empfindlich auf Compiler und ihre Optionen. Hast du das schon mal geprüft?
GCC 3.4.6 -O2. Dürfte eigentlich kein Problem sein :|

Ich lass aber nochmal durchkompilieren.

HellHorse
2006-05-22, 23:34:18
Coda[/POST]']GMP ist einfach toll :D
Ja, ich bin jetzt auch doll Fan von GMP. :)
Coda[/POST]']Allerdings bekomm ich nen Speicherzugriffsfehler wenn ich das bei mir laufen lass :|
Normalerweise würde ich jetzt an der wahrscheinlichsten Fehlerquelle (mir) ansetzen. Da es bei mir aber schon zweimal lief, halte ich das für weniger wahrscheinlich.

Wo genau hakt es denn? Bei der Berechnung? Falls ja könnte es durchaus an GMP liegen:
http://www.swox.com/gmp/
GMP is very often miscompiled! We are seeing ever increasing problems with mis-compilations of the GMP code. Please never use your newly compiled libgmp.a or libgmp.so without first running make check.
Q3: I get a segfault in a program that uses GMP to calculate numbers with several hundred thousand digits. Why?

A3: Upgrade to GMP 4.2.x. (Previous version of GMP allocated huge blocks of temporary memory on the stack, causing problems for some system.)

Also ich habe hier auch gcc 3.4.6 mit -O2.

Coda
2006-05-23, 00:04:46
Aaah ok, ich hab noch GMP 4.1 :)

Ganon
2006-05-25, 12:36:40
HellHorse[/POST]']
Damit lässt sich auf meiner Möhre 9^(9^9) in etwa 5 Minuten berechnen (vorausgesetzt ich habe keine Fehler gemacht).

Bei mir ca. 3 Minuten, etwas darunter.

HellHorse[/POST]']
Die Zahl roh zu speichern dauert etwa eine halbe Stunde. Die Datei ist 153'511'741 Bytes gross.

Hat nicht mal eine Minute gedauert. :)

HellHorse[/POST]']
Die Zahl im Zehnersytem formattiert abzuspeichern dauert wesentlich länger, ist aber innerhalb einer Nacht machbar.

Läuft noch. ;)

P.S. Das soll jetzt kein "bei mir ist's schneller" Post sein. Nur zur Info. ;)

tombman
2006-05-25, 12:41:31
könntet ihr mal ne fertig kompilierte .exe uploaden inkl. aller software/tools die man dazu braucht um es auszuführen? Danke.. ;)

Ganon
2006-05-25, 12:56:12
tombman[/POST]']könntet ihr mal ne fertig kompilierte .exe uploaden inkl. aller software/tools die man dazu braucht um es auszuführen? Danke.. ;)

Hmm, also ich kann's nicht, da OS X ;).

Das "Blöde" ist nur, das sich GMP beim kompilieren den Prozessor ausliest und dann dafür entsprechend "optimiert". Da müsste man crosscompilen, wenn du z.B. ne A64-Version (64bit) auf einem P4 machen willst...

MadMan2k
2006-05-25, 12:57:08
HellHorse[/POST]']
Krieg' ich jetzt 'was? ;D
wenn du mir erklärst wie mpz_ui_pow_ui() das so viel schneller hinkiregt...

Coda
2006-05-25, 13:03:18
Weil GMP ziemlich optimiert ist auf Rechnungen mit großen Zahlen? Genaueres steht im Source-Code.

tombman[/POST]']könntet ihr mal ne fertig kompilierte .exe uploaden inkl. aller software/tools die man dazu braucht um es auszuführen? Danke.. ;)
GMP unter Windows zu kompilieren ist ziemlich kompliziert und fertige Libs hab ich auch nirgends gefunden. Wenn dann für Linux.

Ganon
2006-05-25, 13:03:58
MadMan2k[/POST]']wenn du mir erklärst wie mpz_ui_pow_ui() das so viel schneller hinkiregt...

Guck doch in den Code ^^ Ich blick da zwar gerade nicht durch, sieht aber wie ein ziemliches Bit-Gehäcksel aus. ;)

HellHorse
2006-05-25, 13:49:04
Ganon[/POST]']Bei mir ca. 3 Minuten, etwas darunter.
Etwa eine Minute halte ich für ein schnelles 64bit System (AMD64) durchaus erreichbar.
Ganon[/POST]']
Hat nicht mal eine Minute gedauert. :)
Mehr RAM?
Ganon[/POST]']
P.S. Das soll jetzt kein "bei mir ist's schneller" Post sein. Nur zur Info. ;)
;)

HellHorse
2006-05-25, 17:23:55
tombman[/POST]']könntet ihr mal ne fertig kompilierte .exe uploaden inkl. aller software/tools die man dazu braucht um es auszuführen? Danke.. ;)
Ich hoffe das geht
http://rapidshare.de/files/21355878/999.exe.html

Unglaublich un1337 da nur 32bit und langweilige Konsolenapplikation.

Coda
2006-05-25, 18:06:15
Ist das eine GMP-Version von Windows mit oder ohne Assembler-Zeug? Weil das ist ja in GAS geschrieben und eigentlich nicht kompilierbar unter Windoze. Wobeis ja da den einen Port gibt...

The_Invisible
2006-05-25, 18:19:10
kann das sein, die raw datei war in ca 1min fertig (150mb), RAM verbrauch schwankte zwischen 10 und 600mb auf und ab und für die formatierte geschichte macht er jetzt schon 6min rum

mfg

HellHorse
2006-05-25, 18:40:57
Coda[/POST]']Ist das eine GMP-Version von Windows mit oder ohne Assembler-Zeug? Weil das ist ja in GAS geschrieben und eigentlich nicht kompilierbar unter Windoze. Wobeis ja da den einen Port gibt...
Du fragst mich Sachen. Da das einzige was ich für Windows fand 4.1 war (http://www.cs.nyu.edu/exact/core/gmp/) hab ich's einfach selbst kompiliert (MinGW).
Auf jeden Fall ist es nicht unterirdisch langsam auf Windows.

kann das sein, die raw datei war in ca 1min fertig (150mb), RAM verbrauch schwankte zwischen 10 und 600mb auf und ab und für die formatierte geschichte macht er jetzt schon 6min rum
Mit einem schnellen System und viel RAM? Ja. Die formatierte Geschichte wird "länger" dauern.

Ganon
2006-05-25, 19:01:32
HellHorse[/POST]']Ja. Die formatierte Geschichte wird "länger" dauern.

Ich hab nach 2 Stunden abgebrochen, weil ich weg musste. Bringt mir ja eh nix. ^^

Kabelsalat
2006-05-25, 19:49:02
360MB... was eine Zahl :eek:

The_Invisible
2006-05-25, 19:49:17
HellHorse[/POST]']
Mit einem schnellen System und viel RAM? Ja. Die formatierte Geschichte wird "länger" dauern.

ist jetzt fertig, keine ahnung wie lange das gedauert hat da ich weg war, aber die fertige datei ist 361029kb groß

mfg

Gast
2006-05-28, 21:09:26
kann man die mal posten ich möchte sie sehen bitte :D

TheGamer
2006-05-29, 20:38:10
hier stand mist

Coda
2006-05-29, 21:26:10
Gast[/POST]']kann man die mal posten ich möchte sie sehen bitte :D
Ich will sehen wie du 360MiB hier ins Forum postest. Viel Glück.

Kabelsalat
2006-05-29, 21:27:37
Naja, gehen müsste es ja eigentlich. Die Frage ist eher, ob der DB-Server damit klarkommt...

Aqualon
2006-05-29, 22:14:57
Klar geht das, auf 7200 Postings verteilt (zumindest wenn die 50000 Zeichen pro Posting Beschränkung noch gilt).

Aqua

Coda
2006-05-29, 22:51:43
*script schreib* *evil* ;)

Kabelsalat
2006-05-29, 23:06:37
Bei 360MB macht blöderweise auch die Zwischenablage schlapp...

Coda
2006-05-29, 23:52:04
Abtippen :ugly:

The_Strip
2006-05-30, 13:17:13
Coda[/POST]']Abtippen :ugly: Ich machs *postingssammel* ;) Wär ich ja dann immerhin Master Member!

alkorithmus
2006-05-30, 13:52:29
Coda[/POST]']Abtippen :ugly:

Pfingsten ist verlängertes Wochenende, da setz ich mich mal ran.

:ugly2::

Coda
2006-05-30, 14:15:01
Fairplayaa[/POST]']Pfingsten ist verlängertes Wochenende, da setz ich mich mal ran.
Woa :eek:
Ich wusste noch gar nicht, dass das bis ins nächste Jahrtausend geht *Party*

alkorithmus
2006-05-30, 14:35:04
Ist doch ein klacks wenn man erstmal ein System gefunden hat und sich die Zahlen wiederholen.

Mr. Lolman
2006-05-30, 16:39:45
So ne Datei sollte sich doch auf ein paar 100kb zippen lassen...

Kabelsalat
2006-05-30, 16:47:09
Ich schätze kleiner als die RAW-Datei lässt sich das ganze nicht packen... bei ~150MB ist somit schluss.

Mr. Lolman
2006-05-30, 16:47:41
HellHorse[/POST]']Ich hoffe das geht
http://rapidshare.de/files/21355878/999.exe.html

Unglaublich un1337 da nur 32bit und langweilige Konsolenapplikation.

Rund 45 sec. hat damit das Ausrechnen auf einem 3700+ @ 3GHz gedauert.

Kabelsalat
2006-05-30, 16:48:32
Danach kommt noch das konvertieren in eine lesbare Zahl!

(del676)
2006-05-30, 16:51:26
machst ein photo vom mathelehrer wenn du ihm die zahl präsentierst?

Mr. Lolman
2006-05-30, 16:59:22
Kabelsalat[/POST]']Danach kommt noch das konvertieren in eine lesbare Zahl!

Ja das dauert. Raw war innerhalb von 2 sec fertig. Aber an der Formatierten werkt er immernoch...

Coda
2006-05-30, 17:41:05
Mr. Lolman[/POST]']So ne Datei sollte sich doch auf ein paar 100kb zippen lassen...
Warum sollte sie?

Ganon
2006-05-30, 17:46:48
Müsste einfach mal einer mit bzip2 packen ;) 100kb zwar nicht aber.... wollen wir ne Wette machen? ;)

Gast
2006-05-30, 17:47:52
Man kann die Zahl doch auch binär in eine Datei speichern. Dann verbraucht die sicherlich keine 360mb mehr.

HellHorse
2006-05-30, 17:56:07
Kabelsalat[/POST]']Ich schätze kleiner als die RAW-Datei lässt sich das ganze nicht packen... bei ~150MB ist somit schluss.
Yepp, 159'282'862 bytes mit bzip2.

Gast
2006-05-31, 21:27:04
mich würd mal interessieren wieviel das in der einheit "schreibmaschinen geschriebene seiten" ist

Coda
2006-05-31, 21:50:21
Ganon[/POST]']Müsste einfach mal einer mit bzip2 packen ;) 100kb zwar nicht aber.... wollen wir ne Wette machen? ;)
Gern. Viel unter 50% wirst nicht kommen.

Aqualon
2006-05-31, 21:58:35
Wenn wir mal von Courier New 12pt ausgehen, dürften es ~102000 DINA4 Seiten sein.

Aqua

Ganon
2006-05-31, 22:00:45
Coda[/POST]']Gern. Viel unter 50% wirst nicht kommen.

Ja nu ist's zu spät. ;D

Gast
2006-05-31, 23:05:50
Aqualon[/POST]']Wenn wir mal von Courier New 12pt ausgehen, dürften es ~102000 DINA4 Seiten sein.

Aqua:eek:

HellHorse
2006-05-31, 23:11:17
Gast[/POST]']mich würd mal interessieren wieviel das in der einheit "schreibmaschinen geschriebene seiten" ist
Wikipedia sagt eine Schreibmaschinenseite sei etwa 5kb (http://de.wikipedia.org/wiki/Speicherkapazit%C3%A4t).
Also wären das ungefär 72'205.

Coda
2006-05-31, 23:23:41
Ganon[/POST]']Ja nu ist's zu spät. ;D
Das hätt ich auch schon vorher gewusst :tongue:

Gast
2006-06-01, 21:19:38
hi leute aber ich check eure aufregung net. wenn ich 9^9^9 in den taschenrechner eingeb dann kommt folgendes raus:
1966270505 x 10^77

MFG ...

Ganon
2006-06-01, 21:31:55
Gast[/POST]']hi leute aber ich check eure aufregung net. wenn ich 9^9^9 in den taschenrechner eingeb dann kommt folgendes raus:

Thread nicht kapiert, bzw. nicht mal gelesen. Setzen 6... :|

http://www.forum-3dcenter.org/vbulletin/showpost.php?p=1977410&postcount=13

Gast
2006-06-01, 21:36:27
warum setzen 6?

ich schreib des mal schnell mit C++ aber ich kanns net glauben.^^

MFG ...

Ganon
2006-06-01, 21:39:44
Wie wäre es wenn du einfach mal die erst 2 Seiten lesen würdest? Die danach sind auch interessant... :|

Coda
2006-06-01, 21:47:27
Gast[/POST]']ich schreib des mal schnell mit C++ aber ich kanns net glauben.^^
Es geht um 9^81 nicht um 81^9.

Ganon
2006-06-01, 21:53:02
Coda[/POST]']Es geht um 9^81 nicht um 81^9.

:|

Eigentlich geht's um 9^387420489 oder was meinst du jetzt?

Coda
2006-06-01, 21:56:08
Äääh ja mein ich doch...

mf_2
2006-07-09, 17:33:02
ich weiss der thread is alt, aber das rapidshare programm kann nicht mehr gedownloaded werden. kann das nochmal jemand uppen bitte?
Thx!

HellHorse
2006-07-09, 21:24:25
http://rapidshare.de/files/25391813/999.exe.html

Gast
2006-07-10, 02:46:08
wo issn der source code :D

Gast
2006-07-10, 02:47:04
vielleicht ist ja ein trojanisches hell horse drin ;)

HellHorse
2006-07-10, 10:01:03
Gast[/POST]']wo issn der source code :D
Blätter ein paar Seiten nach vorne.

Gast
2007-06-06, 16:42:34
Ich habe 9^(9^9) ausgerechnet.

Auswertung fuer die Zahl 9^9^9:

Die Quersumme ist : 1663600878
Quersumme/9 ist : 184844542 Rest 0
Durchschnittlicher Ziffernwert: 4.5000

Ziffernhaeufigkeit bei 369693100 Stellen:
+--------+---------------+---------------+
| Ziffer | Anzahl | Prozent |
+--------+---------------+---------------+
| 0 | 36967783 | 9.999587 |
+--------+---------------+---------------+
| 1 | 36967842 | 9.999603 |
+--------+---------------+---------------+
| 2 | 36969142 | 9.999955 |
+--------+---------------+---------------+
| 3 | 36973760 | 10.001204 |
+--------+---------------+---------------+
| 4 | 36979528 | 10.002764 |
+--------+---------------+---------------+
| 5 | 36961052 | 9.997766 |
+--------+---------------+---------------+
| 6 | 36966895 | 9.999347 |
+--------+---------------+---------------+
| 7 | 36972157 | 10.000770 |
+--------+---------------+---------------+
| 8 | 36970838 | 10.000413 |
+--------+---------------+---------------+
| 9 | 36964103 | 9.998592 |
+--------+---------------+---------------+

Die Zahl selbst habe ich als Textdatei mit 369693100 Byte Länge vorliegen.
Gepackt sind es immer noch ca. 155MB.

Ich habe erst selbst ein Programm geschrieben das ganz naiv schriftlich rechnet. Das wäre in 10 Jahren noch nicht durch gewesen. Mit der GNU-MP Library "gnp.lib" gings schneller (ca 3 Stunden bei 1,5 MHz und 1GB RAM).

Ganon
2007-06-06, 18:30:44
Ich habe 9^(9^9) ausgerechnet.

Nur leider 1 Jahr zu spät ;)

Gast
2007-06-07, 11:24:49
ich weiß der thread ist alt, aber ihr habt euch echt doof angestellt
lernt man das nicht an der uni, sich vorher gedanken zu machen? ;-)
ihr hättet einfach die zahl im neuner-system nehmen können und mit
dem horner-schema ins dezimalsystem umrechnen. dann braucht man
keine großen zahlen mehr...

Coda
2007-06-07, 12:16:34
Jetzt seht nur was ihr angerichtet habt:
#include <stdlib.h>
#include <stdio.h>
#include "gmp.h"

int compute() {
// initialize
mpz_t result;
int status, written;
unsigned long int base = 9;
unsigned long int exp = 387420489; // 9^9
FILE *file;
mpz_init(result);

// compute 9^9^9
printf("computing 9^9^9 ...");
fflush(stdout);
mpz_ui_pow_ui(result, base, exp);
printf(" done\n");
fflush(stdout);

// save raw
printf("saving raw data...");
fflush(stdout);
file = fopen("999.raw", "w");
if (file != NULL) {
written = mpz_out_raw(file, result);
fclose(file);
printf(" done\n");
fflush(stdout);
status = written != 0 ? 0 : 1;
} else {
printf(" failed\n");
fflush(stdout);
status = 1;
}

// save formatted
if (status == 0) {
printf("formatted raw data...");
fflush(stdout);
file = fopen("999.txt", "w");
if (file != NULL) {
written = mpz_out_str(file, 10, result);
fclose(file);
printf(" done\n");
fflush(stdout);
status = written != 0 ? 0 : 1;
} else {
printf(" failed\n");
fflush(stdout);
status = 1;
}
}

// clean up
mpz_clear(result);
return status;
}

int main(int argc, char *argv[]) {
return compute() == 0 ? EXIT_SUCCESS : EXIT_FAILURE;
}


Damit lässt sich auf meiner Möhre 9^(9^9) in etwa 5 Minuten berechnen (vorausgesetzt ich habe keine Fehler gemacht). Ein 64bit Athlon64/Opterton System sollte signifikant schneller sein.
Die Zahl roh zu speichern dauert etwa eine halbe Stunde. Die Datei ist 153'511'741 Bytes gross.
Die Zahl im Zehnersytem formattiert abzuspeichern dauert wesentlich länger, ist aber innerhalb einer Nacht machbar. Datei ist 369'693'100 Bytes gross d.h die Zahl wird wohl ebensoviele Stellen haben.

Zum Speicherverbrauch: 384 MB RAM reichen zum berechnen locker. Bei der Ausgabe wurde dann hin und wieder mal geswap. Es artete aber nicht in einer Swappingorgie aus.

Krieg' ich jetzt 'was? ;D
Soviel zu keine Gedanken machen.

Spasstiger
2007-06-07, 13:01:20
Soviel zu keine Gedanken machen.
Es wird da allerdings nicht im Neunersystem mit kaskadiertem Hornerschema gerechnet.
Im Neunersystem ist das Ergebniss ja einfach eine 1 mit eine Milliarde Nullen dran. Hellhorse hat aber den Exponenten 387420489 im Zehnersystem vorgegeben, so dass hier gar nicht so geschickt gerechnet wird wie im Neunersystem.
Ich weiß aber natürlich nicht, wie der Befehk mpz_ui_pow_ui realisiert ist.

Gast
2007-06-07, 14:23:35
http://rapidshare.de/files/25391813/999.exe.html
Schon wida "Datei nicht gefunden" :( :( :(


BTW die Zahl kann man sehr wohl extrem komprimieren. Genau genommen wäre 9^9^9 nämlich eine sehr effektive Komprimierung. Nur das Entpacken würde ne ganze Weile dauern. Ändert aber nichts daran, dass das eine legitime Komprimierung ist. :smile:

Spasstiger
2007-06-07, 14:53:58
Genau genommen wäre 9^9^9 nämlich eine sehr effektive Komprimierung.
9^(9^9) ist eine 1 mit eine Milliarde Nullen dran (im Neunersystem).

D.h. du musst nur speichern:
1000000000
9

Der Decoder weiß dann, dass eine 1 mit eine Milliarde Nullen dahinter im Neunersystem gespeichert wurde.

Oder man speichert "9^(9^9)". ;)

Coda
2007-06-07, 15:46:57
Hellhorse hat aber den Exponenten 387420489 im Zehnersystem vorgegeben, so dass hier gar nicht so geschickt gerechnet wird wie im Neunersystem.
Nach dem kompilieren ist das natürlich binär.

Ich weiß aber natürlich nicht, wie der Befehk mpz_ui_pow_ui realisiert ist.
Über Fouriertransformation. Das ist hochoptimiert für die Multiplikation großer Zahlen.

Die Frage ist doch, ob die Umwandlung von binär in dezimal schneller geht oder von der 9er-Basis.

HellHorse
2007-06-09, 23:12:06
Schon wida "Datei nicht gefunden" :( :( :(
http://rapidshare.com/files/36215871/999.exe.html

Ich halte das ja für einen cooleren Benchmark als SuperPi, aber mich fragt ja keiner.

BAGZZlash
2007-06-10, 00:15:18
Ich halte das ja für einen cooleren Benchmark als SuperPi, aber mich fragt ja keiner.


Tatsächlich ist's ähnlich wie Prime, da hier auch FFTs verwendet werden.

PHuV
2007-06-14, 19:23:14
Das Berechnen und das Speichern der Rohdaten geht ja recht flott, ca 5 min. Aber das Programm hat sich mal so 600 MB gekrallt, kein Problem bei 2 GB.

HellHorse
2007-06-14, 22:56:53
Aber das Programm hat sich mal so 600 MB gekrallt, kein Problem bei 2 GB.
Naja, es haut halt einen 350 MB string raus.

Gast
2007-06-15, 05:41:10
Och, wenn dein Lehrer die Zeit hat um sich das Ergebnis vorlesen zu lassen :D

Das lohnt sich dann selbst als Schüler nicht.

Selbst wenn du 10 Stunden lang das Ergebnis vorliest, hast du nur einen stundenlohn von 10 €.


Ich bin dafür daß der Lehrer den Preis erhöht.
100 € sind zu wenig.

Gast
2007-06-15, 05:58:05
Ich habe mal sowas gehört, dass man für für mathematische Berechnungen auch die GPU einsetzen kann? Stmmt das? Würde das schneller gehen?


In der Theorie ja, aber leider kannst du das in der GPU nicht abbilden.
Bei max 64 Bit ist Schluß.

Eine richtige CPU aber ist flexibel genug, so daß du die Berechnung anders realisieren kannst, z.B. nicht mit der typischen Integer Methode sondern z.b. mit Strings.

Gast
2007-06-15, 06:50:39
der lehrer wollte heut als ich ihm mal die ersten 50000 stellen präsentiert hab nix mehr wissen von den 100€ (war ja irgendwie auch zu erwarten... aber trotzdem :down: ) :(:(:(:(

Es ist natürlich denkbar, daß der Lehrer keine 100 € bezahlen will.
Aber es ist genauso denkbar, daß der Lehrer die 100 € zahlt und du aber das Geld selber behalten willst, es weiß ja hier schließlich niemand, ob der Lehrer dir das Geld gegeben hat oder nicht. :mad: :down:

Gast
2007-06-15, 10:35:26
Der Code von Hellhorse aus Postin #359 läßt sich bei mir nicht compilieren.
http://www.forum-3dcenter.org/vbulletin/showpost.php?p=4338985&postcount=359

Ich bekomme folgendes als Fehlermeldung:

g++ 9pow9pow9.cpp -o 9pow9pow9.bin
/tmp/ccY9czDg.o: In function `compute()':
9pow9pow9.cpp:(.text+0x1b): undefined reference to `__gmpz_init'
9pow9pow9.cpp:(.text+0x4d): undefined reference to `__gmpz_ui_pow_ui'
9pow9pow9.cpp:(.text+0xae): undefined reference to `__gmpz_out_raw'
9pow9pow9.cpp:(.text+0x15e): undefined reference to `__gmpz_out_str'
9pow9pow9.cpp:(.text+0x1bf): undefined reference to `__gmpz_clear'
collect2: ld gab 1 als Ende-Status zurück


OS ist Ubuntu 7.04

Gast
2007-06-15, 10:42:01
ich weiß der thread ist alt, aber ihr habt euch echt doof angestellt
lernt man das nicht an der uni, sich vorher gedanken zu machen? ;-)
ihr hättet einfach die zahl im neuner-system nehmen können und mit
dem horner-schema ins dezimalsystem umrechnen. dann braucht man
keine großen zahlen mehr...


++ :up:

Stimmt, Horner Schema rulez.
Hatte ich ganz vergessen. :D

HellHorse
2007-06-15, 20:11:11
Der Code von Hellhorse aus Postin #359 läßt sich bei mir nicht compilieren.

ist C und nicht C++
zu musst schon gegen GMP linken und compilieren

gcc -lgmp 9pow9pow9.c -o 9pow9pow9

Gast
2007-06-15, 21:31:24
THX, damit hat es geklappt.

Gast
2008-02-23, 23:47:45
Ich weiss dieser Thread ist etwas veraltet...

Habs dennoch mal ausgerechnet und hochgeladen:

http://rapidshare.com/files/94319084/xyz.part1.rar.html
http://rapidshare.com/files/94366066/xyz.part2.rar.html

Super Grobi
2008-02-23, 23:49:53
Passt: Wie oft muss man ein DinA4 Blatt fallten, damit es bis zum Mond reicht? (Stichwort:Blattdicke)

Das Ergebniss ist sehr interessant!

SG

p.s.
wer es weiss, sollte sich "HALLO ICH, ICHWEISS ES UND BIN SEHR SCHLAU" sparen und den anderen den Spaß nicht verderben!

Gast
2008-02-23, 23:58:21
Passt: Wie oft muss man ein DinA4 Blatt fallten, damit es bis zum Mond reicht? (Stichwort:Blattdicke)

Das Ergebniss ist sehr interessant!

SG

p.s.
wer es weiss, sollte sich "HALLO ICH, ICHWEISS ES UND BIN SEHR SCHLAU" sparen und den anderen den Spaß nicht verderben!
Wenn ich mich nicht täusche ist das aber eine ziemlich einfache Aufgabe :P

Berni
2008-02-24, 00:13:21
Wenn ich mich nicht irre, war das doch bei Kerner im Fernsehen da vor ein paar Tagen?

Gast
2008-02-24, 00:36:36
Ich hab folgendes rausgekriegt:
binlog M/B
Wobei M der Abstand zum Mond und B die Blattdicke ist.

Stimmts?

Super Grobi
2008-02-24, 12:24:22
Wenn ich mich nicht irre, war das doch bei Kerner im Fernsehen da vor ein paar Tagen?

Jup. Ich war ganz hin und weg von den Sachen, die dort gezeigt wurden. Aber das mit dem Blatt und dem Mond fand ich extrem.

42 mal
http://www.tagesspiegel.de/magazin/wissen/Mathematik;art304,2457711

SG

rotalever
2008-02-24, 12:47:24
Mit dem einzigen Problem, dass man es nicht 42 mal falten kann.

Trap
2008-02-24, 13:51:15
Selbst wenn man 42 mal faltet wird das Blatt nicht so dick, die Kante über die Falz muss ja selbst so lang sein wie der Stapel hoch ist. Damit kann der Stapel maximal 29cm hoch werden (bei einem A4 Blatt).

Mathematisches Modell und reales Beispiel passen nicht zusammen. Mit in der Mitte durchschneiden und aufeinanderstapeln ginge es, aber mit Falten nicht.

rotalever
2008-02-24, 15:11:24
Selbst wenn man 42 mal faltet wird das Blatt nicht so dick, die Kante über die Falz muss ja selbst so lang sein wie der Stapel hoch ist. Damit kann der Stapel maximal 29cm hoch werden (bei einem A4 Blatt).

Mathematisches Modell und reales Beispiel passen nicht zusammen. Mit in der Mitte durchschneiden und aufeinanderstapeln ginge es, aber mit Falten nicht.
Stimmt. Aber mit auseinanderschneiden wird man auch nicht fertig, da 2^42 Schneiden ein wenig viel sein dürfte ;)

Trap
2008-02-24, 16:14:33
Stimmt. Aber mit auseinanderschneiden wird man auch nicht fertig, da 2^42 Schneiden ein wenig viel sein dürfte ;)
Wenn man nach jedem Schnitt beide Teilstapel aufeinanderlegt reichen auch 42 Schnitte.

Der Stapel hat mit verlustlosen Schnitten am Ende ~15000 nm² wenn man mit einem A4 Blatt anfängt, also eine Seitenlänge in der Größenordnung 100 nm.

Gast
2008-02-25, 10:58:14
Wenn man nach jedem Schnitt beide Teilstapel aufeinanderlegt reichen auch 42 Schnitte.

Der Stapel hat mit verlustlosen Schnitten am Ende ~15000 nm² wenn man mit einem A4 Blatt anfängt, also eine Seitenlänge in der Größenordnung 100 nm.Papier besteht aus Zellulose, einem Polysaccharid. Die Makromoleküle bestehen aus mehreren tausend einzelnen Glucosemolekülen, die wiederum ja auch schon eine gewisse Größe haben. U.U. hätte man also das Problem, daß man nichtmehr einfach nur das Papier schneidet, sondern seine molekularen Bestandteile.

mfg

Trivial
2008-02-28, 04:10:03
Erinnert mich an die Schachbrettaufgabe aus der (afair) siebten Klasse: Wenn ich auf das erste Feld eines Schachbrettes ein Reiskorn lege und auf jedes folgende Feld die doppelte Menge Reiskörner, wieviele Reiskörner habe ich nach den 64 Feldern?

Hmmm... :ulove:

Gast
2008-02-28, 09:13:32
Erinnert mich an die Schachbrettaufgabe aus der (afair) siebten Klasse: Wenn ich auf das erste Feld eines Schachbrettes ein Reiskorn lege und auf jedes folgende Feld die doppelte Menge Reiskörner, wieviele Reiskörner habe ich nach den 64 Feldern?

Hmmm... :ulove:
Ne, 2^64-1 ist viel kleiner.

PHuV
2008-02-28, 10:40:40
Warum falten, man könnte doch auch einfach immer die Din A4 Blätter verdoppelnd aufeinander legen. :uponder: Das würde dann wieder dem klassischen Schachbrett-Rätsel entsprechen.

rotalever
2008-02-28, 15:08:16
Warum falten, man könnte doch auch einfach immer die Din A4 Blätter verdoppelnd aufeinander legen. :uponder: Das würde dann wieder dem klassischen Schachbrett-Rätsel entsprechen.
Beim aufeinanderlegen ist sofort jedem klar, dass man da so viel braucht. Beim Falten ist jeder überrascht, weil 42 eine so kleine Zahl ist.

=Floi=
2016-06-27, 17:30:51
daraus könnte wirklich mal jemand nen benchmark machen. ^^

mich fasziniert das thema auch nach all den jahren noch immer.

nalye
2016-06-27, 18:07:45
Du hattest ~8,5 Jahre Zeit...

kevsti
2016-06-28, 21:18:28
Ok, anstatt was Sinnvolles zu machen, habe ich weiter daran gebastelt ;)

[...]


verbose = True

def info(message):
if verbose: print message

def to_boolean_list(number):
if number < 0:
raise Exception, "number below 0"
boollist = []
while number:
div, rest = divmod(number, 2)
boollist.append(rest)
number = div
return boollist

def biggest_power_of_2(border):
exp = 0
current = 1
while current < border:
exp = exp + 1
current = current * 2
if current == border:
return exp
else:
return exp - 1

def ones(boollist):
count = 0
for next in boollist:
if next:
count = count + 1
return count

def write_to_file(n, filename='9pow9pow9.txt', timeMessage=None):
conservion_timer = Timer()
conservion_timer.start()
info("converting")
s = str(n)
conservion_timer.stop()
info("conversion done, time used: %s" % conservion_timer)

info("writing to file")
f = open(filename, 'w')
f.write("amount of places: %s \n" % len(s))
f.write(s)
if timeMessage:
f.write("\ntime used: %s" % timeMessage)
f.close()
info("done")

class PythonPowerComputer:
def power(self, base, exp):
return base ** exp

class OptimizedMultPowerComputer:
def power(self, base, exp):
biggest_power = biggest_power_of_2(exp)
rest = to_boolean_list(exp - (2 ** biggest_power))
rest.extend((biggest_power - len(rest) + 1) * [False])
saved = []
local_timer = Timer()
local_timer.start()

n = base
if rest[0]:
saved.append(base)

info("staring run 1")

for i in xrange(1, biggest_power + 1):
n = n * n
if rest[i]:
saved.append(n)
info("%05.2f %s" % (100.0 * i / biggest_power, "% done"))

local_timer.stop()
info("run 1 done, time used: %s \n" % local_timer)
local_timer.reset()
local_timer.start()
info("starting run2")

r = 1
for i in xrange(len(saved)):
r = r * saved[i]
info("%05.2f %s" % (100.0 * (i + 1) / len(saved), "% done"))

local_timer.stop()
info("run 2 done, time used: %s" % local_timer)
local_timer.reset()
local_timer.start()
info ("doing last big muliplication")
n = n * r
local_timer.stop()
info ("last muliplication done, time used: %s" % local_timer)
return n

from threading import Lock
from threading import Condition
from threading import Thread

class ConcurrentPowerComputer:

def power(self, base, exp):
biggest_power = biggest_power_of_2(exp)
rest = to_boolean_list(exp - 2**biggest_power)
rest.extend((biggest_power - len(rest) + 1) * [False])
lock = Lock()
signal = Condition(lock)
max = ones(rest)
saved = []
restcomputer = RestComputer(signal, max, saved)
restthread = Thread(target=restcomputer.run, name="rest-computer-thread")

n = base
if rest[0]:
saved.append(base)

restthread.start()

for i in xrange(1, biggest_power + 1):
n = n * n
if rest[i]:
signal.acquire()
saved.append(n)
signal.notify()
signal.release()
info("main-thread: %05.2f %s" % (100.0 * i / biggest_power, "% done"))

restthread.join()
info("doing last muliplication")
n = n * restcomputer.result

info("done")
return n

class RestComputer:
def __init__(self, signal, max, numbers):
self.signal = signal
self.numbers = numbers
self.max = max

def run(self):
r = 1
processed = 0
while processed < self.max:
self.signal.acquire()
if len(self.numbers) <= processed:
self.signal.wait()
next = self.numbers[processed]
self.signal.release()
r = r * next
processed = processed + 1
info("helper-thread: %05.2f %s" % (100.0 * processed / self.max, "% done"))
info("helper-thread done")
self.result = r

class PythonMultiplier:
def mult(self, a, b):
return a * b

from time import time
def bench():
globals()["verbose"] = False
base = 9
exp = 5000000
opt_mult_computer = OptimizedMultPowerComputer()
concurrent_computer = ConcurrentPowerComputer()

start_time = time()
python_result = base**exp
end_time = time()
python_time = end_time - start_time

start_time = time()
optmult_result = opt_mult_computer.power(base, exp)
end_time = time()
optmult_time = end_time - start_time

start_time = time()
concurrent_result = concurrent_computer.power(base, exp)
end_time = time()
concurrent_time = end_time - start_time


print "time for python power: %s seconds" % python_time
print "time for optimized multiplication power: %s seconds" % optmult_time
print "time for concurrent multiplication power: %s seconds" % concurrent_time
if python_result == optmult_result:
print "optimized multiplication power was correct"
else:
print "optimized multiplication power was incorrect"
if python_result == concurrent_result:
print "concurrent multiplication power was correct"
else:
print "concurrent multiplication power was incorrect"

from datetime import timedelta

class Timer:
def __init__(self):
self.reset()

def start(self):
self.starttime = time()

def stop(self):
self.stoptime = time()

def reset(self):
self.starttime = 0
self.stoptime = 0

def __str__(self):
diff_seconds = self.stoptime - self.starttime
diff_delta = timedelta(seconds=diff_seconds)
minutes, seconds = divmod(diff_delta.seconds, 60)
hours, minutes = divmod(minutes, 60)
buff = ""
if diff_delta.days:
if diffdelta - 1:
buff = "%s days " % diff_delta.days
else:
buff = "1 day "
if hours:
if hours - 1:
buff = "%s%s hours " % (buff, hours)
else:
buff = "%s 1 hour " % buff
if minutes:
if minutes - 1:
buff = "%s%s minutes " % (buff, minutes)
else:
buff = "%s1 minute " % buff
if seconds:
if seconds - 1:
buff = "%s%s seconds" % (buff, seconds)
else:
buff = "%s1 second" % buff
if not buff:
buff = "less than 1 second"
return buff

import unittest
class PythonPowerTest(unittest.TestCase):
def setUp(self):
self.computer = PythonPowerComputer()

def test9pow9(self):
n = self.computer.power(9, 9)
self.assertEqual(n, 9**9)

def test12pow12(self):
n = self.computer.power(12, 12)
self.assertEqual(n, 12**12)

def test2pow100000(self):
n = self.computer.power(2, 100000)
self.assertEqual(n, 2**100000)

def test9pow57831(self):
n = self.computer.power(9, 57831)
self.assertEqual(n, 9**57831)

class MultPowerTest(PythonPowerTest):
def setUp(self):
self.computer = MultPowerComputer()

class ConcurrentPowerTest(PythonPowerTest):
def setUp(self):
self.computer = ConcurrentPowerComputer()

class OptimizedMultPowerTest(PythonPowerTest):
def setUp(self):
self.computer = OptimizedMultPowerComputer()

def test():
globals()["verbose"] = False
del argv[-1]
unittest.main()

def run(concurrent):
if concurrent:
computer = ConcurrentPowerComputer()
else:
computer = OptimizedMultPowerComputer()
global_timer = Timer()
global_timer.start()
exp = 9**9
base = 9
n = computer.power(base, exp)
global_timer.stop()
write_to_file(n, "neun.txt", global_timer)

def usage():
print """-t to test
-b to bench
-c concurrent
-n normal, default"""

if __name__ == "__main__":
from sys import argv
if len(argv) > 2:
usage()
elif "-b" in argv:
bench()
elif "-c" in argv:
run(True)
elif ("-n" in argv) or (len(argv) == 1):
run(False)
elif "-t" in argv:
test()
else:
usage()

Es gibt folgende optionen

-b für's benchen
-t für's testen
-c berechnet 9^(9^9) im normalen Modus
-n berechnet 9^(9^9) im multithread Modus, default


Und noch ein kleiner Benchmark :D
Zeit zur Benechung von 9^5000000 (5 Millionen)
[...]


time for python power: 9.91100001335 seconds
time for optimized multiplication power: 18.0290000439 seconds
time for concurrent multiplication power: 18.0360000134 seconds
optimized multiplication power was correct
concurrent multiplication power was correct

Interessant... wie aus ~10 Minuten auf einem P4 mit Python 2.3 unter Windows XP nur 45 Sekunden auf einem i5-4690K mit Python 2.7.8 unter Win10 wurde :biggrin:. Hätte mit mehr als nur ~15x schneller erwartet. Alle 4 Kerne wurden auch ausgelastet, allerdings nur zu 50%.

Aber schon cool, wenn man solche alten Leichen im Forum findet, bei denen man sich früher gefragt hat "Wie schnell würde wohl in 10 Jahren eine CPU den Code ausführen?" :biggrin: Und nun weiß man es :freak:

PHuV
2016-06-30, 14:50:48
Die Links von den exes sind ja lange weg, zum Glück heb ich allen Mist immer auf. :freak: Da konnte ich doch glatt nicht wiederstehen, daß Ding nochmal zu starten.

Bei mir mit nem i7-6700k hat es auch gerade mal 19 Sekunden gebraucht. Von Raw nach Text in einer RamDisk (!) 13 Minuten! :confused:

Backe
2016-11-29, 20:05:30
Die Links von den exes sind ja lange weg, zum Glück heb ich allen Mist immer auf. :freak: Da konnte ich doch glatt nicht wiederstehen, daß Ding nochmal zu starten.

Bei mir mit nem i7-6700k hat es auch gerade mal 19 Sekunden gebraucht. Von Raw nach Text in einer RamDisk (!) 13 Minuten! :confused:

Ja, das ist seltsam:

$ clang -O3 -o 999 999.c -I/usr/local/include -L/usr/local/lib/ -lgmp
[backe:~/temp] $ ./999
computing 9^9^9 ... done
saving raw data... done
formatted raw data... done
[backe:~/temp] [B]7m13s $


Auf i7-4870HQ unter macOS Sierra. Das Berechnung hat ca. 25 Sekunden gedauert.

Ganon
2016-11-29, 23:27:08
Neuere GMP-Version, besserer Compiler. Werte nicht vergleichbar :D

i7-2600S@2.80GHz @ ArchLinux

$ time ./999
computing 9^9^9 ... done
saving raw data... done
formatted raw data... done

real 2m51,152s
user 2m49,813s
sys 0m1,290s


und Nachtest auf meinem Notebook:
i7-4750HQ@2.00GHz

real 2m18,289s
user 2m17,607s
sys 0m0,667s

Gast
2016-12-03, 00:58:54
ich würde das auch gerne ausprobieren - bin jedoch kein programmierer.... wie kann ich den code schnell compilieren?

danke vorab :)

Backe
2016-12-03, 14:59:27
ich würde das auch gerne ausprobieren - bin jedoch kein programmierer.... wie kann ich den code schnell compilieren?

danke vorab :)

Für welches Betriebssystem?

gravitino
2017-01-14, 00:53:29
[delete plz]

gravitino
2017-01-14, 02:03:02
In der Theorie ja, aber leider kannst du das in der GPU nicht abbilden.
Bei max 64 Bit ist Schluß.

Eine richtige CPU aber ist flexibel genug, so daß du die Berechnung anders realisieren kannst, z.B. nicht mit der typischen Integer Methode sondern z.b. mit Strings.

Weil es auf Graphikkarten ja keine Arrays gibt und NVLabs auf github keine big integer library hat...

https://github.com/NVlabs/xmp