Fast Fibbing
Vector 3:4, page 120
The text of this article is not yet online. No complete scan of this issue has been found. The only copy found, on vector.org.uk, is damaged: its page images are lost, but the text machine-read from them survives, shown below (help find a scan).
Unedited OCR text, machine-read from a scan now lost: it contains errors, and its APL is wrong. Shown for searching.
VECTOR VoL3 No.4
More on F a s t Fibbing”
by Joseph de Kerf
In a previous issue of VECTOR (see ref 1), John Sullivan compares the Fibonacci function FIB], based on the recurrence relation: ¥ RePIBL N 2 [2] +(¥>pReR,+/2+R) /OLC v with the loop-eliminating Fibonacci function FIB2: Uo RePIB2 WN (17 ReLO.54(4R)™((0.5%1 +R) 4) (0. 521 -Re540.5 ane ° The defined function FIB2 is based on the well-known golden section formula: = +t 1, i=¥5," a = Te! ar
The second term of the formula is very small, even for lower values of n, and converges to zero. By setting: n a, = de UH) v5 ° 2 we get: t+ 3)" 2
u= 0.7236 1.1708
3.0652 4.9597 8.0249 12.9846 21.0095
33.9941 10 55.0036 etc...
Rounding off to integers gives the exact values for the Fibonacci Numbers. This means that we can replace FIB2 by the Fibonacci Function Mark 3: V RFIB3 WN ' O.54(2R)x (0. 5x1 +540. 504 v n=
WMUDNAWHe
Apart from some overhead, the execution of FIB3 versus FIB2 is speeded up by an extra factor of about 2.
This trick is well known in the literature (see e.g. ref 2). So, to the recommendation A l w a y s do the systems analysis before you write the program”, we should add C o n s u l t the literature before you do the systems analysis.” References. 1. Fast Fibbing, by John Sullivan, VECTOR 3.1, July 86, pp 113-114 2. Motivating Arrays in Teaching APL, by Garth H Foster, Proc. of Sth International APL Users’ Conference, Toronto, May 1973, pp 3-1/3-8. Theme: APL applications in Education and Business. Printed by Canadian Printco Ltd., Toronto, 1973.
120