[Haskell-cafe] Optimizing cellular automata evaluation (round 2)
Luke Palmer
lrpalmer at gmail.com
Fri Nov 30 13:30:42 EST 2007
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
More information about the Haskell-Cafe
mailing list