Thực hiện chức năng XOR với Prolog CLPFD cho các số 32 bit

Question

Tôi cố gắng thực hiện độc quyền hoặc (XOR) hiệu quả trong Prolog CLPFD. Điều này cần được đơn giản ngữ như:

xor(A, B, AxorB). 

A, B, AxorB là số tự nhiên (với 0) và AxorB là kết quả của AxorB.

Vấn đề chính của tôi là hiệu quả. Thứ nhất, tôi đã không thể tìm thấy bất kỳ cách nào để XOR hai số mà không vi phạm các số đó thành các phần riêng biệt có thể được xử lý/hạn chế hơn nữa và quá trình phá vỡ các số đó (tạo ra các ràng buộc thích hợp và sau đó giải quyết chúng) thời gian. Thứ hai, tôi không thể đưa ra bất kỳ cách hiệu quả nào để "mô phỏng" các hàm XOR trên các số tự nhiên khác ngoài các mã được trình bày trong mã thứ hai bên dưới.

Cho phép bắt đầu từ mã đầu tiên của tôi. Đây là XOR thực hiện đơn giản nhất có thể và nó chỉ hoạt động cho các giá trị 1 bit (0 và 1):

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

Để sử dụng nó cho số lớn hơn 1, số phải được chia thành các 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). 

mẫu đầu vào và đầu ra:

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

Bây giờ, đây là quá chậm cho các mục đích của tôi, như trong mã của tôi, tôi có đôi khi cần phải đoán A và B khi tôi có 0.123.trong đó tất cả các số này phải là số 32 bit. Và đối với những con số cần nhiều hơn 10 bit, điều này đi vào hàng triệu suy luận theo nghĩa đen dường như gia tăng theo cấp số nhân. Và tôi sử dụng các chiến lược ghi nhãn tốt nhất, các đối số XOR trao đổi và các thủ thuật khác để tăng tốc độ tính toán.

Vì vậy, tôi đã cố gắng thực hiện một số phép toán. Những gì tôi nghĩ ra là chức năng XOR cho các giá trị 2-bit (0, 1, 2, 3):

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

Để sử dụng nó với số lượng lớn hơn 3 có mã tương tự như những gì tôi đã trình bày trước đây:

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

Điều này dường như hoạt động nhanh hơn gần 50% so với mã đầu tiên. Nhưng vẫn còn, sự khác biệt hai lần vẫn còn quá nhỏ đối với tôi.

Vì vậy, câu hỏi của tôi dành cho bạn là: làm thế nào tôi có thể triển khai XOR hiệu quả cho các số 32 bit? Nếu điều này là không thể trên máy móc hiện đại và bạn có thể chứng minh nó bằng một số loại calcucation sau đó nó cũng là một câu trả lời tốt đẹp cho câu hỏi của tôi. Cuối cùng, làm cách nào để tôi có thể cải thiện mã của mình tốt nhất? Có lẽ bạn có một số ý tưởng làm thế nào để đối phó với các con số mà không vi phạm chúng ngoài hoặc làm thế nào để XOR số theo cách khác?

Thông tin bổ sung: Nếu bạn thử mã của tôi để đoán hai từ ba đối số hoặc XOR, thì có khả năng tự do trao đổi đối số của hàm đó (xuất phát từ các thuộc tính toán học). dưới dạng biến số ràng buộc và B và AxorB là không bị ràng buộc. CLPFD dường như hoạt động nhanh nhất theo cách đó. Ngoài ra, chiến lược ghi nhãn tốt nhất sẽ là labeling([bisect], [B,AxorB].

Answer 1

Tôi nghĩ rằng tôi sẽ cố gắng tính toán trước một số bảng 'bit chunks', và sau đó, bằng cách sử dụng modulo và phân chia (cả hai hoạt động được hỗ trợ), sẽ làm N tra cứu vào bảng. Ý tưởng nó là một tra cứu có thể làm việc nhanh hơn so với việc mở rộng số học (khổng lồ!) Được thực hiện bởi thư viện. Đây là thủ thuật 'không gian thương mại thời gian' thông thường.

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

kiểm tra

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

dù sao, đây là một cách tiếp cận ngây thơ, một trong những quyền nên để biên dịch run_propagator riêng bạn/2. Nhưng tôi chưa từng làm điều đó ...