Download An Introductory Course on Constraint Logic Programming

3.4. FIBONACCI NUMBERS
39
Thirtynine elements may seem a lot for an accuracy of only 0.1, but if one thinks carefully,
the 40th element is 401 , and since the series itself returns 4e , the dierence among the 39th and
the 40th element is just 0.1 concerning the accuracy of the approximation, it is not really
meaningful, and should be looked mainly as an exercise of using CLP in innovative ways, not
possible in other languages.
Some primitives not yet explained are used in this example: abs/1 returns the absolute
value of a number. The ! sign forces Prolog IV (and any other Prolog or CLP language) to
stop after nding the rst answer to a query. We will return to them (especially to !) later.
Problem 3.7 There is some redundancy in this example. Two of the arguments perform
similar roles: the rst one counts the number of elements in the series still to be worked out,
and it thus goes from N to 0 the second one has the denominator of the fractions, and it goes
from 1 to N. The only reason for doing that is automatically calculating whether to add or
substract each element in the series by reversing the sign of the third argument. CLP can help
to have a simpler program: we can start at N1 and progress towards 11 , leaving undetermined
the sign of every element of the series, but reversing its sign, until the rst element is reached.
Write this program.
3.4 Fibonacci Numbers
The Fibonacci series is a classical problem in mathematics and computer science. It is usually
dened as:
F0 = 0
F1 = 1
Fn+2 = Fn+1 + Fn
I.e., the numbers of Fibonacci are 0, 1, 1, 2, 3, 5, 8, 13. . . It is easy to straightforwardly
translate it to a logical denition, mimicking each equation with a clause. The rst argument of the predicate is the index of the Fibonacci number, and the second argument is the
Fibonacci number itself. Note that there is an explicit check of the index in the last clause:
fib(0, 0).
fib(1, 1).
fib(N, F1+F2):gelin(N, 2),
fib(N-1, F1),
fib(N-2, F2).
There are two recursive calls in this case. This will be important later. As usual, queries
can be issued to nd out which number corresponds to a given index:
?- fib(10, F).
F = 55.
But, as in previous examples, other calls are possible, as, for example, nding out the
index of a Fibonacci number: