Re: [Haskell-cafe] Optimizing cellular automata evaluation (round 2)

On Nov 30, 2007 6:03 PM, Justin Bailey wrote:

On Nov 29, 2007 9:11 PM, Jon Harrop wrote:

...

Mathematica uses a single arbitrary-precision integer to represent each generation of a 1D automaton. The rules to derive the next generation are compiled into arithmetic operations on the integer. The offloads all such work onto your big number library and, with GMP, will be as fast in Haskell as most other languages.

Does GHC already use the GMP library for Integer? It looks that way but I'm not positive. That'd be ironic, if the higher-level Integer representation is faster than a low-level bitwise one ... Still, I suspect accessing individual "bits" might kill me if I'm not able to move most of the calculation into a call to the library.

Do you mind elaborating on how rules are compiled into 'arithmetic' operations or providing a link?

Integer is an instance of Bits, so you can just use bitshifts and bitops to do any 1-D rule. There might be a more efficient way. For rule 110: 111 110 101 100 011 010 001 000 0 1 1 0 1 1 1 0 Algebraically, that's not (a && b && c || a && not b && not c || not a && not b && not c) So just translate that to: rule z = complement ((a .&. b .&. c) .|. (a .&. b' .&. c') .|. (a' .&. b' .&. c')) where a = z `shift` (-1) b = z c = z `shift` 1 a' = complement a b' = complement b c' = complement c Modulo some algebra to make it even better, but this should be pretty darn fast... Luke