Fast Computation of Additive Cellular Automata
Arch D. Robison
Department of Computer Science, University of Illinois,
1304 West Springfield Avenue,
Urbana, IL 61801, USA
Abstract
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 
.
