The easiest and shortest way to compute Fibonacci's numbers is a 40-position lookup table. The worst possible algorithm is recursive. It's only use is, of course, for benchmarking (or for filling the lookuptable).
The Forth FIB benchmark shows the quality of your compiler's integer code as compared to what an optimizing "C" compiler would give you. Results for a large number of C compilers on a variety of systems are available in the .tbl file.
Do not overestimate the importance of good FIB performance. For native code compilers the importance of small call/threading overhead is usually small because they inline so much.
FORTH> main Fibonacci Benchmark The 40'th Fibonacci Number is: 102334155 Run Time (sec) = 22.451 okThe result for the Athlon (only 4 times faster) shows that iForth is not performing optimally here. The problem is iForth's emulated return stack (most other Forths emulate the data stack and use the machine hardware stack as the Forth return stack). In iForth recursive procedures should do more work than just a few simple instructions.
FORTH> main Fibonacci Benchmark The 40'th Fibonacci Number is: 102334155 Run Time (sec) = 5.333 ok
The FIB result puts iForth in the following company (fib.tbl):
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<( fib(40) )>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> System OS CPU/FPU CPU Run Time REF (MHz) (seconds) ### ---------------------- -------------- ------------ ----- --------- --- --- ---------------------------------------------------------------------- AMD Athlon Windows 2000 Athlon 900 5.333 --- ---------------------------------------------------------------------- 001 Dell XPS Pro 200n NT 3.51 Pentium Pro 200 12.680 2 002 Brett Station ATX Linux 2.0.0 Pentium Pro 180 17.830 8 003 SGI Origin 200 Irix 6.4 MIPS R10000 180 20.467 6 004 HP 9000/J210XC HP-UX 10.20 PA7200_2CPU 120 21.35 9 --- ---------------------------------------------------------------------- P54C NT 4.0 Pentium 166 22.451 --- ---------------------------------------------------------------------- 005 SGI O2 Irix 6.3 MIPS R10000 175 24.041 3 006 SGI Indy Irix 6.2 MIPS R5000 150 25.301 6 007 HP 9000/712 HP-UX 10.20 HP-PA7100LC 100 25.730 9 008 Acorn RiscPC 610 RiscOS 3.7 SA-110 202 25.78 11 009 SGI Challenge S Irix 6.2 MIPS R4400 200 26.620 4 010 Escom P100 Win95/DOS Pentium 100 27.440 2 011 SGI O2 Irix 6.3 MIPS R10000 175 28.468 3 012 Acorn RiscPC RiscOS V 3.70 SA-110 200 28.840 12 013 AMD K5-PR133 Windows 95 AMD K5-PR133 100 29.380 5 014 SGI Onyx Irix 6.2 MIPS R8000 75 29.202 7 015 IBM RS/6000 25E AIX 3.2.5 PPC601 66 30.20 10free counter