フィボナッチルーカス数の同時再帰CLP（FD）の可能性

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 

従来プロローグrealizationすでにnからFnまで働いています。これは高速再帰を維持すると同時に双方向的にするCLP（FD）プログラムに変えることができますか？たとえば、Fn = 377のインデックスnを計算しますか？はいの場合はどうですか？なぜそうならないのでしょうか？

bye

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はインスタンス化されていません。
はここでLinuxでSWI Prologの7.1.33で実行するタイミング、複合クエリの例、です：

?- 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で一時的に存在していました。