@database FastFibo @remark $VER: FastFibo V1.1 @node main "FastFibo" FastFibo V1.1 Bitte Sprache auswählen / Please select language: @{"Deutsch" link g_main} @{"English" link e_main} @endnode @node g_main "FastFibo" FastFibo ist ein kleines Programm, um die Fibonacci- und die ver- wandten Lucaszahlen zu berechen. Ich programmierte es, nachdem ich im Aminet ein ähnliches Programm von JIPSoft (Joona I Palaste) fand. Tut mir leid, Joona, aber dein Programm ist wirklich langsam und auch etwas groß für ein solche einfache Berechnung. Weiter gehts mit: - @{"Benutzung" link "g_usage"} - @{"Voraussetzungen" link "g_require"} - @{"Rechenzeit" link "g_timing"} - @{"Literatur" link "g_literature"} - @{"Geschichte" link "g_history"} - @{"Autor" link "g_author"} - @{"Disclaimer" link "g_disclaimer"} @{"Zurück zum Start" link main} @endnode @node e_main "FastFibo" FastFibo is a small program for calculating Fibonacci's numbers and the related Lucas numbers. I programmed it after receiving a similar program by JIPSoft (Joona I Palaste) via the Aminet. Sorry Joona, but your program is really slow and a little to big for such a simple calculation. Further info: - @{"Usage " link "e_usage"} - @{"Requirements" link "e_require"} - @{"Timing " link "e_timing"} - @{"Literature" link "e_literature"} - @{"History " link "e_history"} - @{"Author " link "e_author"} - @{"Disclaimer " link "e_disclaimer"} @{"Back to main" link main} @endnode @node g_usage "Benutzung" FastFibo ist ein kleines CLI-Programm. Die Befehlsschablone ist recht einfach: FastFibo NUMBER/A/N,LUCAS/S,NO=NOOUTPUT/S Man muß das Argument für die Fibonaccifunktion angeben. Diese Zahl muß positiv sein (siehe auch @{"Voraussetzungen" link "g_require"}). Der Switch LUCAS bewirkt die Berechnung von Lucas-Zahlen, ansonsten werden Fibonacci-Zahlen berechnet. Mit NOOUTPUT kann die Ausgabe der berechneten Fibonaccizahl unterdrückt werden. Dann erhält man nur die benötigte Zeit und die Anzahl der berechneten Stellen als Ausgabe. Alle Ausgaben erfolgen ins Shellfenster. Um die Ergebnisse zu speichern, muß man also die Redirection benutzen. Neben der berechneten Zahl wird auch die dafür benötigte Zeit angegeben. Die Berechnung kann bei großen Argumenten recht lange dauern (siehe auch @{"Timing" link "g_timing"}). @{"Weiter" LINK g_require} @endnode @node e_usage "Usage" FastFibo is a small CLI-program. It has a simple template: FastFibo NUMBER/A/N,LUCAS/S,NO=NOOUTPUT/S You have to supply the number parameter, which is the argument for the Fibonacci-function. That number has to be positive, for other things see @{"Requirements" link "e_require"}. The switch LUCAS forces the calculation of Lucas numbers instead of Fibonacci numbers. With NOOUTPUT you can disable the output of the calculated number. FastFibo then just gives you the time needed for the calculation and the number of calculated digits. All output is written to the console (shell-window), for saving the results you have to use the redirection option. When FastFibo is running, there is no progress indication (yet), so prepare for long execution times on big numbers. (see also @{"Timing" link "e_timing"}) @{"Next" LINK e_require} @endnode @node g_require "Voraussetzungen" FastFibo benötigt: - einen Amiga® mit Workbench 2.0 oder besser - einen 68020+ Prozessor (das ist wirklich unterstes Minimum heutzutage) - keine FPU oder externe Library - etwas Speicher für große Zahlen (Man benötigt ca. NUMBER/4 Bytes für die Berechnung. Auf meinem Amiga mit 16Mb FAST-Ram reicht das für NUMBER=67*10^6. Allerdings würde FastFibo dann auch mehr als 2 Jahre lang rechnen.) @{"Weiter" LINK g_timing} @endnode @node e_require "Requirements" FastFibo requires: - an Amiga® computer with Workbench 2.0 or above - a 68020 or better processor (thats really a minimum today) - no FPU or any third party libraries - some memory for big numbers (You need approx. NUMBER/4 bytes for the calculation. On my Amiga with 16Mb FAST-Ram that should be enough for NUMBER=67*10^6. But FastFibo would need over 2 years for that NUMBER.) @{"Next" LINK e_timing} @endnode @node g_timing "Rechenzeit" Die Berechnung von Fibonaccizahlen ist eigentlich eine einfache Aufgabe: addiere zwei Zahlen, um die nächste in der Reihe zu erhalten. Aber trotzdem muß man die Berechnung "von Hand" durchführen: der 68K-Prozessor (wie so viele andere auch) kann nur mit maximal 32-bit-Integers rechen. Das ergibt gerade mal 10 Dezimalstellen und erlaubt nur ein maximales NUMBER-Argument von 50! Man könnte natürlich eine FPU zu Hilfe nehmen, aber auch diese hat maximal 64 Bit Auflösung (ext float, nicht im IEEE-Standard!). Damit kommt man dann bis NUMBER~=90. Nicht gerade toll. Deshalb muß man Strings statt Zahlen benutzen. Für FastFibo verwende ich einen speziellen Befehl des Prozessors: die abcd-Instruktion. ABCD steht dabei für Add BCD-packed Decimal with Extend. Damit kann man Zahlen mit beliebiger Stellenzahl addieren (wenn man genug Ram und Zeit hat). Weiterhin ist der verwendete Algorithmus wichtig. Es gibt mehrere Wege, um Fibonaccizahlen zu berechnen: eine "direkte" Formel, rekursive Algorithmen und die iterative Berechnung. Ich benutze hier die iterative Berechnung, weil sie so einfach zu programmieren ist. Der iterative Algorithmus ist von der Ordung(n*n). Das bedeutet, das sich die Berechnungszeit mit doppelter NUMBER vervierfacht. Auf meinem Amiga (A500, 030+882/50 MHz, 16 MB Ram) erreicht FastFibo folgende Werte: NUMBER Rechenzeit Dezimalstellen [s] 4782 0,4 1000 9567 1,4 2000 10000 1,5 2090 14352 3,2 3000 19137 5,6 4000 20000 6,1 4180 50000 38,0 10450 100000 153,6 20899 200000 611,6 41798 400000 2433,3 83595 526345 4205,6 110000 Mit dieser Tabelle kann man die benötigte Rechenzeit leicht abschätzen: zeit = constant*NUMBER*NUMBER Für meinen Amiga beträgt constant=15,2 ns. Für andere Computer muß die Konstante entsprechend angepaßt werden. Für WinUAE auf einem Intel P166 MMX ergibt sich constant=85 ns, ein 68030/33 erreicht constant=22,3 ns. Die Anzahl der resultierenden Stellen ergibt sich aus: Stellen = NUMBER/4,7845 Wenn man die Ergebnisdateien zum Abspeichern komprimieren will, empfehle ich einen Huffman-Komprimierer (z.B. xpkHFMN). Diese komprimieren diese Art von Dateien besser als irgendwelche ZIP-Varianten (xpkGZIP...). Das liegt daran, daß nur ca. 32 verschiedene Zeichen in der Datei vorkommen und nur 12 davon wirklich oft (0..9,".",Linefeed). @{"Weiter" LINK g_literature} @endnode @node e_timing "Timing" The calculation of Fibonacci numbers is a rather simple job: just add two numbers to get the next number. But you have to do this "by hand": the 68k processor (and others) can only handle 32 bit integers (in C: long), which equals 10 decimal digits. With long integers you would end with a maximal NUMBER of 50! So you could reply: use floating point capabilities. But there you only have maximal 64 bits of resolution (ext float, not IEEE-standard), which gives you circa 19 decimal digits. Gee, you would end up with a maximal NUMBER of 90. Thats not so much. So you have to use strings instead of normal variables. For this little program I use a special instruction of the 68k-processor: the abcd-instruction. Abcd is the acronym for Add BCD-packed Decimal with Extend. This instruction makes it possible to add arbitralily long numbers (if you have enough ram and time). Another important fact is the kind of calculation you use. There are many ways to calculate a Fibonacci number: a ´direct´ formula, a recursive algorithm or the iterative way. I use the iterative way, it`s easy to program. The recur- sive algorithm requires a good stack handling, which is not so easy for big numbers. The iterative algorithm is of Order(n*n). This means, if you double the argument number, you need four times longer to calculate the result. On my computer (A500, 030+882/50 MHz, 16 MB Ram) FastFibo gives this results: NUMBER calc time # of digits [s] 4782 0.4 1000 9567 1.4 2000 10000 1.5 2090 14352 3.2 3000 19137 5.6 4000 20000 6.1 4180 50000 38.0 10450 100000 153.6 20899 200000 611.6 41798 400000 2433.3 83595 526345 4205.6 110000 With this table you can easily estimate the time needed for any NUMBER: time = constant*NUMBER*NUMBER constant is 15.2 ns for my Amiga. For other computers you have to set the constant accordingly. For WinUAE on an Intel P166 MMX constant is 85 ns, a 68030/33 reaches constant=22.3 ns. The number of digits can be estimated with: #digits = NUMBER/4.7845 If you want to compress the resulting files for storage I recommend a Huffman-like compressor (e.g. xpkHFMN). They compress this type of file better than any ZIP-variant (GZIP, LZX, ...).You only have ~32 different characters in the file and only 12 of them are used often (0..9,".",Linefeed), but in a more or less random pattern. @{"Next" LINK e_literature} @endnode @node g_literature "Literatur" Für alle Interessierten mit Internetzugang empfehle ich folgende Website: http://www.ee.surrey.ac.uk/Personal/R.Knott/Fibonacci/fib.html Wirklich aufschlußreich! @{"Weiter" LINK g_history} @endnode @node e_literature "Literatur" For all you interested I recommend this website: http://www.ee.surrey.ac.uk/Personal/R.Knott/Fibonacci/fib.html All you need to know! @{"Next" LINK e_history} @endnode @node g_history "Geschichte" v1.0 ( 1. April 1999) Erste Aminet-Version. v1.1 (27. April 1999) Neu: Berechnung von Lucas-Zahlen @{"Weiter" LINK g_author} @endnode @node e_history "History" v1.0 ( 1. April 1999) First public release. v1.1 (27. April 1999) New: Calculation of Lucas-numbers @{"Next" LINK e_author} @endnode @node g_author "Autor" Ich freue mich über jede Anmerkung und jeden Vorschlag. Bugmeldungen sind zwar kein Grund zur Freude, werden aber trotzdem bearbeitet. Gerd Wieczorek SMail: Berliner Str.1 14959 Trebbin BRD EMail: gwieifjc@sp.zrz.tu-berlin.de (Mein Studium endet im Sommer, kontaktet mich besser schnell!) @{"Weiter" LINK g_disclaimer} @endnode @node e_author "Author" If you have any questions, remarks, suggestions or even bug reports please let me know. Gerd Wieczorek SMail: Berliner Str.1 14959 Trebbin BRD EMail: gwieifjc@sp.zrz.tu-berlin.de (My studies end in summer, so better contact fast!) @{"Next" LINK e_disclaimer} @endnode @node g_disclaimer "Disclaimer" Dieses Programm ist Freeware. Über Geschenke (fast) jeder Art freut sich der @{"Autor" link g_author} trotzdem. Es gelten die allgemein üblichen Hinweise: Für Schäden jeder Art, die sich aus der Benutzung von FastFibo ergeben, ist der Autor nicht haftbar... @{"Zurück" link g_main} @endnode @node e_disclaimer "Disclaimer" @{b}Disclaimer@{ub} ---------- This program is freeware, but gifts of (nearly) all kinds are welcome by the @{"author" LINK e_author}. Also you should email me your results (only time and number of digits, not the Fibonacci number!). And of course with your computer configuration. The entire risk as to the use of the program and the information presented is assumed by the user. In no event will I be liable for any damage resulting from any claim arising of the use of the program or the information presented herein, even if I have been advised of the possibilities of such damages. @{"Back to Contents" LINK e_main} @endnode