Re: killing time in 6502 assembly

[pg@sff.net (Paul Guertin)]

On 14 Feb 99 13:16:10 GMT, david@uow.edu.au (David Wilson) wrote:

> pg@sff.net (Paul Guertin) writes:
> >It could be interesting to try to come up with 6502 "busy beavers".
> >A busy beaver is a program that eventually terminates (in other words,
> >it doesn't enter an infinite loop). The idea is to come up with the
> >program of length N that works for the longest time before terminating.
> >To preserve the theoretical flavor of the problem, assume 64k of RAM
> >and no ROM routines to call.
> 
> Treat almost all RAM as a very long binary number, the rest is the program.
> Increment that number from 000..000 to 111..111. When it wraps stop.

Right, that's the asymptotic optimum for large N, but I was more 
interested in smaller values of N.

Assume the routine must return to the caller with a RTS. So for N=1..7
we can start with the following:

length 1: RTS
length 2: NOP; RTS
length 3: PHA; PLA; RTS
length 4: JSR FOO; FOO: RTS
length 5: JSR FOO; FOO: NOP RTS  (I think this can be improved)
length 6: LDX #0; FOO: DEX; BNE FOO; RTS
length 7: FOO: DEC BAR+1; BAR: LDA #0; BNE FOO; RTS

I have no idea if they are optimal (in the sense that no routine of the
same length takes longer to return). Any takers?

Paul Guertin