CLP(FD)-ying 斐波那契卢卡斯数的同时递归可能吗？

Question

有一些 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)

通过这个加倍递归步骤：

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

这个递增的递归步骤：

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

传统的 Prolog realization 从 n 到 Fn 已经可以工作了。这可以变成一个 CLP(FD) 程序，保留快速递归并同时使其双向递归，例如计算 Fn=377 的索引 n 吗？如果是如何？如果不是为什么？

再见

Answer 1

是的，可以通过限制值来完成。您也可以将递归移动为尾递归，尽管它不是获得解决方案所必需的：

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).

将产生：

?- 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 ;
...

这可以修改为在 N 未实例化时生成增加 N 值的结果。
这是一个定时的复合查询示例，运行 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.

?-

使用具有上述相同代码和相同复合查询的 SWI Prolog 7.2.3，代码确实会运行很长时间。我等了至少 15 分钟才终止。现在还在运行ning...我可能会在早上查看。 :)

不过，我确实重新安排了上面的代码，将递归调用移回到原始代码的位置，如下所示：

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.

在这种情况下，有利的结果返回：

?- 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.

请注意，CLP(FD) 的性能在不同的 Prolog 解释器之间可能会有很大差异。有趣的是，对于 SWI Prolog，处理尾递归情况的能力在 7.1.33 版本中暂时存在。

CLP(FD)-ying 斐波那契卢卡斯数的同时递归可能吗？

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

prolog

clpfd