Prolog CLPFD で効率的な排他的論理和 (XOR) を実装しようとしています。これは、次のような単純な述語である必要があります。
xor(A, B, AxorB).
A、B、AxorBは自然数 (0 を含む) であり、 xorAxorBの結果です。A B
私の主な問題は効率です。まず、これらの数値をさらに処理/制約できる別々の部分に分割せずに XOR する方法を見つけることができませんでした。これらの数値を分割するプロセス (適切な制約を作成してから解決する) には、ある程度の処理が必要です。時間。第二に、以下の 2 番目のコードに示されている以外に、自然数で XOR 関数を「シミュレート」する効率的な方法を思いつくことができませんでした。
最初のコードから始めましょう。これは可能な最も単純な XOR 実装であり、1 ビット値 (0 と 1) に対してのみ機能します。
xor_1bit_values(A, B, AxorB) :-
AxorB #= (A + B) mod 2.
これを 1 より大きい数値に使用するには、数値をビットに分割する必要があります。
xor_number(A, B, Result, Bits) :-
Count is Bits - 1,
xor_number(A, B, Result, Count, 0).
xor_number(A, B, Result, 0, Sum) :-
xor_1bit_values(A, B, Xor),
Result #= Xor + Sum.
xor_number(A, B, Result, Count, Sum) :-
P is 2^Count,
X #= A / P,
Y #= B / P,
xor_1bit_values(X, Y, Tmp),
NewSum #= Sum + P*Tmp,
NewCount is Count - 1,
xor_number(A, B, Result, NewCount, NewSum).
入力と出力の例:
?- time(xor_number(123456789, 987654321, R, 32)).
% 943 inferences, 0.000 CPU in 0.001 seconds (0% CPU, Infinite Lips)
R = 1032168868
私のコードでは時々推測する必要があり、これらすべてが 32 ビットの数値である必要がある場合、これは私の目的には遅すぎAます。そして、10 ビット以上を必要とする数値の場合、これは文字通り数百万回の推論になり、指数関数的に増加するようです。また、最適なラベル付け戦略、XOR 引数のスワッピング、その他のトリックを使用して計算を高速化しています。BAxorB
というわけで、ちょっと計算してみました。私が考案したのは、2 ビット値 (0、1、2、3) の XOR 関数です。
xor_2bit_values(A, B, Result) :-
Result #= ((A + B*((-1)^A)) mod 4).
3 より大きい数で使用するには、前に提示したものと同様のコードがあります。
xor_number2(A, B, Result, Bits) :-
Count is (Bits / 2) - 1,
xor_number2(A, B, Result, Count, 0).
xor_number2(A, B, Result, 0, Sum) :-
xor_2bit_values(A, B, Xor),
Result #= Xor + Sum,
!.
xor_number2(A, B, Result, Count, Sum) :-
P is 4^Count,
X #= A / P,
Y #= B / P,
xor_2bit_values(X, Y, Tmp),
NewSum #= Sum + P*Tmp,
NewCount is Count - 1,
xor_number2(A, B, Result, NewCount, NewSum).
これは、最初のコードよりも 50% 近く高速に動作するようです。それでも、2 倍の差は私には小さすぎます。
それで、私の質問は次のとおりです。32 ビットの数値に対して効率的な XOR を実装するにはどうすればよいですか? これが最新のマシンでは不可能であり、何らかの計算で証明できる場合、それは私の質問に対する素晴らしい答えでもあります。最終的に、コードを改善するにはどうすればよいでしょうか? 数値を分割せずに処理する方法や、他の方法で数値を XOR する方法について、いくつかのアイデアがあるかもしれません。
追加情報: 私のコードで 3 つの引数または XOR から 2 つを推測しようとした場合、その関数の引数を自由に交換できる可能性があるため (これは数学的特性に由来します) A、バインドされた変数およびバインドされていない変数としてB設定AxorBすることをお勧めします。 . CLPFD はその方法で最も速く動作するようです。また、最適なラベリング戦略はlabeling([bisect], [B,AxorB].