Elementary cellular automaton/Random number generator: Difference between revisions
m (→{{header|Racket}}: stub added) |
|||
Line 224: | Line 224: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
Implementation of [[Elementary cellular automaton]] is saved in "Elementary_cellular_automata.rkt" |
|||
⚫ | |||
</lang> |
|||
⚫ | |||
; below is the code from the parent task |
|||
(require "Elementary_cellular_automata.rkt") |
|||
(require racket/fixnum) |
|||
;; This is the RNG automaton |
|||
(define ng/30 (CA-next-generation 30)) |
|||
(define (random-usable-bits) (random (fxlshift 1 usable-bits/fixnum-1))) |
|||
(define CA30-rand |
|||
(let ((v ; seed CA state -- I'd expect the period of a wider automaton to be larger |
|||
; maybe even as high as 2^(30*4) -- who knows? |
|||
(fxvector (random-usable-bits) (random-usable-bits) (random-usable-bits) (random-usable-bits)))) |
|||
(define (next-word) |
|||
(define-values (v+ o) (ng/30 v 0)) |
|||
(set! v v+) |
|||
(fxvector-ref v 0)) |
|||
;; make sure all bits have affected each other |
|||
(for ((i (* usable-bits/fixnum-1 (fxvector-length v)))) (next-word)) |
|||
(lambda (bits) |
|||
(for/fold ((acc 0)) |
|||
((_ (in-range bits))) |
|||
;; the CA is fixnum, but this function returns integers of arbitrary width |
|||
(bitwise-ior (arithmetic-shift acc 1) (bitwise-and (next-word) 1)))))) |
|||
(module+ main |
|||
(CA30-rand 32) |
|||
(CA30-rand 32) |
|||
(CA30-rand 32) |
|||
(CA30-rand 32) |
|||
; we also do big numbers... |
|||
(number->string (CA30-rand 256) 16) |
|||
(number->string (CA30-rand 256) 16) |
|||
(number->string (CA30-rand 256) 16) |
|||
(number->string (CA30-rand 256) 16))</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre>2849574621 |
||
1863474554 |
|||
</pre> |
|||
2735907428 |
|||
1999558413 |
|||
"790cffff341e073a195bec90d411437b80ede7be3953765b3059c158eb12bbc5" |
|||
"c014dc24b52f5c7e305dd2b4e7b753af1107b88f8055dd1c3cdb81f806e62fb2" |
|||
"414ff56f551747b740e7fb4d0613cd9d645db546e783cbf77d026724e1e8ee5" |
|||
"9a3224043946601f7181c1a6efdeed5fb45f8deb76c339bfff73ad281160bc7d"</pre> |
|||
Random. Obviously <code>:-)</code> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
Revision as of 19:26, 12 January 2015
Rule 30 is considered to be chaotic enough to generate good pseudo-random numbers. As a matter of fact, rule 30 is used by the Mathematica software for its default random number generator.
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.
The purpose of this task is to demonstrate this. With the code written in the parent task, which you don't need to re-write here, show the ten first bytes that emerge from this recommendation. To be precise, you will start with a state of all cells but one equal to zero, and you'll follow the evolution of the particular cell whose state was initially one. Then you'll regroup those bits by packets of eight, reconstituting bytes with the first bit being the most significant.
You can pick which ever length you want for the initial array but it should be visible in the code so that your output can be reproduced with an other language.
For extra-credits, you will make this algorithm run as fast as possible in your language, for instance with an extensive use of bitwise logic.
- Reference
C
64-bits array size, cyclic borders. <lang c>#include <stdio.h>
- include <limits.h>
typedef unsigned long long ull;
- define N (sizeof(ull) * CHAR_BIT)
- define B(x) (1ULL << (x))
void evolve(ull state, int rule) { int i, p, q, b;
for (p = 0; p < 10; p++) { for (b = 0, q = 8; q--; ) { ull st = state; b |= (st&1) << q;
for (state = i = 0; i < N; i++) if (rule & B(7 & (st>>(i-1) | st<<(N+1-i)))) state |= B(i); } printf(" %d", b); } putchar('\n'); return; }
int main(void) { evolve(1, 30); return 0; }</lang>
- Output:
220 197 147 174 117 97 149 171 100 151
C++
We'll re-write the code of the parent task here. <lang cpp>#include <bitset>
- include <stdio.h>
- define SIZE 80
- define RULE 30
- define RULE_TEST(x) (RULE & 1 << (7 & (x)))
void evolve(std::bitset<SIZE> &s) {
int i; std::bitset<SIZE> t(0); t[SIZE-1] = RULE_TEST( s[0] << 2 | s[SIZE-1] << 1 | s[SIZE-2] ); t[ 0] = RULE_TEST( s[1] << 2 | s[ 0] << 1 | s[SIZE-1] ); for (i = 1; i < SIZE-1; i++)
t[i] = RULE_TEST( s[i+1] << 2 | s[i] << 1 | s[i-1] );
for (i = 0; i < SIZE; i++) s[i] = t[i];
} void show(std::bitset<SIZE> s) {
int i; for (i = SIZE; i--; ) printf("%c", s[i] ? '#' : ' '); printf("|\n");
} unsigned char byte(std::bitset<SIZE> &s) {
unsigned char b = 0; int i; for (i=8; i--; ) {
b |= s[0] << i; evolve(s);
} return b;
}
int main() {
int i; std::bitset<SIZE> state(1); for (i=10; i--; )
printf("%u%c", byte(state), i ? ' ' : '\n');
return 0;
}</lang>
- Output:
220 197 147 174 117 97 149 171 240 241
D
Adapted from the C version, with improvements and bug fixes. Optimized for performance as requested in the task description. This is a lazy range. <lang d>import std.stdio, std.range, std.typecons;
struct CellularRNG {
private uint current; private immutable uint rule; private ulong state;
this(in ulong state_, in uint rule_) pure nothrow @safe @nogc { this.state = state_; this.rule = rule_; popFront; }
public enum bool empty = false; @property uint front() pure nothrow @safe @nogc { return current; }
void popFront() pure nothrow @safe @nogc { enum uint nBit = 8; enum uint NU = ulong.sizeof * nBit; current = 0;
foreach_reverse (immutable i; 0 .. nBit) { immutable state2 = state; current |= (state2 & 1) << i;
state = 0; /*static*/ foreach (immutable j; staticIota!(0, NU)) { // To avoid undefined behavior with out-of-range shifts. static if (j > 0) immutable aux1 = state2 >> (j - 1); else immutable aux1 = state2 >> 63;
static if (j == 0) immutable aux2 = state2 << 1; else static if (j == 1) immutable aux2 = state2 << 63; else immutable aux2 = state2 << (NU + 1 - j);
immutable aux = 7 & (aux1 | aux2); if (rule & (1UL << aux)) state |= 1UL << j; } } }
}
void main() {
CellularRNG(1, 30).take(10).writeln; CellularRNG(1, 30).drop(2_000_000).front.writeln;
}</lang>
- Output:
[220, 197, 147, 174, 117, 97, 149, 171, 100, 151] 44
Run-time: less than two seconds with the ldc2 compiler.
J
ca is a cellular automata class. The rng class inherits ca and extends it with bit and byte verbs to sample the ca. <lang J> coclass'ca' DOC =: 'locale creation: (RULE ; INITIAL_STATE) conew ca' create =: 3 :'RULE STATE =: y' next =: 3 :'STATE =: RULE (((8$2) #: [) {~ [: #. [: -. [: |: |.~"1 0&_1 0 1@]) STATE' coclass'base'
coclass'rng' coinsert'ca' bit =: 3 :'([ next) ({. STATE)' byte =: [: #. [: , [: bit"0 (i.8)"_ coclass'base' </lang> Having installed these into a j session we create and use the mathematica prng.
m =: (30 ; 64 {. 1) conew 'rng' byte__m"0 i.10 220 197 147 174 117 97 149 171 100 151
Perl
<lang perl>my $a = Automaton->new(30, 1, map 0, 1 .. 100);
for my $n (1 .. 10) {
my $sum = 0; for my $b (1 .. 8) {
$sum = $sum * 2 + $a->{cells}[0]; $a->next;
} print $sum, $n == 10 ? "\n" : " ";
}</lang>
- Output:
220 197 147 174 117 97 149 171 240 241
Perl 6
<lang perl6>my Automaton $a .= new: :rule(30), :cells( 1, 0 xx 100 );
say :2[$a++.cells[0] xx 8] xx 10;</lang>
- Output:
220 197 147 174 117 97 149 171 240 241
Python
Python: With zero padded ends
<lang python>from elementary_cellular_automaton import eca, eca_wrap
def rule30bytes(lencells=100):
cells = '1' + '0' * (lencells - 1) gen = eca(cells, 30) while True: yield int(.join(next(gen)[0] for i in range(8)), 2)
if __name__ == '__main__':
print([b for i,b in zip(range(10), rule30bytes())])</lang>
- Output:
[255, 255, 255, 255, 255, 255, 255, 255, 255, 255]
!
Python: With wrapping of end cells
<lang python>def rule30bytes(lencells=100):
cells = '1' + '0' * (lencells - 1) gen = eca_wrap(cells, 30) while True: yield int(.join(next(gen)[0] for i in range(8)), 2))</lang>
- Output:
[220, 197, 147, 174, 117, 97, 149, 171, 240, 241]
Racket
Implementation of Elementary cellular automaton is saved in "Elementary_cellular_automata.rkt"
<lang racket>#lang racket
- below is the code from the parent task
(require "Elementary_cellular_automata.rkt") (require racket/fixnum)
- This is the RNG automaton
(define ng/30 (CA-next-generation 30)) (define (random-usable-bits) (random (fxlshift 1 usable-bits/fixnum-1))) (define CA30-rand
(let ((v ; seed CA state -- I'd expect the period of a wider automaton to be larger ; maybe even as high as 2^(30*4) -- who knows? (fxvector (random-usable-bits) (random-usable-bits) (random-usable-bits) (random-usable-bits)))) (define (next-word) (define-values (v+ o) (ng/30 v 0)) (set! v v+) (fxvector-ref v 0)) ;; make sure all bits have affected each other (for ((i (* usable-bits/fixnum-1 (fxvector-length v)))) (next-word)) (lambda (bits) (for/fold ((acc 0)) ((_ (in-range bits))) ;; the CA is fixnum, but this function returns integers of arbitrary width (bitwise-ior (arithmetic-shift acc 1) (bitwise-and (next-word) 1))))))
(module+ main
(CA30-rand 32) (CA30-rand 32) (CA30-rand 32) (CA30-rand 32) ; we also do big numbers... (number->string (CA30-rand 256) 16) (number->string (CA30-rand 256) 16) (number->string (CA30-rand 256) 16) (number->string (CA30-rand 256) 16))</lang>
- Output:
2849574621 1863474554 2735907428 1999558413 "790cffff341e073a195bec90d411437b80ede7be3953765b3059c158eb12bbc5" "c014dc24b52f5c7e305dd2b4e7b753af1107b88f8055dd1c3cdb81f806e62fb2" "414ff56f551747b740e7fb4d0613cd9d645db546e783cbf77d026724e1e8ee5" "9a3224043946601f7181c1a6efdeed5fb45f8deb76c339bfff73ad281160bc7d"
Random. Obviously :-)
Ruby
<lang ruby>size = 100 eca = ElemCellAutomat.new("1"+"0"*(size-1), 30) eca.take(80).map{|line| line[0]}.each_slice(8){|bin| p bin.join.to_i(2)}</lang>
- Output:
220 197 147 174 117 97 149 171 240 241
Scheme
<lang scheme>
- uses SRFI-1 library http://srfi.schemers.org/srfi-1/srfi-1.html
(define (random-r30 n)
(let ((r30 (vector 0 1 1 1 1 0 0 0))) (fold (lambda (x y ls)
(if (= x 1) (cons (* x y) ls) (cons (+ (car ls) (* x y)) (cdr ls))))
'() (circular-list 1 2 4 8 16 32 64 128) (unfold-right
(lambda (x) (zero? (car x))) cadr (lambda (x) (cons (- (car x) 1) (evolve (cdr x) r30))) (cons (* 8 n) (cons 1 (make-list 79 0))))))) ; list
(random-r30 10) </lang>
- Output:
(220 197 147 174 117 97 149 171 240 241)
Tcl
<lang tcl>oo::class create RandomGenerator {
superclass ElementaryAutomaton variable s constructor {stateLength} {
next 30 set s [split 1[string repeat 0 $stateLength] ""]
}
method rand {} {
set bits {} while {[llength $bits] < 8} { lappend bits [lindex $s 0] set s [my evolve $s] } return [scan [join $bits ""] %b]
}
}</lang> Demonstrating: <lang tcl>set rng [RandomGenerator new 31] for {set r {}} {[llength $r]<10} {} {
lappend r [$rng rand]
} puts [join $r ,]</lang>
- Output:
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 and that deviations from this are due to interactions between the state modification “wavefront” as the automaton wraps round.