Nonrandom random fill in Golly?
Nonrandom random fill in Golly?
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?
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.
Re: Nonrandom random fill in Golly?
You get vertical stripes when the width is 8192, rather than diagonal stripes for 8193. Anyway, let's delve into the implementation:
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.
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();
}
What do you do with ill crystallographers? Take them to the mono-clinic!
Re: Nonrandom random fill in Golly?
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
Code: Select all
x = 31, y = 5, rule = B2-a/S12
3bo23bo$2obo4bo13bo4bob2o$3bo4bo13bo4bo$2bo4bobo11bobo4bo$2bo25bo!
Re: Nonrandom random fill in Golly?
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.
- Extrementhusiast
- Posts: 1966
- Joined: June 16th, 2009, 11:24 pm
- Location: USA
Re: Nonrandom random fill in Golly?
Browsing through the Wikipedia page on PRNGs, I found these three: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.
- Mersenne twister
- Well equidistributed long-period linear family
- xorshift family
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)
- PHPBB12345
- Posts: 1096
- Joined: August 5th, 2015, 11:55 pm
- Contact:
Re: Nonrandom random fill in Golly?
Have stripes:
Brent's XORGEN algorithm
Another PRNG suggestion:
Brent's XORGEN algorithm