Is hashing a good way to compare two 32x64 two dimensional arrays exactly?

Question

I'm trying to implement Conway's Game of Life on an embedded device. I've only got 1kb of RAM to play with and in total there are 2048 cells which equals 512 bytes. I'm going to calculate the next generation 8x8 cells at a time so that I don't have to store two generations in RAM at any one point.

However what I would also like to do is detect when the GoL is stuck in a loop/static state. When I created a mockup on a PC I simply stored the last hundreth and thousandth generation and compared the current generation to it. I can't do this with 1kb of RAM, what I am thinking of doing is simply calculating a hash of the last x generation and comparing the hash of that to the hash of the current generation.

There are some very light implementations of XTEA or SHA1 but I'm not sure if hashing is really fit for this purpose since I need to determine if each individual cell in both generations are equal. What would you recommend?

Thanks,

Joe

EDIT: Just thinking, I could actually count the number of matches and if it reaches a certain threshold then assume that it is in a loop, that wouldn't work very well for patterns that recur every thousand generations or so though.

Answer 1

I decided to just get a device with more RAM but one thing that I observed is that if there is a pattern then the same pattern will be matched every x generations whilst if it was just a random hash collision then it won't. So if we have the following generations:

123*
231
312
123*
231
312
123*

123 gets matched every 3 generations. This wouldn't occur with a hash collision.

The other answers were correct and valuble but this is the only one that offers a solution to the problem. I'm not sure what the etiquette is when answering your own questions so if I shouldn't have marked this as the answer then please don't down vote it, just message me and I will re-assign the correct answer.

Thanks,

Joe

Answer 2

I think it's quite good choice. The probability for hash collision is so low, hence it's acceptable for application as yours, it is not nuclear reactor.

Answer 3

Hashing is good to tell when things are not equal. If the hashes are equal, then you still need (well ought) to do the individual comparison.