perm filename BITS.SAI[1,LMM] blob
sn#131277 filedate 1974-11-17 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00005 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 begin "pattern finder"
C00006 00003 ! Set manipulation routines
C00009 00004 ! This is the main procedure of the program. It is given two sets A and B
C00015 00005 str BESTREE int BESTCOST
C00018 ENDMK
C⊗;
begin "pattern finder"
require 1000 system!pdl;
require "⊂⊃" delimiters;
define !=⊂ COMMENT ⊃;
define ref=⊂ REFERENCE ⊃;
define proc=⊂ PROCEDURE ⊃;
define int=⊂ INTEGER ⊃;
define str=⊂ STRING ⊃;
define crlf=⊂ ('15&'12) ⊃;
int DUMMY;
int NUMBITS,NODECNT,ALL; ! NUMBITS is the number of bits in the input.
2*NUMBITS is the number of data items.
NODECNT is a counter of the number of
times the main procedure is called
ALL is a word with bits 1 to NUMBITS turned on;
str ITSA, ITSB; ! The tree is stored as a string (since in SAIL strings
are the only easily manipulatable variable length data
types). A decision tree can be defined by:
<tree>::= IT'S A | IT'S B |
if <bit> then <tree> else <tree>.
The string representation is thus
<treerep>::= NUMBITS+1 | NUMBITS+2 |
<bitnumber>&<treerep>&<treerep>
NUMBITS+1 is the code for "ITSA" and
NUMBITS+2 for "ITSB" (since those numbers
are never legal bit numbers).
see the procedure OUTREE for the decoding algorithm;
! I/O routines ;
str INFILE; int INJFN, OUTJFN;
define SAY(A)=⊂ out(OUTJFN, A & CRLF) ⊃;
str proc ASK(str Q);
if INFILE="TTY:" then
begin outstr(Q); return(intty) end
else return(sini(INJFN,200,'12));
str proc CONVERT(int BITNUM);
begin ! Convert bit number counting from right
to 2 char column number, counting from left ;
BITNUM←NUMBITS+1-BITNUM;
return ((if BITNUM<10 then " " else NULL) & CVS(BITNUM))
end;
recursive proc OUTREE(int LEVEL; ref str TREE);
begin int I,V;
V←LOP(TREE);
if V=ITSA then say("it's A")
else if V=ITSB then say("it's B")
else begin
out(outjfn,CONVERT(V) & " on => ");
OUTREE(LEVEL+1,TREE);
for I←1 step 1 until LEVEL do out(outjfn," ");
out(outjfn,CONVERT(V) & " off => ");
OUTREE(LEVEL+1,TREE);
end;
end;
! Set manipulation routines ;
define RESTBITS(X)=⊂ (X land (X-1)) ⊃; ! X with the low order 1 bit turned off;
define FIRSTBIT(X)=⊂(X xor RESTBITS(X))⊃; ! word with low order bit of X only;
define ONBIT(X)=⊂ (1 lsh (X-1)) ⊃; ! word with bit number X turned on ;
define NOTEMPTY(X)=⊂ (X≠0) ⊃;
define EMPTY(X)=⊂ (X=0) ⊃; ! for notational convenience;
simple int proc SIZE(int X); ! Returns the number of bits in X which are on;
begin int R;
R←0;
while NOTEMPTY(X) do
begin X←RESTBITS(X); R←R+1 end;
return(R);
end;
! Open files and get the number of bits ;
int STARTIM;
outstr("OUTPUT TO: "); OUTJFN←openfile(NULL,"WC");
outstr("INPUT FROM: "); INFILE←jfns(INJFN←openfile(NULL,"ROC"),0);
STARTIM←runtm('400000,DUMMY);
NODECNT←0;
NUMBITS←cvd(ASK("SIZE? "));
begin "inner block"
safe int array ONA,ONB[1:NUMBITS];
! ONA[i] is a set representation of those elements of A which have bit I
turned on - similarly for ONB and B. By splitting up the representation
into separate words for A and B, we can fit the problem into the PDP10's
36 bit words (20 bits for A and 20 for B);
proc INITIALIZE;
begin "init" Initialize ON arrays from data ;
int INSET,J,I;
ALL←(1 lsh NUMBITS)-1;
ITSA←NUMBITS+1; ITSB←NUMBITS+2;
for I←1 step 1 until NUMBITS do
ONA[I]←ONB[I]←0;
for I←1 step 1 until NUMBITS do
begin
INSET←cvo(ASK("A ?"));
for J←1 step 1 until NUMBITS do
if EMPTY(ONBIT(J) land INSET) then ONA[J]←ONA[J] lor ONBIT(I);
INSET←cvo(ASK("B ?"));
for J←1 step 1 until NUMBITS do
if EMPTY(ONBIT(J) land INSET) then ONB[J]←ONB[J] lor ONBIT(I);
end;
end "init";
! This is the main procedure of the program. It is given two sets A and B
(subsets of the original A and B respectively) and a set BITS of those bits
which can be looked at to distinguish them. SIZES is the size of A + the size
of B. COST is the "cost" of reaching this point in the tree (initially zero).
BEST is the cost of the best tree found so far (initially infinity). If a
better tree than BEST is found, it returns the cost of that tree (to which COST
has been added) and resets BESTREE to a representation for that tree. If no
better tree is found, it just returns BEST and leaves BESTREE alone;
recursive int proc MINTREE(int A,B,SIZES,BITS,COST,BEST;ref str BESTREE);
begin "mintree"
NODECNT←NODECNT+1;
if COST ≥ BEST then return(BEST);
if EMPTY(A) or EMPTY(B) then
begin ! one of the sets is empty. Thus the added cost is 0,
and the "tree" is a single node;
BESTREE←(if EMPTY(A) then ITSB else ITSA);
return (COST);
end;
begin "recur"
int BIT,BITNO,NEWB,REST,ADDED,ONSIZ,AON,AOFF,BON,BOFF,C,D;
str ONTREE,OFFTREE;
! loop thru all of BITS, trying for each bit the decision tree
generated by "deciding" on that bit. The minimum cost tree we
can generate has a cost of
|A|+|B|+cost(min tree for A ∩ ON(bit) and B ∩ ON(bit))
+cost(min tree for A ∩ OFF(bit) and B ∩ OFF(bit))
The |A|+|B| is the number of bits we look at this level and is
passed to us as the parameter SIZES;
COST←COST+SIZES;
if COST ≥ BEST then return(BEST);
REST←BITS; ! REST is those bits not yet considered;
BITNO←0; ! BITNO will be bit number under consideration;
while NOTEMPTY(REST) do begin "bitloop"
BIT←FIRSTBIT(REST);
do BITNO←BITNO+1
until NOTEMPTY (REST land ONBIT(BITNO));
REST←RESTBITS(REST);
NEWB←BITS xor BIT;
AON←ONA[BITNO] land A;
BON←ONB[BITNO] land B;
AOFF←A xor AON;
BOFF←B xor BON;
if (AON or BON) and (AOFF or BOFF)
then begin ! if this bit is either on or off in all of A or B,
don't bother looking at it;
ONSIZ←SIZE(AON)+SIZE(BON);
ADDED←(if AOFF and BOFF then SIZES-ONSIZ else 0);
! if some decision must be made amongst the "off" data
items, the cost will be at least |AOFF|+|BOFF|. This is added
to the cost of the "on" tree here to improve the pruning of
the search tree;
C←MINTREE(AON,BON,ONSIZ,NEWB,COST+ADDED,BEST,ONTREE);
if C < BEST then
begin D←MINTREE(AOFF,BOFF,SIZES-ONSIZ,
NEWB,C-ADDED,BEST,OFFTREE);
if D<BEST then
begin BEST←D;
BESTREE←BITNO & ONTREE & OFFTREE;
end;
end;
end;
end "bitloop";
return (BEST);
end "recur";
end "mintree";
str BESTREE; int BESTCOST;
INITIALIZE;
BESTCOST←MINTREE(ALL,ALL,2*NUMBITS,ALL,0,NUMBITS*NUMBITS*2,BESTREE);
say(" #NODES SEARCHED = " & cvs (NODECNT));
say(" DECISION COST = " & cvs(BESTCOST));
OUTREE(0,BESTREE);
say(cvs(runtm('400000,dummy)-STARTIM) & " MS IN EXECUTION");
closf(OUTJFN); closf(INJFN);
end "inner block";
end "pattern finder";
------------------------------------------------------------------------
#NODES SEARCHED = 93752
DECISION COST = 130
3 on => 19 on => 13 on => 20 on => it's A
20 off => it's B
13 off => it's A
19 off => it's B
3 off => 14 on => 6 on => it's A
6 off => 20 on => it's A
20 off => 15 on => it's A
15 off => it's B
14 off => 15 on => 20 on => it's A
20 off => it's B
15 off => it's B
55515 MS IN EXECUTION