bimandre@uunet.UU.NET (Andre Marien) (01/27/89)
/*
The following program illustrates how to convert a bit map in
the objects it represents in a time linear with the number
of set one bits, in stead of linear in the length of the bit map.
Some remarks :
- xor is not standard available in prologs, therefore it
is done with ((a | b) & ~(a & b))
- the data base q/2 would be implemented as an array in C
- the prolog version I use (BIM_Prolog) restricts the size of integers,
as do many prolog inplementations. This explains the limitation
of the prolog algorithm to 28 bit positions
- it pays off only if set bits are sparse, and at least one is
a high numbered bit, because the cost per iteration is higher
than the shift method
*/
genl(_n,[_g|_l]) :-
_n > 0, !,
_nm1 is (_n - 1),
_nn is _n /\ _nm1,
_v is ((_n \/ _nm1) /\ (\ _nn)) mod 29,
q(_v,_g),
genl(_nn,_l) .
genl(0,[]) .
q(1,1) .
q(3,2) .
q(7,3) .
q(15,4) .
q(2,5) .
q(5,6) .
q(11,7) .
q(23,8) .
q(18,9) .
q(8,10) .
q(17,11) .
q(6,12) .
q(13,13) .
q(27,14) .
q(26,15) .
q(24,16) .
q(20,17) .
q(12,18) .
q(25,19) .
q(22,20) .
q(16,21) .
q(4,22) .
q(9,23) .
q(19,24) .
q(10,25) .
q(21,26) .
q(14,27) .
q(0,28) .
/*
C- code :
int convtab[] =
{28, 1, 5, 2,22,
6,12, 3,10,23,
25, 7,18,13,27,
4,21,11, 9,24,
17,26,20, 8,16,
19,15,14};
new_procedure(n,add)
register int n;
register int *add;
{
while(n)
{ *add++ = convtab[((n -1) ^ n) % 29];
n = (n-1) & n;
}
*add++ = 0;
}
shift_procedure(n,add)
register int n;
register int *add;
{ register int nm1,ctr;
ctr = 1;
while(n)
{ if(n&1) *add++ = ctr;
ctr++;
n >> = 1;
}
*add++ = 0;
}
Note : 31 bits in C :
int convtab[] =
{-1, 1,26, 2,23,
27,-1, 3,16,24,
30,28,11,-1,13,
4, 7,17,-1,25,
22,31,15,29,10,
12, 6,-1,21,14,
9, 5,20, 8,19,
18};
..
{ *add++ = convtab[((n -1) ^ n) % 37];
..
Note : DON'T try mersenne primes !! (ie, 31)
Andre' Marien
mcvax!prlb2!kulcs!bimandre (uucp)
bimandre@cs.kuleuven.ac.be (might work)
*/