32 비트 숫자 용 Prolog CLPFD로 XOR 기능 구현

Question

Prolog CLPFD에서 효율적인 배타적 논리합 (XOR)을 구현하려고합니다.

xor(A, B, AxorB). 

A, B, AxorB가 (0) 자연수와 AxorB가 AXORB의 결과이다 : 이것은 단순한 술어 같이해야한다.

내 주요 문제는 효율성입니다. 첫째, 나는 더 많은 처리/제약이 될 수있는 별도의 부분으로 그 수를 깨지 않고 2 개의 수를 XOR 할 수있는 방법을 찾을 수 없었고, 그 수를 깨는 프로세스 (적절한 제약 조건을 생성 한 다음이를 해결하는 과정) 시각. 두 번째로, 아래의 두 번째 코드에서 제시된 것 이외의 자연수에 대한 XOR 함수를 "시뮬레이트"하는 효율적인 방법을 생각해 낼 수 없습니다.

내 첫 번째 코드부터 시작합니다. 이것은 가장 간단한 XOR 구현 가능하며, 단지 1 개 비트 값 (0, 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). 

:

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

1보다 큰 숫자를 사용하려면, 숫자들은 비트들로 분할되어야

샘플 입력 및 출력 :

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

지금이 내가 가진 내 코드와 같이 내 목적을 위해 너무 느립니다 가끔 내가있을 때 A 및 B을 추측 할 필요가이들 모두는 32 비트 숫자 여야합니다. 그리고 10 비트 이상을 필요로하는 숫자의 경우, 이것은 외래 적으로 증가하는 것처럼 보이는 수백만 개의 추론으로 이어집니다. 그리고 저는 최상의 라벨링 전략, XOR 인수 교환 및 기타 트릭을 사용하여 계산 속도를 높입니다.

그래서 저는 몇 가지 수학을 시도했습니다. 내가 고안하는 것은 (3 0, 1, 2) 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 % 빠른 속도로 작동합니다. 그러나 아직도, 2 배의 차이는 여전히 나에게는 너무 작습니다.

그럼 내 질문은 다음과 같습니다. 어떻게하면 32 비트 숫자에 대해 효율적인 XOR을 구현할 수 있습니까? 이것이 현대의 기계에서는 불가능하고 어떤 종류의 계산으로 증명할 수 있다면 내 질문에 대한 좋은 대답이기도합니다. 궁극적으로 코드를 어떻게 향상시킬 수 있습니까? 어쩌면 몇 가지 아이디어를 나누지 않고 숫자를 다루는 방법 또는 다른 방법으로 숫자를 배타하는 방법이 있을까요?

추가 정보 : 그 다음 때문에 자유롭게 나는 A을 설정하는 것이 좋습니다 (수학적 특성에서 유래)이 함수의 인수를 교환 할 가능성이 세 가지의 인수 또는 XOR을 추측하려면 코드를 시도하는 당신에게 발생하는 경우 바인딩 된 변수로 B 및 AxorB을 언 바운드로 사용합니다. CLPFD는 그렇게 빨리 작동하는 것 같습니다. 또한 최상의 라벨링 전략은 labeling([bisect], [B,AxorB]입니다.

Answer 1

나는 '비트 덩어리'의 일부 테이블을 사전 계산하려고 시도하고, 모듈러스와 나누기 (둘 다 지원되는 연산)를 사용하여 테이블에 N 개의 조회를 수행한다고 생각합니다. 조회는 라이브러리가 수행 한 (거대한!) 산술 확장보다 빨리 수행 할 수 있다는 아이디어입니다. 이것은 일반적인 '시간을위한 무역 공간'트릭입니다.

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

/** <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_propagator/2를 컴파일 할 수 있어야 권리입니다. 하지만 난 그것을 한 적이 없어 ...