Friday Fun: Generating Fibonacci Numbers with GNU Make

Nobody would ever claim that GNU Make is a general purpose programming language, but with a little work, we can coerce it into generating Fibonacci numbers for us. Why bother? Because we can .

First, let me give a simple demonstration. Here's the makefile:

16:=x x x x x x x x x x x x x x x x
input_int:=$(foreach a,$(16),$(foreach b,$(16),$(foreach c,$(16),$(16))))
decode=$(words $1)
encode=$(wordlist 1,$1,$(input_int))
decr=$(wordlist 2,$(words $1),$1)
decr2=$(wordlist 3,$(words $1),$1)
eq=$(filter $(words $1),$(words $2))
g0:=
g1:=x

fib=$(if $(filter-out undefined,$(origin f$1)),
$(f$1),
$(if $(call eq,$1,$(g0)),
$(eval f$1:=$(g0))$(g0),
$(if $(call eq,$1,$(g1)),
$(eval f$1:=$(g1))$(g1),
$(eval f$1:=$(call fib,$(call decr2,$1)) $(call fib,$(call decr,$1)))$(f$1))))

print=$(if $1,
$(call print,$(call decr,$1))$(info $(call decode,$1): $(call decode,$(f$1))),
$(info 0: 0))

:
@:$(if x$(call fib,$(call encode,$@)),$(call print,$(call encode,$@)),)

Invoke it with a single argument, the length of the sequence to generate:

ericm@chester:~/blog/fibonacci$ gmake 10
0: 0
1: 1
2: 1
3: 2
4: 3
5: 5
6: 8
7: 13
8: 21
9: 34
10: 55

Nifty!
Now, although this demonstration is not especially practical, it does make use of a few advanced gmake concepts: arithmetic; caching dynamically generated variables; and recursive functions.

Arithmetic

None of this would be possible without support for arithmetic operations. Here's a brief explanation of how this works (for more details, the Mr. Make article Learning GNU Make Functions with Arithmetic ): we use strings of space-separated x characters to represent values; for example, the number five is represented as x x x x x . To add numbers together, we concatenate the string representations, and to subtract, we trim the appropriate number of x 's from the string. To convert from the string representation to the numeric value, we just count the number of x 's in the string, using the $(words) builtin, and finally, to convert from the numeric value to the string representation we extract the appropriate number of x 's from a canonical string that just has a series of several thousand x 's.
This is inefficient, in both memory and time. The representation of a number requires double the value in bytes, so the number 50,000 requires 100,000 bytes of storage. Converting to a numeric value from the string representation is a linear operation that scales with the magnitude of the value -- the bigger the value, the longer the conversion takes. These factors together limit the range of numbers that you can practically work with using this scheme, although it works fine for small values (up to around 10,000 or so). For the Fibonacci makefile, the inefficiencies mean that we can only generate the sequence out to about the 40th value. At that point, gmake has already sucked up 1.4 GB of memory!

Caching dynamic values

Because it is time-consuming to compute Fibonacci numbers this way, we'd like to cache the results, so we don't ever duplicate work. But the values are dynamically generated. For that matter, the variables themselves must be dynamically generated — we don't know beforehand which Fibonacci numbers we're going to have to compute. So how do you dynamically generate variables and cache their values in gmake? With $(eval) . You can read all about it in another Mr. Make article, $(eval) and macro caching . In our Fibonacci makefile, you can see that as we determine each Fibonacci number, we invoke $(eval) to save the value. The fib function is then setup to first check for the existence of a cached value and only bother with the computation if there is no cache entry.

Recursive functions

The Fibonacci sequence is defined recursively as f(n) = f(n - 1) + f(n - 2) , so naturally we use a recursive function in our implementation. The fib function takes one argument, the index of the Fibonacci number to compute, encoded using the scheme described above. After checking the cache, fib checks if the current index is either zero or one. By convention, these Fibonacci numbers are defined to have value zero and one, respectively, so there is no need to compute them. This also serves as a terminating condition so we don't recurse infinitely.
If the current index is neither zero nor one, then fib calls itself recursively twice, to compute the two preceding Fibonacci values. The recursive results are combined, cached, and returned as the overall result of the fib function itself.

Conclusion

I'm surprised at how quickly gmake computes the sequence, actually. On my laptop, gmake computes the first 30 values in a fraction of a second. After that the inefficiencies in the arithmetic operations really come into play: it takes about 3.5 seconds to compute 35 values, and 25 seconds to compute 39 values. Still, considering the limitations of the environment, I think it's impressive that it works at all.