Re: Super encryption? (was Re: Conway's Game of Life; my brain hurts)

[Ilmari Karonen]

[Note: Crossposted to comp.theory.cell-automata and followups set.]

On 2009-03-13, Maaartin <graj...@seznam.cz> wrote:
> To Joseph Ashwood:
>
>> The first major problem is the lack of avalanche. With Conway's Life the
>> number of locations that change are relatively small, and each location is
>> only affected by the surrounding 8.
>
> Yes, but this locality is no problem if you can do many round very
> quickly. In fact, you can compute billions of rounds easily, because
> there's an algorithm running in about logarithmic time (see hashlife).

Hashlife only does well on patterns with fairly low entropy (and which
remain so as they evolve). For non-repetitive high entropy patterns,
the theoretical logarithmic time performance comes at the cost of
exponential memory usage.

--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.