Hello, Guest the thread was viewed3.1k times and contains 50 replies

last post from enthusi at the

Schnelle Fakultätsberechnung

    Irgendwann wurde im 64'er ein Programm veröffentlicht, mit dem man die Fakultät von 10000 berechnen konnte. Das Programm rechnete allerdings, wenn ich mich recht erinnere, mehrere Tage. Das hatte ich damals zum Anlass genommen, selber so ein Programm zu schreiben. Meins benötigt nur 11 Stunden 17 Minuten und 42 Sekunden (ich hatte das aber nie an die 64'er geschickt). In den nachfolgenden Ausgaben kamen immer mal neue, schnellere Programme raus. Wobei ich keine Ahnung mehr habe, wie schnell die am Ende waren. Was aber an meinem Programm bemerkenswert ist: Es nutzt den BCD-Modus des Prozessors. :D


    Nach dem Laden mit ,8,1 wird das Programm mit SYS49152,n+1 gestartet um die Fakultät von n zu berechnen. Oben links auf dem Bildschirm wird mitgezählt, wie weit das Programm bereits ist. Am Ende befindet sich die Zahl im Speicher ab $0800 in Little-Endian-BCD, mit einem HEX-Monitor also gut auslesbar. Im Anhang zudem auch der Quellcode im Hypra-Ass-Format.

    Quote from FRauANtje

    Ich gestehe, dass ich von diesem Dezimal-Modus das erste mal höre...

    Spannend.

    Was ist der Grund, Fakultäten in BCD zu berechnen?

    Man muss das Ergebnis nicht mehr umrechnen. Bei einer Zahl, die die Hälfte des Speichers des C64 einnimmt, wäre das sicherlich ein ziemlicher Aufwand gewesen.

    Quote from FRauANtje

    Der rechnet also alle Stellen exakt aus? Taschenrechner gingen früher nur bis 69!. Und dann sollen die auch nur angenähert haben, was aber eh egal war, weil man eh nur die ersten acht Stellen + die E-Notation sah.

    Ja, das ist ganz exakt. Allerdings ist mir noch unklar, was man damit anfangen kann. ^^

    Ich kenne lediglich ein Programm aus der 64'er, das in der Lage ist, Fakultäten so genau wie aus dem Taschenrechner zu berechnen, allerdings auch wesentlich größere als es bspw. der Windows-Rechner kann, und das in Sekundenschnelle.


    Ein Programm mit vielen Nachkommastellen, da kenne ich nur Division2000, das auf 2000 Stellen genau dividieren kann.

    Quote from Hoogo
    Quote from FRauANtje

    Wir hatten mal bei ner mathe-plympiade die frage, wieviele Nullen 99! am ende hat :)

    Aber das konnte man noch logisch lösen - also ohne ausrechnen

    Display Spoiler

    Du hast vergessen, dass bei 25, 50 und 75 noch je eine zusätzliche 5 drin ist. 2en hat man ja genug.

    Quote from flyppo
    Quote from berni

    Ja, das ist ganz exakt. Allerdings ist mir noch unklar, was man damit anfangen kann.

    Mir auch, wozu benötigt man Fakultätsrechnung?

    Es gibt schon zahlreiche sinnvolle Anwendungen der Fakultätsrechnung. Was ich meinte, war die genauen Ziffern in Dezimaldarstellung. Da hat man eher nichts davon. Meist nutzt man Fakultätsrechnung eher in multiplikativen Kontexten ohne die Zahlen explizit auszurechnen; oder alternativ benötigt man nur die Größenordnung für eine Abschätzung. Aber da braucht man halt auch nicht die genauen Ziffern.

    Quote from Krill
    Quote from berni

    Was aber an meinem Programm bemerkenswert ist: Es nutzt den BCD-Modus des Prozessors. :D

    diesen Modus hielt ich bisher für reinste Transistorverschwendung. Jetzt nur noch reine. ;)

    Ich könnte mir noch vorstellen, dass er für das Handling der Echtzeituhren in den CIAs irgendwie von Bedeutung sein könnte. Die benutzen ja auch die BCD-Darstellung. Aber ansonsten ist mir bislang auch keine Idee gekommen, wo man den sonst noch brauchen könnte...

    Quote from flowerking

    Der Windows 10 Rechner kann immerhin 3248! berechnen, was 1,9736342530860425312047080034031e+9997 ergibt.

    Mit meinen Vorurteilen gegenüber Windows hätte ich ja jetzt vermutet, dass nur die ersten Ziffern stimmen, aber da sind tatsächlich alle richtig. Hier die exakte Zahl:

    Berechnet habe ich das mit bc unter Linux im Bruchteil einer Sekunde (10000! dauert damit übrigens etwa eine Sekunde):

    Code
    1. define fak(n) { if (n==1) return 1 else return n*fak(n-1); }
    2. fak(3248)

    Und der VICE im Warp-Modus mit meinem Programm hat es jetzt auch gleich raus... Moment... Dumdideldumm... Gleich, gleich... Ja, jetzt: Es ist das selbe Ergebnis! Hurra! :thumbsup:

    Quote from berni

    Du hast vergessen, dass bei 25, 50 und 75 noch je eine zusätzliche 5 drin ist. 2en hat man ja genug.

    Du meinst also, dass bei der Multiplikation mit 25, 50 und 75 je eine zusätzliche Null am Ende entsteht? Kannst Du mir das mal erkären? Ich komm grad nicht drauf, wieso das so sein sollte. *denk*

    Quote from FRauANtje
    Quote from berni

    Du hast vergessen, dass bei 25, 50 und 75 noch je eine zusätzliche 5 drin ist. 2en hat man ja genug.

    Du meinst also, dass bei der Multiplikation mit 25, 50 und 75 je eine zusätzliche Null am Ende entsteht? Kannst Du mir das mal erkären? Ich komm grad nicht drauf, wieso das so sein sollte. *denk*

    Schau dir mal die Primfaktorzerlegung von n! an: n! = 2^a * 3^b * 5^c * 7^d * ... Jede Null am Ende dieser Zahl benötigt eine 2 und eine 5 in dieser Zerlegung. Die Anzahl der 0en am Ende der Zahl ist also genau das Minimum von a und c.


    Da a bei einer Fakultät viel größer ist als c, muss man einfach nur c ausrechnen, um die Anzahl der 0en am Ende zu berechnen: Bei jeder durch 5 teilbaren Zahl kommt hier eins hinzu, bei jeder durch 5^2=25 teilbaren kommt nochmal eins dazu, bei jeder durch 5^3=125 teilbaren nochmal eins und so weiter. Damit kann man die Nullen von 99 leicht ausrechnen. 19 Zahlen, die kleiner oder gleich 99 sind (einfach 99/5, abgerundet), sind durch 5 teilbar; 3 weitere sind durch 25 teilbar (eben die drei, die ich oben erwähnt habe) und durch 125 sind keine mehr teilbar, genau wie durch alle größeren 5er-Potenzen. Damit ist die Anzahl der Nullen von 99! = 19+3.

    Ich hab noch ein bisschen gegrübelt, wie man Fakultät schnell berechnen könnte.

    Zumindest die Anzahl der 00 am Ende würde ja Multiplikationen sparen. Oder alle Primfaktoren 2 könnten entfernt werden, wenn man binär rechnet.

    Ich hatte da auch noch den Gedanken, dass man erstmal alle Primfaktoren sammeln und neu zusammenstellen könnte. Könnte auf Prozessoren mit Mul-Befehl nützlich sein, aber ich sehe grad nicht, wo das auf dem C64 nützlich wäre.