prolog - 使用 Prolog CLPFD 实现 32 位数字的 XOR 功能

Question

我尝试在 Prolog CLPFD 中实现高效的异或 (XOR)。这应该是简单的谓词，例如:

xor(A, B, AxorB).

A、B、AxorB 是自然数(带 0)，AxorB 是 A异或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

现在，这对于我的目的来说太慢了，因为在我的代码中，当我有 AxorB 时，我有时需要猜测 A 和 B > 其中所有这些都应该是 32 位数字。对于需要超过 10 位的数字，这会涉及数百万个推论，而且这些推论似乎呈指数级增长。我使用最好的标签策略、异或参数交换和其他技巧来加速计算。

所以，我尝试做一些数学题。我设计的是 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？如果这在现代机器上不可能，并且您可以通过某种计算来证明这一点，那么这也是对我的问题的一个很好的答案。最终，我怎样才能最好地改进我的代码？也许您有一些想法如何在不分解数字的情况下处理数字或如何以其他方式对数字进行异或？

附加信息:如果您碰巧尝试我的代码从三个参数中猜测两个或异或，那么因为可以自由交换该函数的参数(来自其数学属性)我建议将 A 设置为绑定(bind)变量，将 B 和 AxorB 设置为未绑定(bind)。 CLPFD 似乎以这种方式工作得最快。此外，最好的标签策略是labeling([bisect], [B,AxorB]。

Answer 1

我想我会尝试预先计算一些“位 block ”表，然后使用取模和除法(两者都受支持的操作)，对表进行 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。但我从来没有这样做过...