Nonrandom random fill in Golly?

Has something gone haywire? Let us know about it!
Post Reply
User avatar
velcrorex
Posts: 339
Joined: November 1st, 2009, 1:33 pm

Nonrandom random fill in Golly?

Post by 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
calcyman
Posts: 2095
Joined: June 1st, 2009, 4:32 pm

Re: Nonrandom random fill in Golly?

Post by 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:

Code: Select all

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
Freywa
Posts: 589
Joined: June 23rd, 2011, 3:20 am
Location: Singapore
Contact:

Re: Nonrandom random fill in Golly?

Post by 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
Andrew
Moderator
Posts: 763
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia
Contact:

Re: Nonrandom random fill in Golly?

Post by 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
Extrementhusiast
Posts: 1796
Joined: June 16th, 2009, 11:24 pm
Location: USA

Re: Nonrandom random fill in Golly?

Post by 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)



Post Reply