7

我尝试在 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].

4

2 回答 2

3

我想我会尝试预先计算一些“位块”表，然后使用模和除法（均支持的操作），对表进行 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。但是我从来没有做过...

于 2014-05-17T22:49:52.517 回答
1

也许当时它不可用，但现在，我们可以这样做：

Y in 0..5, X #= Y xor 1, label([Y]).

从docs，它写道：

位运算 ()/1, (/)/2, (/)/2, (>>)/2, (<<)/2, lsb/1, msb/1, popcount/1 和 (xor)/ 2也支持。

看看你是否可以根据你的目的调整它。

于 2021-04-03T22:30:02.480 回答