Complex Systems

Fast Computation of Additive Cellular Automata Download PDF

Arch D. Robison
Department of Computer Science, University of Illinois,
1304 West Springfield Avenue,
Urbana, IL 61801, USA


Direct simulation of an additive cellular atuomaton takes a time to compute an arbitrary site value time steps into the future. For the case of a single initial nonzero site, the problem is equivalent to computing a coefficient residue of a polynomial power. An algorithm is derived which computes an abitrary site's value in time .