Implementazione della funzione XOR con Prolog CLPFD per numeri a 32 bit

Question

Cerco di implementare l'esclusivo esclusivo o XOR in Prolog CLPFD. Questo dovrebbe essere predicato semplice come:

xor(A, B, AxorB). 

A, B, AxorB sono numeri naturali (con 0) e AxorB è il risultato di AxorB.

Il mio problema principale è l'efficienza. In primo luogo, non sono stato in grado di trovare un modo per XOR due numeri senza infrangere quei numeri in parti separate che potrebbero essere ulteriormente elaborati/vincolati, e il processo di rottura di quei numeri (creando vincoli appropriati e poi risolvendoli) sta prendendo un po 'di elaborazione tempo. In secondo luogo, non sono in grado di trovare un modo efficace per "simulare" le funzioni XOR su numeri naturali diversi da quelli presentati nel secondo codice qui sotto.

Iniziamo dal mio primo codice. Ciò è possibile la più semplice attuazione XOR e funziona solo per valori 1 bit (0 e 1):

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

utilizzarlo per numeri maggiori di 1, numeri devono essere suddivisi in bit:

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). 

di ingresso del campione e l'uscita:

?- time(xor_number(123456789, 987654321, R, 32)). 
% 943 inferences, 0.000 CPU in 0.001 seconds (0% CPU, Infinite Lips) 
R = 1032168868 

Ora, questo è troppo lento per i miei scopi, come nel mio codice che ho a volte hanno bisogno di indovinare A e B quando ho 0.123.dove tutti questi dovrebbero essere numeri a 32 bit. E per i numeri che richiedono più di 10 bit, ciò si traduce in milioni di inferenze letterali che sembrano aumentare espotenzialmente. E io uso le migliori strategie di etichettatura, lo scambio degli argomenti XOR e altri trucchi per accelerare i calcoli.

Quindi, ho provato a fare alcuni calcoli matematici. Quello che ho ideato è la funzione XOR per i valori 2-bit (0, 1, 2, 3):

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

di usarlo in numero maggiore di 3 c'è un codice simile a quello che ho presentato prima:

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). 

Sembra funzionare quasi il 50% più veloce del primo codice. Ma ancora, la doppia differenza è ancora troppo piccola per me.

Quindi, la mia domanda per voi è questa: come posso implementare XOR efficiente per i numeri a 32 bit? Se questo non è possibile su macchine moderne e puoi provarlo con una sorta di calcolo allora è anche una bella risposta alla mia domanda. Alla fine, come posso migliorare al meglio il mio codice? Forse hai qualche idea su come gestire i numeri senza dividerli o come fare i numeri XOR in altro modo?

Ulteriori informazioni: Se succede a voi di provare il mio codice di indovinare due da tre argomenti o XOR, poi a causa della possibilità di scambiare liberamente argomenti di che le funzioni (che proviene dalle sue proprietà matematiche) vi consiglio di impostare A come variabile associata e B e AxorB come non associati. CLPFD sembra funzionare più velocemente in questo modo. Inoltre, la migliore strategia di etichettatura sarebbe labeling([bisect], [B,AxorB].

Answer 1

Penso che proverei a precalcolare alcune tabelle di "bit chunks", e quindi, usando modulo e divisione (entrambe le operazioni supportate), farei N lookups nella tabella. L'idea è che una ricerca possa funzionare più velocemente dell'espansione aritmetica (enorme!) Eseguita dalla libreria. Questo è il solito trucchetto "trade for time".

/** <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). 

prova

?- 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. 

in ogni caso, questo è un approccio ingenuo, quello giusto dovrebbe essere quello di compilare il proprio run_propagator/2. Ma non l'ho mai fatto ...