使用 Prolog CLPFD 为 32 位数字实现 XOR 函数 [英] Implementing XOR function with Prolog CLPFD for 32-bit numbers

问题描述

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

I try to implement efficient exclusive-or (XOR) in Prolog CLPFD. This should be simple predicate like:

xor(A, B, AxorB).

A、B、AxorB 是自然数(带 0)，AxorB 是 AxorB 的结果code>A xor B.

A, B, AxorB are natural numbers (with 0) and AxorB is a result of A xor B.

我的主要问题是效率.首先，我无法找到任何方法对两个数字进行异或而不将这些数字分成可以进一步处理/约束的单独部分，并且打破这些数字的过程(创建适当的约束然后解决它们)需要一些处理时间.其次，我想不出任何有效的方法来模拟"自然数上的 XOR 函数，而不是下面第二个代码中给出的方法.

My main problem is with efficiency. Firstly, I wasn't able to find any way to XOR two number without breaking those numbers into separate parts that could be further processed/constrained, and the process of breaking those numbers (creating proper constraints and then resolving them) is taking some processing time. Secondly, I wans't able to come up with any efficient way to "simulate" XOR functions on natural numbers other than presented in the second code below.

让我们从我的第一个代码开始.这是最简单的 XOR 实现，它仅适用于 1 位值(0 和 1):

Lets start from my first code. This is the most simple XOR implementation possible and it works only for 1 bit values (0 and 1):

xor_1bit_values(A, B, AxorB) :-
    AxorB #= (A + B) mod 2.

要将其用于大于 1 的数字，必须将数字分解为位:

To use it for numbers larger than 1, numbers must be broken into bits:

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 位的数字，这会转化为数以百万计的推论，这些推论似乎呈指数增长.我使用最好的标签策略、异或参数交换和其他技巧来加速计算.

Now, this is too slow for my purposes, as in my code I have sometimes need to guess A and B when I have AxorB where all of these should be 32-bit numbers. And for numbers that need more than 10 bits this goes into literal millions of inferences that seem to increase expotentially. And I use the best labeling strategies, XOR arguments swapping and other tricks to speed up calculations.

所以，我试着做一些数学运算.我设计的是 2 位值 (0, 1, 2, 3) 的 XOR 函数:

So, I tried to do some maths. What I devised is XOR function for 2-bit values (0, 1, 2, 3):

xor_2bit_values(A, B, Result) :-
    Result #= ((A + B*((-1)^A)) mod 4).

要在大于 3 的数字中使用它，有类似于我之前介绍的代码:

To use it in numbers larger than 3 there is code similar to what I presented before:

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%.但是，两倍的差异对我来说还是太小了.

This seems to work nearly 50% faster than the first code. But still, two-fold difference is still too small for me.

所以，我要问你的问题是:如何为 32 位数字实现高效的 XOR?如果这在现代机器上是不可能的，并且您可以通过某种计算来证明它，那么这也是我问题的一个很好的答案.最后，我怎样才能最好地改进我的代码?也许您有一些想法如何处理数字而不将它们分开，或者如何以其他方式对数字进行异或?

So, my question for you is this: how can I implement efficient XOR for 32-bit numbers? If this is not possible on modern machines and you can prove it by some sort of calcucation then it is also a nice answer to my question. Eventually, how can I best improve my code? Maybe you have some ideas how to deal with numbers without breaking them apart or how to XOR numbers in other way?

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

Additional info: If it happens to you to try my code to guess two from three arguments or XOR, then because of possibility to freely swap arguments of that functions (which comes from its mathematical properties) I recommend setting A as bound variable and B and AxorB as unbound. CLPFD seems to work fastest that way. Also, the best labeling strategy would be labeling([bisect], [B,AxorB].

推荐答案

我想我会尝试预先计算一些位块"表，然后，使用模数和除法(都支持的操作)，将进行 N 次查找桌子.这个想法是查找可以比库执行的(巨大的！)算术扩展更快.这是通常的用空间换时间"的把戏.

I think I would try to precompute some table of 'bit chunks', and then, using modulo and division (both supported operations), would do N lookups into the table. The idea it's that a lookup could work faster than the (huge!) arithmetic expansion performed by the library. This is the usual 'trade space for time' trick.

/** <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.但我从来没有做过...

anyway, this is a naive approach, the right one should be to compile your own run_propagator/2. But I've never done it...

这篇关于使用 Prolog CLPFD 为 32 位数字实现 XOR 函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！