🚀 go-pugleaf

On Wed, 16 Dec 1998, Markus Kuhn wrote:
>In Markus.Wurdak@t-online.de (Markus Wurdak) writes:
>|> Ich habe folgendes Problem: Ich will ein Programm schreiben (Turbo
>|> Pascal), welches mir die Zahl "9 hoch 9 hoch 9", also "9 hoch 387420489"
>|> berechnet. Da diese Zahl (ca. 387420489 Ziffern) viel zu gro� f�r eine
>|> Variable ist, h�tte ich folgende Fragen:
>|> 
>Du berechnest 9^2, 9^4, 9^8, 9^16, 9^32, 9^64, usw. durch
>fortw�hrendes Quadrieren. Du stellst 387420489 als Binaerzahl
>dar, und multipliziert die 9^(2^i) f�r die die i-te Binaerziffer
>des Exponenten 1 ist. Das ist der �bliche Square&Multiply
>Algorithmus.

Und summierst das Ergebnis auf ...

>
>Literatur: Donald E. Knuth, The Art of Computer Programming,
>Volume II, Seminumerical Algorithms.
>
Gut, aber ganz so trivial ist das ja nun auch nicht ... 387420489 besteht
naehmlich aus 29 Bit. 
Das heisst man muss immernoch mit 9^(2^28) multiplizieren und das ist auch eine
Zahl mit 256152524 Stellen. Dafuer sind es somit nur 29 Multiplikationen mit
sehr grossen Zahlen.
Und ich weis nicht ob das Quadrieren so grosser Zahlen ohne weitere
Komplikationen moeglich ist ... ich stell mir gerade (9^(2^27))^2 vor :-}
Man multipliziere mit der ersten Stelle merke sich das Ergebnis, multipliziere
mit der zweiten Stelle, summiere auf u.s.w. ... da ist man auch nicht schneller
fertig als wenn man das gleich "von Hand" macht.

Man kann das Byte natuerlich voll ausnutzen und so 369693100 / 256 gleich
1444114 Stellen abspeichern. Na damit laesst sich doch schon rechnen.
Natuerlich rechnet man am Ende mit 'int', das erspart unnoetige Multiplikationen
und Additionen.

Falls eine grobe Implementierung gewuenscht ist, kann ich mir darueber ja
nochmal Gedanken machen ...

Danny
--
In einer Irrsinnigen Welt vern�nftig sein zu wollen, 
ist schon wieder ein Irrsinn f�r sich.
Voltaire