Grz*_*ski 6 prolog swi-prolog bitwise-xor clpfd
我尝试在Prolog CLPFD中实现高效的异或(XOR).这应该是简单的谓词,如:
xor(A, B, AxorB).
A,B,AxorB是自然数(用0表示)和AxorB是的结果A 的XOR B.
我的主要问题是效率.首先,我无法找到任何方法来对两个数字进行异或,而不将这些数字分成可以进一步处理/约束的单独部分,并且打破这些数字的过程(创建适当的约束然后解析它们)正在进行一些处理时间.其次,我不能提出任何有效的方法来"模拟"自然数字上的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
现在,这对我的目的来说太慢了,因为在我的代码中我有时需要猜测A,B当我AxorB所有这些都应该是32位数字时.对于需要超过10位的数字,这可能会导致数百万的推论,这些推断似乎会呈现出潜在的增长.我使用最好的标签策略,XOR参数交换和其他技巧来加速计算.
所以,我试着做一些数学.我设计的是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%.但是,对我来说,两倍的差异仍然太小.
所以,我的问题是:如何为32位数字实现高效的XOR？如果这在现代机器上是不可能的,你可以通过某种计算证明它,那么它也是我的问题的一个很好的答案.最终,我怎样才能最好地改进我的代码？也许你有一些想法如何处理数字而不会分开它们或如何以其他方式对数字进行异或？
附加信息:如果您碰巧尝试我的代码从三个参数或XOR猜测两个,那么因为可以自由地交换该函数的参数(来自其数学属性)我建议设置A为绑定变量B并且AxorB作为未绑定.CLPFD似乎以这种方式运作得最快.此外,最好的标签策略是labeling([bisect], [B,AxorB].
我想我会尝试预先计算一些“位块”表，然后使用取模和除法（两者都支持的操作）对表进行 N 次查找。这个想法是查找可以比库执行的（巨大！）算术扩展更快。这是常见的“用空间换时间”的伎俩。
/** <module> bits_clpfd
*
* naive implementation of basic bit operations on constrained variables
* --------
*
* source file /home/carlo/prolog/bits_clpfd.pl
* created at dom mag 18 07:57:03 2014
*
* @author carlo
* @version 0.9.9
* @copyright carlo
* @license LGPL v2.1
*/
:- module(bits_clpfd,
[bits_clpfd_prepare_lut/2
]).
:- use_module(library(clpfd)).
:- dynamic lut_and_or_xor/5.
:- dynamic chunk_size/2.
%% bits_clpfd_prepare_lut(Bits, Max) is det.
%
% setup the lookup table for basic most operations on constrained variables
% the cost is mainly controlled by Bits, being the LUT size 2^(Bits*2)
%
% @arg Bits how many bits to store
% @arg Max describe Max
%
bits_clpfd_prepare_lut(Bits, BMax) :-
( nonvar(Bits) ; Bits = 4 ),
( nonvar(BMax) ; BMax = 32 ),
retractall(chunk_size(_, _)),
Max is 1 << BMax,
assert(chunk_size(Bits, Max)),
retractall(lut_and_or_xor(_,_, _,_,_)),
N is (1 << Bits) - 1,
forall((between(0, N, A), between(0, N, B)), (
And is A /\ B,
Or is A \/ B,
Xor is A xor B,
assertz(lut_and_or_xor(A,B, And,Or,Xor))
)).
%% xor_clpfd(A, B, C) is nondet.
%
% naive constraint A xor B #= C
%
% @arg A constrained variable
% @arg B constrained variable
% @arg C constrained variable
%
xor_clpfd(A, B, C) :-
maplist(check_domain_range, [A,B,C]),
split_apply_xor(1, A, B, C).
split_apply_xor(L, A, B, C) :-
chunk_size(NBits, Max),
( L < Max
-> Mod is (2 << NBits),
Am #= A mod Mod,
Bm #= B mod Mod,
Cm #= C mod Mod,
lut_and_or_xor(Am, Bm, _, _, Cm),
Ad #= A / Mod,
Bd #= B / Mod,
Cd #= C / Mod,
M is L << NBits,
split_apply_xor(M, Ad, Bd, Cd)
; true
).
check_domain_range(V) :-
chunk_size(_, Max),
assertion((fd_dom(V, Inf .. Sup), Inf>=0, Sup < Max)).
:- begin_tests(bits_clpfd).
test(1) :-
bits_clpfd_prepare_lut(2, 4),
Vs = [A,B,C], Vs ins 0..15,
A #= 1, B #= 1, C #= 0,
xor_clpfd(A, B, C).
:- end_tests(bits_clpfd).
测试
?- run_tests(bits_clpfd).
% PL-Unit: bits_clpfd
Warning: /home/carlo/prolog/bits_clpfd.pl:83:
PL-Unit: Test 1: Test succeeded with choicepoint
done
% test passed
true.
不管怎样，这是一种幼稚的方法，正确的方法应该是编译自己的 run_propagator/2。但我从来没有这样做过...