Conference rusure::math

    Three questions:
    
    #1.
    
    >	by reading a value from cell i, and writing to cell j; the next
    >	operation to access j MUST read it and write to k; the next
    >	operation to access k MUST read it and write to l, etc.  This

    	Is this a requirement for a set of operations to be valid, or
    is it only a requirement for the valid formation of a chain?
    
    
    #2.
    
    	Does the following sequence:
    
    		1: (i,j) -> k
    		2:   (k) -> i
    		3:   (k) -> j
    
    					constitute 2 chains ( i(1)-k(2)-i,
    	and j(1)-k(2)-j ), 1 chain ( i(1)-k(2)-j(1)-k(2)-i ), or 0 chains?
    	(ie. just how does the 2 read, 1 write operation affect the
    	definition/construction of a chain?)
    
    
    #3.
    
    	What on earth is this for? (just curious B^) ).
    
    -- Barry
    

    Three answers: (re .1)
    
    #1.
    
>>	by reading a value from cell i, and writing to cell j; the next
>>	operation to access j MUST read it and write to k; the next
>>	operation to access k MUST read it and write to l, etc.  This

>    	Is this a requirement for a set of operations to be valid, or
>    is it only a requirement for the valid formation of a chain?
    

	This is a requirement for a chain.  A set of operations may
 	have no chains at all.
    


    #2.
    
>    	Does the following sequence:
>    
>    		1: (i,j) -> k
>    		2:   (k) -> i
>    		3:   (k) -> j
>    
>    					constitute 2 chains ( i(1)-k(2)-i,
>    	and j(1)-k(2)-j ), 1 chain ( i(1)-k(2)-j(1)-k(2)-i ), or 0 chains?
>    	(i.e. just how does the 2 read, 1 write operation affect the
>    	definition/construction of a chain?)
    
    
	The above example has two chains (i(1)->k(2)->i and j(1)->k(3)->j).

	Let me propose a notation now:

	"x(A)->z" is to be interpreted as : 
	"Cell x is read by operation A and operation A writes cell z"

	Thus we may form a chain by appending "x(A)->z" and "z(B)->w"
	to form "x(A)->z(B)->w" IF there are no intermediate writes
	to cell z in between operation A and B.

	The following set of operations has the following chains:

             i(1)->k(3)->i, j(1)->k(4)->j, and h(5)-> h

    
    		1: (i,j) -> k
		2:   (k) -> h
    		3:   (k) -> i
    		4:   (k) -> j
	        5:   (h) -> h
                6:   (k) -> i


   #3.
    
>    	What on earth is this for? (just curious B^) ).
    

	This is part of the work being done for an instruction generation
	program.  The program generates sample sets of instructions and
        one of the useful pieces of information about a sequence of
  	instructions is the number of chains (as well as resource
	usage like memory & registers).  There are two straight-forward 
	algorithms that I've come up with (top-down and bottom-up)
	and on intuition the bottom-up seems better, but I haven't tested
	them yet.

	

    David

	A better term for these would be "Closed" chains, since
	a "simple" chain would merely reflect the flow of results
	from one operation to another.

	David

    I'm still working on this (not easy).
    
    Can you tell me a couple of things?
    
    	1)  What is the average number of instructions that you expect?
    
    	2)  What is the Maximum number of instructions (if any)?
    
    	3)  Is the address set to be a well defined numeric range, or
    	   is it to be an open range of symbolic identifiers?
    
    	4)  Ave & Max for number of unique addresses.
    
    	5)  What is the expected ratio of 1 read 1 write instructions
    	   to 2 read 1 write instructions?
    
    	6)  What kind of response times would you like/require for (1)
    	   and (2) ?
                                                                   2
    So far I have some working algorithims, but they look to be O(n )
    or O(n*a), where a=# addresses.
    
    -- Barry

    
    	1)  What is the average number of instructions that you expect?

	    4.5 for now.  Perhaps as high as 32.
    
    	2)  What is the Maximum number of instructions (if any)?

	    8 for now, perhaps up to 64.
    
    	3)  Is the address set to be a well defined numeric range, or
    	   is it to be an open range of symbolic identifiers?
    
           I am using a fixed set of 64 cells.

    	4)  Ave & Max for number of unique addresses.

           Average unique cells is 15.
    
    	5)  What is the expected ratio of 1 read 1 write instructions
    	   to 2 read 1 write instructions?
    
            25% have 1 read.  A small % read the same cell twice.


    	6)  What kind of response times would you like/require for (1)
    	   and (2) ?
                                                                   2
            Good question.  My work on this problem has been
	    slowed to a stop.  My guess is some pruning can be
	    done.

            My original intent was to see if there were any 
	    elegant solutions akin to matrix multiplication
	    etc.  When I get a sample algorithm running I 
            will post it here.


	Thanks for the effort.  Things are really busy here, but
	I intend to get back to this as ASAP.

	David

    Uh, bad news Dave.
    
    It appears that there are certain pathological sequences of
    instructions that will cause an exponential number of circuits to
    be formed.  Finding, and deliniating all of them would likewise
    require exponential time (of course).
    
    Consider:
    
    		1:     (a1) -> b1
    		2:     (a1) -> c1
    		3:  (b1,c1) -> a2
    now repeat;
    		4:     (a2) -> b2
    		5:     (a2) -> c2
    		6:  (b2,c2) -> a3
    et cetera.
    
    Even this short sequence has at least four circuits (curious onlookers
    may amuse themselves by trying to find them all...).  Adding another
    three instructions like this will raise that to eight.
    
    In short:
                               (n/3)
    	Max_circuits (n)  ~=  2     
    
    For the stated maximum of 64 instructions could result in at least
    2^21 circuits (WARNING: Home viewers should NOT try this on their
    own computers).
    
    Of course no pratical algorithim would be interested in garbage
    results like this, but I can't seem to come up with a set of 
    limitations/revisions of the stated problem that eliminates all
    the garbage, keeps all the valuable possibilities, and is tractable.
    
    Any help?
    
    -- Barry