@database FastFibo @remark $VER: FastFibo V1.4 @node main "FastFibo" FastFibo V1.4 Bitte Sprache auswählen / Please select language: @{"Deutsch" link g_main} @{"English" link e_main} Zur Benutzung dieses Guide-Files: Ich benutze gern und oft die Tastatur. Deshalb ist dieses Guide-File so ausgelegt, dass man es per Tastatur bequem durchlesen kann. Dies bedeutet, das zur Navigation die Cursortasten benutzt werden. Den gerade aktivierten Link kann man per Enter auswählen. Will man einen anderen Link auswählen, so geht dies mit der Tabulatortaste. Wenn man die Browse-Gadgets benutzt, landet man abwechselnd im deutschen und englischen Text! Using this guide: Normally I prefer using the keyboard instead of the mouse. So this guide is made for exploring it by keyboard. With Multiview you can navigate with the cursor keys. Selecting a link is done with Tab, entering the link by Return. If you use the browse-gadgets you alternatingly see the German and English text. @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. Mit Version 1.4 wurde FastFibo erneut schneller. FastFibo benötigt nun nur noch knapp 80% der Rechenzeit von V1.3. 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. With V1.4 FastFibo is even faster. Now FastFibo calculates numbers in less than 80% of the time V1.3 needed. 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 etwas weniger als NUMBER/5 Bytes für die Berechnung. Auf meinem Amiga mit 16Mb FAST-Ram reicht das für NUMBER=88*10^6. Allerdings würde FastFibo dann auch circa 2 Jahre lang rechnen.) - statt einem echten Amiga kann es auch WinUAE sein @{"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 (that's really a minimum today) - no FPU or any third party libraries - some memory for big numbers (You need less than NUMBER/5 bytes for the calculation. On my Amiga with 16Mb FAST-Ram that should be enough for NUMBER=88*10^6. But FastFibo would need about 2 years for that NUMBER.) - instead of a real Amiga you can use WinUAE too @{"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 V1.1 verwendete 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). Seit V1.3 wird stattdessen der normale add-Befehl benutzt. Dies erfordert zwar etwas mehr (Programmier-)Aufwand als der abcd-Befehl, ist dafür aber schneller. 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, dass 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] 10000 0,7 2090 20000 2,6 4180 50000 16,2 10450 100000 64,8 20899 200000 260,0 41798 300000 585,0 62697 400000 1039,0 83595 500000 1620,0 104495 526345 1799,0 110000 600000 2338,5 125393 700000 3183,6 146291 750000 3654,8 156741 800000 4158,5 167190 900000 5264,4 188089 1000000 6501,3 208988 Mit dieser Tabelle kann man die benötigte Rechenzeit leicht abschätzen: zeit = constant*NUMBER*NUMBER Für meinen Amiga beträgt constant=6,5 ns. Für andere Computer muß die Konstante entsprechend angepasst werden. Für WinUAE auf einem Athlon550 ergibt sich constant=10,5 ns, ein 68030/33 erreicht constant=9,8 ns. Die Anzahl der resultierenden Stellen ergibt sich aus: Stellen = NUMBER/4,7845 (Vorsicht Mathematik: 4,7845 ~= -1/log(phi); phi = Fib(n)/Fib(n+1) für n-> unendlich; phi = ½ (sqrt(5)-1), "Goldener Schnitt") 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 about 19 decimal digits. You would end up with a maximal NUMBER of 90. Thats not so much. So you have to use strings instead of normal variables. In V1.1 I used 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). Since V1.3 I use the normal add-instruction. This requires some more instructions, but is also faster than before. 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] 10000 0.7 2090 20000 2.6 4180 50000 16.2 10450 100000 64.8 20899 200000 260.0 41798 300000 585.0 62697 400000 1039.0 83595 500000 1620.0 104494 526345 1799.0 110000 600000 2338.5 125393 700000 3183.6 146291 750000 3654.8 156741 800000 4158.5 167190 900000 5264.4 188089 1000000 6501.3 208988 With this table you can easily estimate the time needed for any NUMBER: time = constant*NUMBER*NUMBER constant is 6.5 ns for my Amiga. For other computers you have to set the constant accordingly. For WinUAE on an Athlon 550 constant is 10.5 ns, a 68030/33 reaches constant=9.8 ns. The number of digits can be estimated with: #digits = NUMBER/4.7845 (mathematics: 4,7845 ~= -1/log(phi); phi = Fib(n)/Fib(n+1) for n-> infinity; phi = ½ (sqrt(5)-1), "Golden Ratio") 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 "Literature" 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" Version Datum Rechen Kommentar zeit 1.0 1. 4.1999 100% Erste Aminet-Version. 1.1 27. 4.1999 100% Berechnung von Lucas-Zahlen 1.2 16. 4.2000 100% interne Version Umstellung der Ausgabe von 4er- auf 3er-Gruppierung 1.3 9. 5 2000 55% schnellere Berechnung geringerer Speicherbedarf 1.4 30. 5 2000 43% schnellere Berechnung @{"Weiter" LINK g_author} @endnode @node e_history "History" version date calc. comment time 1.0 4/ 1/1999 100% First public release. 1.1 4/27/1999 100% Calculation of Lucas-numbers 1.2 4/16/2000 100% internal version changed output formatting from groups of 4 to groups of 3 digits 1.3 5/ 9/2000 55% faster calculation reduced memory usage 1.4 5/30/2000 43% faster calculation @{"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: wieczorek@mat.ee.tu-berlin.de @{"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: wieczorek@mat.ee.tu-berlin.de @{"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