Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site dartvax.UUCP
Path: utzoo!watmath!clyde!bonnie!akgua!mcnc!decvax!dartvax!chuck
From: chuck@dartvax.UUCP (Chuck Simmons)
Newsgroups: net.puzzle
Subject: Re: Z80 Code Puzzle (spoiler and another puzzle)
Message-ID: <2830@dartvax.UUCP>
Date: Tue, 12-Mar-85 14:42:32 EST
Article-I.D.: dartvax.2830
Posted: Tue Mar 12 14:42:32 1985
Date-Received: Sun, 17-Mar-85 01:03:05 EST
References: <1059@decwrl.UUCP>
Organization: Dartmouth College, Hanover, NH
Lines: 53

<Another puzzle appears below.>

> LOOP:
> 	CP	(HL)	; Compare A to memory at HL
> 	RET	Z	; Return if equal.
> 
> 	RL	L	; Rotate carry and L register (bottom 8 bits of
> 			; HL pair) left (Carry goes into LSB of L)
> 	DJNZ	LOOP	; B--; if (B != 0) GOTO LOOP
> 
> 	LD	L,0	; Load L with the value Zero.
> 	RET		; Return

This looks like a binary search.  Suppose A is a value that we want to
lookup in a table and that the address of the table is equivalent to 1
mod 64k.  Further we suppose that the number of elements in the table 
is 2**B-1.  Finally the elements in the table have been stored in a
rather special order.  In particular, we have 

    table(2i) < table(i) < table(2i+1)

for all i in 1..2**(B-1)-1.  (Actually, we can violate this constraint
for the last few values if we don't have enough elements to fill up
the table.  A reasonable thing to do would be to use table(1) as a
filler element.)

Example:  A = 5; B = 3; table = 4, 2, 6, 1, 3, 5, 7; L = 1

5>4 so set carry bit
L <- 3
B = 2
5<6 so clear carry bit
L <- 6
B = 1
5=5 so return


My puzzle is written in 68000 code, and it does not do anything nearly
as common as perform a binary search.  (This puzzle is due to Mike Morton,
the author of the reaganagrams published in a recent Scientific American.)
d0, d1, and d2 are 32 bit registers.

        move.w #32,d2   ; d2 = 32
        bra.s start     ; jump into our loop
lp:     or.l d1,d0      ; d0 |= d1
start:  move.l d0,d1    ; d1 = d0
        add.l #1,d0     ; d0 = d0 + 1
        dbcs d2,lp      ; if carry is clear, then decrement d2,
                        ; and if d2 != 0 goto lp.
                        ; (Thus if the carry is set or if d2 becomes 0,
                        ; we will leave the loop.)

chuck_simmons%d1@dartvax