CLP（FD）-ying同步遞推的斐波那契Lukas數可能嗎？

Question

有一些instances其中遞歸謂詞可以是CLP（FD） - 謂詞變爲雙向的好處。這種方法有什麼限制？例如可以如下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沒有實例。
這裏有一個定時，複合查詢例如，在SWI Prolog的33年7月1日在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分鐘，沒有終止。它現在仍在運行......我可能在早上檢查它。 :)

我沒有，但是，重新排列上面的代碼移動遞歸調用回哪裏原始代碼有它如下：

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. 

在這種情況下，有利的結果返回：

​​

請注意，CLP（FD）的性能在不同的Prolog解釋器之間會有很大差異。有趣的是，在SWI Prolog中，處理尾遞歸案件的能力暫時在7.1.33版本中出現。