Elementary cellular automaton/Random number generator: Difference between revisions

 

Steven Wolfram's recommendation for random number generation from rule 30 consists in extracting successive bits in a fixed position in the array of cells, as the automaton changes state.

;Reference:

* [http://www.cs.indiana.edu/~dgerman/2005midwestNKSconference/dgelbm.pdf Cellular automata: Is Rule 30 random]? (PDF).

=={{header|C}}==

64-bits array size, cyclic borders.

#include <limits.h>

 

evolve(1, 30);

return 0;

{{out}}

<pre> 220 197 147 174 117 97 149 171 100 151</pre>

=={{header|C++}}==

We'll re-write the code of the parent task here.

#include <stdio.h>

 

printf("%u%c", byte(state), i ? ' ' : '\n');

return 0;

{{out}}

<pre>220 197 147 174 117 97 149 171 240 241</pre>

{{trans|C}}

Adapted from the C version, with improvements and bug fixes. Optimized for performance as requested in the task description. This is a lazy range.

 

struct CellularRNG {

CellularRNG(1, 30).take(10).writeln;

CellularRNG(1, 30).drop(2_000_000).front.writeln;

{{out}}

<pre>[220, 197, 147, 174, 117, 97, 149, 171, 100, 151]

44</pre>

Run-time: less than two seconds with the ldc2 compiler.

 

=={{header|Go}}==

{{trans|C}}

 

import "fmt"

func main() {

evolve(1, 30)

 

{{out}}

Assume the comonadic solution given at [[Elementary cellular automaton#Haskell]] is packed in a module <code>CellularAutomata</code>

 

import Control.Comonad

 

rnd = fromBits <$> unfoldr (pure . splitAt 8) bits

 

 

{{Out}}

Using the rule 30 CA it is possible to determine the <code>RandomGen</code> instance which could be utilized by the <code>Random</code> class:

 

 

instance RandomGen (Cycle Int) where

 

<pre>λ> let r30 = fromList [1,0,1,0,1,0,1,0,1,0,1,0,1] :: Cycle Int

=={{header|J}}==

ca is a cellular automata class. The rng class inherits ca and extends it with bit and byte verbs to sample the ca.

coclass'ca'

DOC =: 'locale creation: (RULE ; INITIAL_STATE) conew ''ca'''

byte =: [: #. [: , [: bit"0 (i.8)"_

coclass'base'

Having installed these into a j session we create and use the mathematica prng.

<pre>

m =: (30 ; 64 {. 1) conew 'rng'

byte__m"0 i.10

220 197 147 174 117 97 149 171 100 151

</pre>

=={{header|Kotlin}}==

{{trans|C}}

 

const val N = 64

fun main(args: Array<String>) {

evolve(1, 30)

 

{{out}}

220 197 147 174 117 97 149 171 100 151

</pre>

 

=={{header|Pascal}}==

{{Works with|Free Pascal}}

//http://en.wikipedia.org/wiki/Next_State_Rule_30;

//http://mathworld.wolfram.com/Rule30.html

{$IFDEF FPC}

{$OPTIMIZATION ON,ALL}

{$ELSE}

{$APPTYPE CONSOLE}

maxRounds = 2*1000*1000;

rounds = 10;

 

var

Rule30_State : Uint64;

 

procedure InitRule30_State;inline;

 

function NextRule30Byte:NativeInt;

Begin

end;

 

procedure Speedtest;

var

i: NativeInt;

Begin

writeln('Speedtest for statesize of ',64,' bits');

Next_State_Rule_30;

 

InitRule30_State;

For i := maxRounds-1 downto 0 do

NextRule30Byte;

writeln(NextRule30Byte);

writeln;

end;

writeln('The task ');

InitRule30_State;

writeln;

end;

Task;

write(' <ENTER> ');readln;

{{out}}

Speedtest for statesize of 64 bits

44

 

The task

<ENTER>

 

Speedtest for statesize of 64 bits

44

 

220 197 147 174 117 97 149 171 100 151

 

=={{header|Perl}}==

sub new {

my $class = shift;

}

print $sum, $n == 10 ? "\n" : " ";

{{out}}

<pre>220 197 147 174 117 97 149 171 240 241</pre>

and with the changes marked [2] C++, Haskell, Perl, Python, Ruby, Scheme, and Sidef, but completely different to Rust and Tcl.

No attempt to optimise.

{{out}}

<pre>

=={{header|Python}}==

===Python: With zero padded ends===

 

def rule30bytes(lencells=100):

 

if __name__ == '__main__':

 

{{out}}

 

===Python: With wrapping of end cells===

cells = '1' + '0' * (lencells - 1)

gen = eca_wrap(cells, 30)

while True:

 

{{out}}

Implementation of [[Elementary cellular automaton]] is saved in "Elementary_cellular_automata.rkt"

 

;; below is the code from the parent task

(require "Elementary_cellular_automata.rkt")

(number->string (C30-rand-64 256) 16)

(number->string (C30-rand-64 256) 16)

 

{{out}}

"6d85153a987dad6f013bc6159a41bf95b9d9b14af87733e17c702a3dc9052172"

"fc6fd302f5ea8f2fba6f476cfe9d090dc877dbd558e5afba49044d05b14d258"</pre>

 

=={{header|Ruby}}==

eca = ElemCellAutomat.new("1"+"0"*(size-1), 30)

{{out}}

<pre>

241

</pre>

=={{header|Rust}}==

//Assuming the code from the Elementary cellular automaton task is in the namespace.

fn main() {

}

}

{{out}}

<pre>

157 209 228 58 87 195 212 106 147 244

</pre>

=={{header|Scheme}}==

; uses SRFI-1 library http://srfi.schemers.org/srfi-1/srfi-1.html

 

 

(random-r30 10)

 

{{out}}

 

=={{header|Sidef}}==

 

10.times {

};

say sum;

{{out}}

<pre>

=={{header|Tcl}}==

{{works with|Tcl|8.6}}

superclass ElementaryAutomaton

variable s

return [scan [join $bits ""] %b]

}

Demonstrating:

for {set r {}} {[llength $r]<10} {} {

lappend r [$rng rand]

}

{{out}}

220,197,147,174,241,126,135,130,143,234

Note that as the number of state bits is increased (the parameter to the constructor), the sequence tends to a limit of <math>220,</math> <math>197,</math> <math>147,</math> <math>174,</math> <math>117,</math> <math>97,</math> <math>149,</math> <math>171,</math> <math>240,</math> <math>241,</math> <math>\ldots</math> and that deviations from this are due to interactions between the state modification “wavefront” as the automaton wraps round.

 

=={{header|zkl}}==

No attempts at extra credit and not fast.

fcn applyRule(rule,cells){

cells=String(cells[-1],cells,cells[0]); // wrap edges

}

n

Note that "var" in a function is "static" in C, ie function local variables, initialized once.

{{out}}

<pre>220,197,147,174,117,97,149,171,100,151,</pre>