Path: utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!uunet!aplcen!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!rpi!ccnysci!phri!cooper!dasys1!jgbritt
From: jgbritt@dasys1.UUCP (James G Britt)
Newsgroups: comp.theory.cell-automata
Subject: CA algorithms and speed
Keywords: hints or tips?
Message-ID: <11456@dasys1.UUCP>
Date: 28 Dec 89 01:58:39 GMT
Organization: The Big Electric Cat
Lines: 44

..
.
:
:
:
I've been coding cellular automata in C, and have been wondering lately about
algorithms or coding tricks to improve processing time.  Specifically, I wrote
a program to produce the cyclic space described in the August '89 Scientific
American "Computer Recreations" column.  This CA follows the rule that for each
cell (value 0 to n), check all the cells in the Von Nuemann neighborhood.  If
any of those cells have the value (n+1)mod(n+1), than the center cell takes that
value.  It's like the game "Paper, Scissor, Stone".  My first version used the
comparison statement
:
n=cell+1;         /*    My OR character doesn't port to ASCII */
if(north==n)OR(west==n)OR(east==n)OR(south==n)
   cell++;
:
:
I decided, though, that this method was clumsy, so I mused a bit and decided on
represting cell values differently.  The idea was to code up the numbers in such
a way that you could add the values together and extract what information you
wanted through some simple operation.  First I tried using various primes, and
testing for there presence through % (the mod() function), but, lacking the
proper analytical tools, I got nowhere.  I then used powers of 10 (cell = 10 to
the n ). This made it easy to see how many neighbooring cells had a given value,
but the execution of this process took twice as long as my original comparison
statement!  I re-did it using powers of 2, extracting information via shifting
and masking.  This reduced overall code length, but was still a fraction of a
second slower than what I started with.

Does anybody else have any experience or pointers regarding such things?  I'm
getting acquainted with assembly, which will be a tremendous help locally, but
of course it won't travel so well.

                               James Britt, New York City


 

-- 
James G Britt
Big Electric Cat Public UNIX
..!cmcl2!{ccnysci,cucard,hombre}!dasys1!jgbritt