Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!mit-eddie!wjc
From: wjc@mit-eddie.UUCP
Newsgroups: comp.graphics
Subject: Re: Munching Squares
Message-ID: <6019@eddie.MIT.EDU>
Date: Thu, 4-Jun-87 16:41:47 EDT
Article-I.D.: eddie.6019
Posted: Thu Jun  4 16:41:47 1987
Date-Received: Sat, 6-Jun-87 09:00:44 EDT
References: <6004@eddie.MIT.EDU> <536@iscuva.ISCS.COM>
Organization: MIT EE/CS Computer Facility, Cambridge, MA
Lines: 36
Summary: I found the answer...



I received two replies to my question, and also looked at the
code for the munching squares demo on Symbolics Lisp machines.

The algorithm is as follows:

	Assume a square bitmap with the number of pixels along
	a side equal to a power of 2, say 2^N.

	Get an N-bit number from the user, this is the SEED.

	Clear an N-bit accumulator, ACC.

	Now loop on the following statements:

		Set ACC = ACC + SEED  (don't worry about overflow, just
					let it wrap around)

		Move the lower N bits of ACC into an
			N-bit variable X.

		Move (the upper N bits of ACC) xor X into an
			N-bit varible Y.

		Invert the state of the pixel at (X, Y).

That's the whole thing.  You can let it run forever, however all states will
have been seen after 2^(2N+1) iterations.

Good seed values are:	1, 2, 401, 10421, 11111, 100001, and 100020.  These
are in octal.


Have fun.
Bill