CLP(FD)-ying Simultaneous Recursion for Fibonacci Lukas Numbers Possible?

There are some instances where recursive predicates can be CLP(FD)-fied with the benefit that the predicate turns bidirectional. What are the limits of this method? For example can the following computation CLP(FD)-fied:

Fn: n-th Fibonacci Number
Ln: n-th Lucas Number (starting with 2)

By this doubling recursion step:

F2n = Fn*Ln
L2n = (5*Fn^2+Ln^2)//2

And this incrementing recursion step:

Fn+1 = (Fn+Ln)//2
Ln+1 = (5*Fn+Ln)//2

The traditional Prolog realization works already from n to Fn. Can this be turned into a CLP(FD) program preserving the fast recursion and at the same time making it bidirectionally, for example figuring out the index n for Fn=377? If yes how? If not why?

Bye

Yes, it can be done by constraining the values. You can also move the recursion to be tail recursion, although it's not required to get the solutions:

fibluc(0, 0, 2).
fibluc(1, 1, 1).
fibluc(N, F, L) :-
    N in 2..1000,        % Pick a reasonable value here for 1000
    [F, L] ins 1..sup,
    N rem 2 #= 1,
    M #= N-1,
    F #= (F1 + L1) // 2,
    L #= (5*F1 + L1) // 2,
    fibluc(M, F1, L1).
fibluc(N, F, L) :-
    N in 2..1000,        % Pick a reasonable value here for 1000
    [F, L] ins 1..sup,
    N rem 2 #= 0,
    M #= N // 2,
    F #= F1 * L1,
    L #= (5*F1*F1 + L1*L1) // 2,
    fibluc(M, F1, L1).

Will yield:

?- fibluc(10, X, Y).
X = 55,
Y = 123 ;
false.

?- fibluc(N, 55, Y).
N = 10,
Y = 123 ;
false.

?- fibluc(N, X, 123).
N = 10,
X = 55 ;
false.

?- fibluc(N, 55, 123).
N = 10 ;
false.

?- fibluc(N, 55, 125).
false.

?- fibluc(N, X, Y).
N = X, X = 0,
Y = 2 ;
N = X, X = Y, Y = 1 ;
N = 3,
X = 2,
Y = 4 ;
N = 7,
X = 13,
Y = 29 ;
N = 15,
X = 610,
Y = 1364 ;
N = 31,
X = 1346269,
Y = 3010349 ;
N = 63,
X = 6557470319842,
Y = 14662949395604 ;
...

This could be modified to generate results for increasing values of N when N is uninstantiated.
Here's a timed, compound query example, run in SWI Prolog 7.1.33 under Linux:

?- time((fibluc(100, X, Y), fibluc(N, X, Z))).
% 11,337,988 inferences, 3.092 CPU in 3.100 seconds (100% CPU, 3666357 Lips)
X = 354224848179261915075,
Y = Z, Z = 792070839848372253127,
N = 100 ;
% 1,593,620 inferences, 0.466 CPU in 0.468 seconds (100% CPU, 3417800 Lips)
false.

?-

Using SWI Prolog 7.2.3 with the same code above and the same compound query, the code does go off for a very long time. I waited at least 15 minutes without termination. It's still running right now... I may check on it in the morning. :)

I did, however, re-arrange the above code to move the recursive call back to where the original code had it as follows:

fibluc(0, 0, 2).
fibluc(1, 1, 1).
fibluc(N, F, L) :-
    N in 2..1000,        % Pick a reasonable value here for 1000
    [F, L] ins 1..sup,
    N rem 2 #= 1,
    M #= N-1,
    fibluc(M, F1, L1),
    F #= (F1 + L1) // 2,
    L #= (5*F1 + L1) // 2.
fibluc(N, F, L) :-
    N in 2..1000,        % Pick a reasonable value here for 1000
    [F, L] ins 1..sup,
    N rem 2 #= 0,
    M #= N // 2,
    fibluc(M, F1, L1),
    F #= F1 * L1,
    L #= (5*F1*F1 + L1*L1) // 2.

In this case, the favorable results returned:

?- time((fibluc(100, X, Y), fibluc(N, X, Z))).
% 10,070,701 inferences, 3.216 CPU in 3.222 seconds (100% CPU, 3131849 Lips)
X = 354224848179261915075,
Y = Z, Z = 792070839848372253127,
N = 100 ;
% 1,415,320 inferences, 0.493 CPU in 0.496 seconds (100% CPU, 2868423 Lips)
false.

Note that the performance of CLP(FD) can be vastly different between different Prolog interpreters. It's interesting that, with SWI Prolog, the ability to handle the tail recursive case was temporarily there with version 7.1.33.

Recommended topics

Hot tags