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

[Luke Palmer]

On Nov 30, 2007 6:03 PM, Justin Bailey <jgbailey at gmail.com> wrote:
> On Nov 29, 2007 9:11 PM, Jon Harrop <jon at ffconsultancy.com> 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