ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

Nonrandom random fill in Golly?

Has something gone haywire? Let us know about it!

Nonrandom random fill in Golly?

Postby velcrorex » July 5th, 2015, 5:35 pm

I'm not sure if this counts as a bug or just a consequence of how the rng works in golly, but I'm getting some not quite random patterns from randomly filling in an area.

Zoom out to Scale = 2^4 : 1
Select an area 8193 x something
Hit Ctrl+5 to randomly fill area 50%
Zoom in and notice stripes in the randomness.

(8193 - 1) is a large power of 2.
Similar results occur when the width is one more than a large power of two

Any thoughts?
-Josh Ball.
User avatar
velcrorex
 
Posts: 339
Joined: November 1st, 2009, 1:33 pm

Re: Nonrandom random fill in Golly?

Postby calcyman » July 5th, 2015, 8:19 pm

You get vertical stripes when the width is 8192, rather than diagonal stripes for 8193. Anyway, let's delve into the implementation:

void Selection::RandomFill()
{
    if (!exists) return;
   
    // can only use getcell/setcell in limited domain
    if (TooBig()) {
        statusptr->ErrorMessage(selection_too_big);
        return;
    }
   
    if (mainptr->generating) {
        // terminate generating loop and set command_pending flag
        mainptr->Stop();
        mainptr->command_pending = true;
        mainptr->cmdevent.SetId(ID_RANDOM);
        return;
    }
   
    // save cell changes if undo/redo is enabled and script isn't constructing a pattern
    bool savecells = allowundo && !currlayer->stayclean;
    if (savecells && inscript) SavePendingChanges();
   
    // no need to kill cells if selection is empty
    bool killcells = !currlayer->algo->isEmpty();
    if ( killcells ) {
        // find pattern edges and compare with selection edges
        bigint top, left, bottom, right;
        currlayer->algo->findedges(&top, &left, &bottom, &right);
        if (Contains(top, left, bottom, right)) {
            // selection encloses entire pattern so create empty universe
            if (savecells) {
                // don't kill pattern otherwise we can't use SaveCellChange below
            } else {
                EmptyUniverse();
                killcells = false;
            }
        } else if (Outside(top, left, bottom, right)) {
            // selection is completely outside pattern edges
            killcells = false;
        }
    }
   
    int itop = seltop.toint();
    int ileft = selleft.toint();
    int ibottom = selbottom.toint();
    int iright = selright.toint();
    int wd = iright - ileft + 1;
    int ht = ibottom - itop + 1;
    double maxcount = (double)wd * (double)ht;
    int cntr = 0;
    bool abort = false;
    BeginProgress(_("Randomly filling selection"));
    int cx, cy;
    lifealgo* curralgo = currlayer->algo;
    int livestates = curralgo->NumCellStates() - 1;    // don't count dead state
   
    for ( cy=itop; cy<=ibottom; cy++ ) {
        for ( cx=ileft; cx<=iright; cx++ ) {
            // randomfill is from 1..100
            if (savecells) {
                // remember cell change only if state changes
                int oldstate = curralgo->getcell(cx, cy);
                if ((rand() % 100) < randomfill) {
                    int newstate = livestates < 2 ? 1 : 1 + (rand() % livestates);
                    if (oldstate != newstate) {
                        curralgo->setcell(cx, cy, newstate);
                        currlayer->undoredo->SaveCellChange(cx, cy, oldstate, newstate);
                    }
                } else if (killcells && oldstate > 0) {
                    curralgo->setcell(cx, cy, 0);
                    currlayer->undoredo->SaveCellChange(cx, cy, oldstate, 0);
                }
            } else {
                if ((rand() % 100) < randomfill) {
                    if (livestates < 2) {
                        curralgo->setcell(cx, cy, 1);
                    } else {
                        curralgo->setcell(cx, cy, 1 + (rand() % livestates));
                    }
                } else if (killcells) {
                    curralgo->setcell(cx, cy, 0);
                }
            }
            cntr++;
            if ((cntr % 4096) == 0) {
                abort = AbortProgress((double)cntr / maxcount, wxEmptyString);
                if (abort) break;
            }
        }
        if (abort) break;
    }
   
    currlayer->algo->endofpattern();
    EndProgress();
   
    if (savecells) currlayer->undoredo->RememberCellChanges(_("Random Fill"), currlayer->dirty);
   
    // update currlayer->dirty AFTER RememberCellChanges
    MarkLayerDirty();
    mainptr->UpdatePatternAndStatus();
}


So, Golly is calling the function rand() from cstdlib. The way that this is implemented depends on the toolchain, but glibc implements this either as a linear congruential generator or a linear feedback shift register. Both of these are pretty weak and far from random, so it is unsurprising that even an untrained eye can spot patterns in the output.
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 1775
Joined: June 1st, 2009, 4:32 pm

Re: Nonrandom random fill in Golly?

Postby Freywa » July 6th, 2015, 7:40 am

I tried this on Golly for Android and got no such generator malfunctioning. What RNG is used on mobile platforms?
Princess of Science, Parcly Taxel
User avatar
Freywa
 
Posts: 313
Joined: June 23rd, 2011, 3:20 am
Location: Singapore

Re: Nonrandom random fill in Golly?

Postby Andrew » July 11th, 2015, 2:52 am

Anybody got any suggestions for something better than rand()? I'm happy to switch to a better RNG, as long as the performance isn't significantly worse.
User avatar
Andrew
Moderator
 
Posts: 681
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia

Re: Nonrandom random fill in Golly?

Postby Extrementhusiast » July 11th, 2015, 7:16 pm

Andrew wrote:Anybody got any suggestions for something better than rand()? I'm happy to switch to a better RNG, as long as the performance isn't significantly worse.


Browsing through the Wikipedia page on PRNGs, I found these three:
  • Mersenne twister
  • Well equidistributed long-period linear family
  • xorshift family

Of these, Mersenne seems to be the one most well-known. (I don't think we need a cryptographically secure PRNG for this application.)

This page contains a visualization of various RNGs, including Mersenne, which was found to look the most random. (I also saw that Simon #1 looked second best, but I don't know much about that one.)

Thus, it looks like Mersenne could be the way to go, although there are a few other fairly good options available.
I Like My Heisenburps! (and others)
User avatar
Extrementhusiast
 
Posts: 1723
Joined: June 16th, 2009, 11:24 pm
Location: USA


Re: Nonrandom random fill in Golly?

Postby wwei23 » May 29th, 2017, 1:10 pm

Nevermind, I was using 1024 for the x.
User avatar
wwei23
 
Posts: 923
Joined: May 22nd, 2017, 6:14 pm
Location: The (Life?) Universe


Return to Bugs & Errors

Who is online

Users browsing this forum: No registered users and 0 guests