Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Comment on

( #3333=superdoc: print w/replies, xml ) Need Help??

And now for something completely different :)

This was written to see if I could use perl's logical string operations to do the calculations need for Life.

Of course, what I really wanted was a string oriented byte-by-byte add ( a +. to go along with the brand new |. and &. ) but I couldn't find one (sigh).

However, this is a way to use three bits in the byte as a sum, provided only one bit is added at a time.
Consider the 8 bits of a byte to be 0011SSSN where the 'S' bits are the sum and a new bit 'N' is added (actually or'd) as the bottom bit. (Why the two '1' bits? Because the character '0' is 00110000 as binary and '1' is 00110001 as binary, and we can do calculations such that the result is immediately printable. We don't, but we could :)

Now if I 'or' in a neighbor character it will only (potentially) change the 'N' bit. For each neighbor, I only have to add that bit to the sum (in SSS) and then clear the bottom bit for the next neighbor.

This turns out to be a simple tr/1357/2468/ translation.

(But tybalt89, you say, you only have a three bit counter and there are eight neighbors, you can't hold a count that high. Answer: I don't have to, since any count four or greater will result in a dead cell, I only have to count to four.)

After processing all eight neighbors, the center cell is then or'd in to give the state of the neighbor count along with the state of the center cell, which can the be translated to "alive or dead" for the next generation.

In this scheme, you need to specify the size of the grid in advance, and any live cells at the grid edge get killed to avoid wraparound'


So how does this do on the challenge - simple, it fails. (Oh good, I can avoid being hired :)

You did say you wanted "to see how others go about it".

Notes:

It's "live cell count" speed invariant, as opposed to techniques that keep only live cells.
I stopped performance testing because I ran into Heisenberg problems, i.e. output seriously affects speed.
It's not infinite size, or even semi-infinite, unless you've got a really, really, really big machine.
It should probably be moved to GPUs but a) I don't have a GPU to test on, and b) it probably already has been.


I usually run it without the override lines, and uncommented print statements. It autosizes to the terminal it is running in, (at least on ArchLinux and xterm), and of course increase the number of generations.



OK, I have to go cook supper, and I'm really tired of typing, so I'll submit at this point, and look for comments later...

#!/usr/bin/perl # http://perlmonks.org/?node_id=1197250 # Conway's life eyepopslikeamosquito use strict; use warnings; use Time::HiRes 'time'; my $w = qx(tput cols) + 0; # probably linux only :) my $h = qx(tput lines) - 7; # strange offset because of my REPL # override for comparison with node results $w = int sqrt 3e6; $h = int 1 + 3e6 / $w; my $board = '0' x $w x $h; my $mask = '0' x $w . ('0' . "\xff" x ($w - 2) . '0') x ($h - 2) . '0' + x $w; # build starting state sub place { my ($x, $y, $pattern) = @_; my $offset = $y * $w + $x; for ( $pattern =~ /.+/g ) { substr $board, $offset, length $_, $_; $offset += $w; } } place( 4, 4, <<END =~ tr/-O/01/r ); # glider gun ------------------------O----------- ----------------------O-O----------- ------------OO------OO------------OO -----------O---O----OO------------OO OO--------O-----O---OO-------------- OO--------O---O-OO----O-O----------- ----------O-----O-------O----------- -----------O---O-------------------- ------------OO---------------------- END place( $w >> 1, $h >> 1, <<END =~ tr/-O/01/r ); # switch engine ---------- -------O-- -----O-OO- -----O-O-- -----O---- ---O------ -O-O------ ---------- END my $generations = 0; my @offsets = ( 1, 2, $w, $w + 2, $w * 2, $w * 2 + 1, $w * 2 + 2 ); my $pad = '0' x ($w + 1); #print "\e[H\e[J"; # clear screen #print "\e[H", $board =~ tr/01/ O/r, "-" x $w, "$generations\n"; my $starttime = time; for (1..2) # loop over generations { $generations++; my $all = $pad . $board . $pad; my $sum = $all =~ tr/1/2/r; # first o +ffset ( $sum |= substr $all, $_ ) =~ tr/1357/2468/ for @offsets; # other 7 $board |= $mask & $sum; # prevent overflow at edges $board =~ tr/1-9/000011100/; # determine alive or dead #print "\e[H", $board =~ tr/01/ O/r, "-" x $w, "$generations\n"; } my $time = time - $starttime; printf "\nw %d h %d cells %d time %.2f generations %d gen/sec %d" . " nanoseconds/cell/gen %d\n", $w, $h, $w * $h, $time, $generations, $generations / $time, $time / ($w * $h) / $generations *1e9;

In reply to Re: High Performance Game of Life by tybalt89
in thread High Performance Game of Life by eyepopslikeamosquito

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and all is quiet...

    How do I use this? | Other CB clients
    Other Users?
    Others musing on the Monastery: (5)
    As of 2017-12-16 01:47 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?
      What programming language do you hate the most?




















      Results (447 votes). Check out past polls.

      Notices?