Elementary cellular automaton/Random number generator: Difference between revisions
(added assembler optimized pascal version) |
(Added FreeBASIC) |
||
(28 intermediate revisions by 14 users not shown) | |||
Line 1: | Line 1: | ||
{{ |
{{task}} |
||
[[wp:Rule 30|Rule 30]] is considered to be chaotic enough to generate good pseudo-random numbers. As a matter of fact, rule 30 |
[[wp:Rule 30|Rule 30]] is considered to be chaotic enough to generate good pseudo-random numbers. As a matter of fact, for a long time rule 30 was used by the [[wp:Mathematica|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. |
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. |
||
Line 12: | Line 12: | ||
;Reference: |
;Reference: |
||
* [http://www.cs.indiana.edu/~dgerman/2005midwestNKSconference/dgelbm.pdf Cellular automata: Is Rule 30 random]? (PDF). |
* [http://www.cs.indiana.edu/~dgerman/2005midwestNKSconference/dgelbm.pdf Cellular automata: Is Rule 30 random]? (PDF). |
||
=={{header|11l}}== |
|||
{{trans|Nim}} |
|||
<syntaxhighlight lang="11l">V n = 64 |
|||
F pow2(x) |
|||
R UInt64(1) << x |
|||
F evolve(UInt64 =state; rule) |
|||
L 10 |
|||
V b = UInt64(0) |
|||
L(q) (7 .. 0).step(-1) |
|||
V st = state |
|||
b [|]= (st [&] 1) << q |
|||
state = 0 |
|||
L(i) 0 .< :n |
|||
V t = ((st >> (i - 1)) [|] (st << (:n + 1 - i))) [&] 7 |
|||
I (rule [&] pow2(t)) != 0 |
|||
state [|]= pow2(i) |
|||
print(‘ ’b, end' ‘’) |
|||
print() |
|||
evolve(1, 30)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
220 197 147 174 117 97 149 171 100 151 |
|||
</pre> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
64-bits array size, cyclic borders. |
64-bits array size, cyclic borders. |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <limits.h> |
#include <limits.h> |
||
Line 44: | Line 75: | ||
evolve(1, 30); |
evolve(1, 30); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 220 197 147 174 117 97 149 171 100 151</pre> |
<pre> 220 197 147 174 117 97 149 171 100 151</pre> |
||
Line 50: | Line 81: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
We'll re-write the code of the parent task here. |
We'll re-write the code of the parent task here. |
||
< |
<syntaxhighlight lang="cpp">#include <bitset> |
||
#include <stdio.h> |
#include <stdio.h> |
||
Line 87: | Line 118: | ||
printf("%u%c", byte(state), i ? ' ' : '\n'); |
printf("%u%c", byte(state), i ? ' ' : '\n'); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>220 197 147 174 117 97 149 171 240 241</pre> |
<pre>220 197 147 174 117 97 149 171 240 241</pre> |
||
Line 94: | Line 125: | ||
{{trans|C}} |
{{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. |
Adapted from the C version, with improvements and bug fixes. Optimized for performance as requested in the task description. This is a lazy range. |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.range, std.typecons; |
||
struct CellularRNG { |
struct CellularRNG { |
||
Line 145: | Line 176: | ||
CellularRNG(1, 30).take(10).writeln; |
CellularRNG(1, 30).take(10).writeln; |
||
CellularRNG(1, 30).drop(2_000_000).front.writeln; |
CellularRNG(1, 30).drop(2_000_000).front.writeln; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[220, 197, 147, 174, 117, 97, 149, 171, 100, 151] |
<pre>[220, 197, 147, 174, 117, 97, 149, 171, 100, 151] |
||
44</pre> |
44</pre> |
||
Run-time: less than two seconds with the ldc2 compiler. |
Run-time: less than two seconds with the ldc2 compiler. |
||
=={{header|FreeBASIC}}== |
|||
{{trans|Go}} |
|||
<syntaxhighlight lang="vbnet">Const n As Uinteger = 64 |
|||
#define pow2(x) Culng(1) Shl x |
|||
Sub Evolve(state As Integer, rule As Integer) |
|||
Dim As Integer i, p, q |
|||
Dim As Ulongint b, st, t1, t2, t3 |
|||
For p = 0 To 9 |
|||
b = 0 |
|||
For q = 7 To 0 Step -1 |
|||
st = state |
|||
b Or= (st And 1) Shl q |
|||
state = 0 |
|||
For i = 0 To n - 1 |
|||
t1 = Iif(i > 0, st Shr (i - 1), st Shr 63) |
|||
Select Case i |
|||
Case 0: t2 = st Shl 1 |
|||
Case 1: t2 = st Shl 63 |
|||
Case Else: t2 = st Shl (n + 1 - i) |
|||
End Select |
|||
t3 = 7 And (t1 Or t2) |
|||
If (rule And pow2(t3)) <> 0 Then state Or= pow2(i) |
|||
Next i |
|||
Next q |
|||
Print Using "####"; b; |
|||
Next p |
|||
Print |
|||
End Sub |
|||
Evolve(1, 30) |
|||
Sleep</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 220 197 147 174 117 97 149 171 100 151</pre> |
|||
=={{header|F_Sharp|F#}}== |
|||
This task uses [[Elementary cellular automaton#The_Function]] |
|||
<syntaxhighlight lang="fsharp"> |
|||
// Generate random numbers using Rule 30. Nigel Galloway: August 1st., 2019 |
|||
eca 30 [|yield 1; yield! Array.zeroCreate 99|]|>Seq.chunkBySize 8|>Seq.map(fun n->n|>Array.mapi(fun n g->g.[0]<<<(7-n))|>Array.sum)|>Seq.take 10|>Seq.iter(printf "%d "); printfn "" |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
220 197 147 174 117 97 149 171 240 241 |
|||
</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 198: | Line 278: | ||
func main() { |
func main() { |
||
evolve(1, 30) |
evolve(1, 30) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 209: | Line 289: | ||
Assume the comonadic solution given at [[Elementary cellular automaton#Haskell]] is packed in a module <code>CellularAutomata</code> |
Assume the comonadic solution given at [[Elementary cellular automaton#Haskell]] is packed in a module <code>CellularAutomata</code> |
||
< |
<syntaxhighlight lang="haskell">import CellularAutomata (fromList, rule, runCA) |
||
import Data.List (unfoldr) |
|||
import Control.Comonad |
import Control.Comonad |
||
import Data.List (unfoldr) |
|||
rnd = fromBits <$> unfoldr (pure . splitAt 8) bits |
rnd = fromBits <$> unfoldr (pure . splitAt 8) bits |
||
where |
where |
||
size = 80 |
|||
bits = extract <$> runCA (rule 30) (fromList (1:replicate size 0)) |
|||
bits = |
|||
extract |
|||
<$> runCA |
|||
(rule 30) |
|||
(fromList (1 : replicate size 0)) |
|||
fromBits = foldl ( |
fromBits = foldl ((+) . (2 *)) 0</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 225: | Line 310: | ||
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: |
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: |
||
< |
<syntaxhighlight lang="haskell">import System.Random |
||
instance RandomGen (Cycle Int) where |
instance RandomGen (Cycle Int) where |
||
next c = |
|||
next c = let x = c =>> step (rule 30) in (fromBits (view x), x) |
|||
let x = c =>> step (rule 30) |
|||
in (fromBits (view x), x) |
|||
split = (,) <*> (fromList . reverse . view)</syntaxhighlight> |
|||
<pre>λ> let r30 = fromList [1,0,1,0,1,0,1,0,1,0,1,0,1] :: Cycle Int |
<pre>λ> let r30 = fromList [1,0,1,0,1,0,1,0,1,0,1,0,1] :: Cycle Int |
||
Line 251: | Line 338: | ||
=={{header|J}}== |
=={{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. |
ca is a cellular automata class. The rng class inherits ca and extends it with bit and byte verbs to sample the ca. |
||
<syntaxhighlight lang="j"> |
|||
<lang J> |
|||
coclass'ca' |
coclass'ca' |
||
DOC =: 'locale creation: (RULE ; INITIAL_STATE) conew ''ca''' |
DOC =: 'locale creation: (RULE ; INITIAL_STATE) conew ''ca''' |
||
Line 263: | Line 350: | ||
byte =: [: #. [: , [: bit"0 (i.8)"_ |
byte =: [: #. [: , [: bit"0 (i.8)"_ |
||
coclass'base' |
coclass'base' |
||
</syntaxhighlight> |
|||
</lang> |
|||
Having installed these into a j session we create and use the mathematica prng. |
Having installed these into a j session we create and use the mathematica prng. |
||
<pre> |
<pre> |
||
m =: (30 ; 64 {. 1) conew 'rng' |
m =: (30 ; 64 {. 1) conew 'rng' |
||
byte__m"0 i.10 |
byte__m"0 i.10 |
||
220 197 147 174 117 97 149 171 100 151 |
|||
</pre> |
|||
=={{header|Java}}== |
|||
<syntaxhighlight lang="java"> |
|||
public class ElementaryCellularAutomatonRandomNumberGenerator { |
|||
public static void main(String[] aArgs) { |
|||
final int seed = 989898989; |
|||
evolve(seed, 30); |
|||
} |
|||
private static void evolve(int aState, int aRule) { |
|||
long state = aState; |
|||
for ( int i = 0; i <= 9; i++ ) { |
|||
int b = 0; |
|||
for ( int q = 7; q >= 0; q-- ) { |
|||
long stateCopy = state; |
|||
b |= ( stateCopy & 1 ) << q; |
|||
state = 0; |
|||
for ( int j = 0; j < BIT_COUNT; j++ ) { |
|||
long t = ( stateCopy >>> ( j - 1 ) ) | ( stateCopy << ( BIT_COUNT + 1 - j ) ) & 7; |
|||
if ( ( aRule & ( 1L << t ) ) != 0 ) { |
|||
state |= 1 << j; |
|||
} |
|||
} |
|||
} |
|||
System.out.print(" " + b); |
|||
} |
|||
System.out.println(); |
|||
} |
|||
private static final int BIT_COUNT = 64; |
|||
} |
|||
</syntaxhighlight> |
|||
{{ out }} |
|||
<pre> |
|||
231 223 191 126 253 251 247 239 223 191 |
|||
</pre> |
|||
=={{header|jq}}== |
|||
'''Works with jq and gojq, the C and Go implementations of jq''' |
|||
The following also works with jaq, the Rust implementation of jq, provided |
|||
the "include" directive is replaced with the set of definitions from |
|||
the parent task, and that a suitable alternative to 100*"0" is |
|||
presented. |
|||
<syntaxhighlight lang=jq> |
|||
include "elementary-cellular-automaton" {search : "."}; |
|||
# If using jq, the def of _nwise can be omitted. |
|||
def _nwise($n): |
|||
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end; |
|||
n; |
|||
# Input: an array of bits represented by 0s, 1s, "0"s, or "1"s |
|||
# Output: the corresponding decimal on the assumption that the leading bits are least significant, |
|||
# e.g. [0,1] => 2 |
|||
def binary2number: |
|||
reduce (.[]|tonumber) as $x ({p:1}; .n += .p * $x | .p *= 2) | .n; |
|||
("1" + 100 * "0" ) | [automaton(30; 80) | .[0:1]] | [_nwise(8) | reverse | binary2number] |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<pre> |
|||
[220,197,147,174,117,97,149,171,240,241] |
|||
</pre> |
|||
=={{header|Julia}}== |
|||
{{trans|C, Go}} |
|||
<syntaxhighlight lang="julia">function evolve(state, rule, N=64) |
|||
B(x) = UInt64(1) << x |
|||
for p in 0:9 |
|||
b = UInt64(0) |
|||
for q in 7:-1:0 |
|||
st = UInt64(state) |
|||
b |= (st & 1) << q |
|||
state = UInt64(0) |
|||
for i in 0:N-1 |
|||
t1 = (i > 0) ? st >> (i - 1) : st >> (N - 1) |
|||
t2 = (i == 0) ? st << 1 : (i == 1) ? st << (N - 1) : st << (N + 1 - i) |
|||
if UInt64(rule) & B(7 & (t1 | t2)) != 0 |
|||
state |= B(i) |
|||
end |
|||
end |
|||
end |
|||
print("$b ") |
|||
end |
|||
println() |
|||
end |
|||
evolve(1, 30) |
|||
</syntaxhighlight>{{out}} |
|||
<pre> |
|||
220 197 147 174 117 97 149 171 100 151 |
220 197 147 174 117 97 149 171 100 151 |
||
</pre> |
</pre> |
||
Line 273: | Line 456: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="scala">// version 1.1.51 |
||
const val N = 64 |
const val N = 64 |
||
Line 299: | Line 482: | ||
fun main(args: Array<String>) { |
fun main(args: Array<String>) { |
||
evolve(1, 30) |
evolve(1, 30) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 305: | Line 488: | ||
220 197 147 174 117 97 149 171 100 151 |
220 197 147 174 117 97 149 171 100 151 |
||
</pre> |
</pre> |
||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
|||
<syntaxhighlight lang="mathematica">FromDigits[#, 2] & /@ Partition[Flatten[CellularAutomaton[30, {{1}, 0}, {200, 0}]], 8]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>{220, 197, 147, 174, 117, 97, 149, 171, 240, 241, 92, 18, 199, 27, 104, 8, 251, 167, 29, 112, 100, 103, 159, 129, 253}</pre> |
|||
=={{header|Nim}}== |
|||
{{trans|Kotlin}} |
|||
<syntaxhighlight lang="nim">const N = 64 |
|||
template pow2(x: uint): uint = 1u shl x |
|||
proc evolve(state: uint; rule: Positive) = |
|||
var state = state |
|||
for _ in 1..10: |
|||
var b = 0u |
|||
for q in countdown(7, 0): |
|||
let st = state |
|||
b = b or (st and 1) shl q |
|||
state = 0 |
|||
for i in 0u..<N: |
|||
let t = (st shr (i - 1) or st shl (N + 1 - i)) and 7 |
|||
if (rule.uint and pow2(t)) != 0: state = state or pow2(i) |
|||
stdout.write ' ', b |
|||
echo "" |
|||
evolve(1, 30)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 220 197 147 174 117 97 149 171 100 151</pre> |
|||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
{{Works with|Free Pascal}} |
{{Works with|Free Pascal}} |
||
Using ROR and ROL is as fast as assembler and more portable.<BR>[https://tio.run/##7VZdb@pGEH33r5iHSEAvYJsQ0kBTifBxawmwC6a9bVVFjr3AKmZtrZdwaZS/Xjq7iwPckOThvvQhSHx45szMmbPD7qZBFgZxZZaG263HkzkPljBexeTcahmmuRAibZomYdU1vacpiWhQTfjclE/miHwVtxMRCHIrI26PQpaBWKwTHkfVdRLPMGs1TJamzlxdiGVsPJ45/W6vD32v82QAPJ4Nk4hAl8Tpgj49nrUnw6Hb7YEz8nsDDXA93xk6f7Z9xx2BOyq3B@gwTenqILQ9cD6PIOVJeG0/YfreYNLTgW3P8//wetBxRxN30FPOUdfpPxmrjGQImWyyqaBx1jLChGUCLcvg6zhZsSiDa6j9YFuWpT5a6OLajq9rsNFiPAQczbo3LQg0YUqZaNTRO1uxUNCEwWciOt701qdL0oSdV2xSgrF@J11hNk7ChEcGHLx@oegqH5kGiUQ3oYv6Rq29izB80lwQIBAh07aMOzKnDI1BtpQ0u/6kI6OG7m86BXiCw18I9asq9d/lXvvLKwBFBwFdCVAFAdZULHTFKFFsOMlWMda/1l0WMcibliBbxHBeg0@6gZahwg25XiRacQIOo@JQxBZlMWVk38ChE5PbL1OcGMk8iRaGr1gZR4Q8lBlC96uUl0A/SOJHPNDuYYiyu@NfpSRFmcguSZdMpF2Db11HIyExRQV2x7JOCb7gD8kl7@N5UmQbOvZmg62OAkEfiMOE/H816pUbx4cwYIDDi3PKNij4nGaC8OydLnGsNy5T0@loy807fe@X0tqHgxYfwDSnjCcxCjyHgEWgtJYPL9cB7jawQMxRzqL@@Ul/laQwUj1oj7q61HsCv7EseUevSf5B5IPIB5H/LZHj0/S9nXN/AkxSQiJBMpHv@L5d9i3c8ZzRbgukTTjYUPMNcM2pIDErFp4TwCzhkMn6Gf2HQDKDQrlRLxfgjoqsUNL73@8BX8IqlTguQCSwDu6JNOCJh4A@pqBqu9zdH9RHxcaTcs0QbeVH5qm7lCRvyeCDi4Os@uKc3BXSlZ4vLq9U2Z8rLaXOiQK5Fsfw0qGrEG7CmGSQEg7SiQIXykXfrgirZD5TaFrN2mHYy@Xyg@w@XymqbkVkTviJZfEXBASCQSv/tga2XIndNW3Xukr0TUfN@ilyeWk1CL6aJNjxzNMU4KceXkvHP0s2nATRLrqK5zNec1MakwjkQU2F8cY8Nepqlox63XgpJ16Try4MI@/bgFrNAvvqEuw6vi/rYNuXAOr5Cp9tOWJgX9hGzs04JHNe@y4ydu3H6kXju9hst/@GsziYZ9uKe76tTB7@Aw Try it online!] counting CPU-Cycles 32 vs 31 on Ryzen Zen1 per Byte -> 100Mb/s |
|||
Use 32-Bit assembler for speed. |
|||
< |
<syntaxhighlight lang="pascal">Program Rule30; |
||
//http://en.wikipedia.org/wiki/Next_State_Rule_30; |
//http://en.wikipedia.org/wiki/Next_State_Rule_30; |
||
//http://mathworld.wolfram.com/Rule30.html |
//http://mathworld.wolfram.com/Rule30.html |
||
//https://www.entwickler-ecke.de/viewtopic.php?t=111812 |
|||
{$IFDEF FPC} |
{$IFDEF FPC} |
||
{$Mode Delphi} |
{$Mode Delphi}{$ASMMODE INTEL} |
||
{$ASMMODE INTEL} |
|||
{$OPTIMIZATION ON,ALL} |
{$OPTIMIZATION ON,ALL} |
||
{$CODEALIGN proc= |
// {$CODEALIGN proc=1} |
||
{$ELSE} |
{$ELSE} |
||
{$APPTYPE CONSOLE} |
{$APPTYPE CONSOLE} |
||
Line 324: | Line 535: | ||
SysUtils; |
SysUtils; |
||
const |
const |
||
maxRounds = |
maxRounds = 2*1000*1000; |
||
rounds = 10; |
rounds = 10; |
||
var |
|||
CpuF = 3.7e9; // AMD Ph XII 955 3.2 Ghz // Ryzen 5 1600 Turbo 3.7 Ghz |
|||
Rule30_State : Uint64; |
|||
function GetCPU_Time: int64; |
|||
const |
|||
RULE30_BITSIZE = 64; |
|||
SizeOfRegister = SizeOf(NativeUint); |
|||
BitsPerRegister = 8*SizeOfRegister; |
|||
Limit32Arr = RULE30_BITSIZE DIV BitsPerRegister -1; |
|||
Limit08Arr = RULE30_BITSIZE DIV 8 -1; |
|||
type |
type |
||
TCpu = record |
|||
tLimit32 = 0..Limit32Arr+1; |
|||
HiCpu, |
|||
tLimit08 = 0..Limit08Arr+1; |
|||
LoCpu : Dword; |
|||
tArr32 = Array[tLimit32] OF Uint32; |
|||
end; |
|||
tArr08 = Array[tLimit08] OF BYTE; |
|||
tpArr08 =^tArr08; |
|||
var |
|||
{$ALIGN 32} |
|||
Rule30_State : tArr32; |
|||
procedure InitRule30_State; |
|||
var |
var |
||
Cput : TCpu; |
|||
begin |
begin |
||
asm |
|||
Rule30_State[Low(tArr32)]:= 1; |
|||
RDTSC; |
|||
For i := Low(tArr32)+1 to High(tArr32) do |
|||
MOV Dword Ptr [CpuT.LoCpu],EAX |
|||
Rule30_State[i] := 0; |
|||
MOV Dword Ptr [CpuT.HiCpu],EDX |
|||
end; |
|||
with Cput do |
|||
result := int64(HiCPU) shl 32 + LoCpu; |
|||
end; |
end; |
||
procedure InitRule30_State;inline; |
|||
function BinStr(Zahl: Uint32): String; |
|||
var |
|||
i : integer; |
|||
begin |
begin |
||
Rule30_State:= 1; |
|||
setlength(result,9); |
|||
result[1] :='_'; |
|||
For i := 0 to 7 do |
|||
begin |
|||
result[7-i+2] := chr(Zahl AND 1+Ord('0')); |
|||
Zahl := Zahl shr 1; |
|||
end; |
|||
end; |
end; |
||
procedure |
procedure Next_State_Rule_30;inline; |
||
var |
var |
||
run, prev,next: Uint64; |
|||
pArr08 :tpArr08; |
|||
begin |
begin |
||
run := Rule30_State; |
|||
Prev := RORQword(run,1); |
|||
For i := High(tLimit08)-1 Downto LOW(tLimit08) do |
|||
next := ROLQword(run,1); |
|||
write(pArr08^[i]:4,BinStr(pArr08^[i])); |
|||
Rule30_State := (next OR run) XOR prev; |
|||
write('D',BinStr(pArr08^[High(tLimit08)-1])); |
|||
writeln; |
|||
end; |
end; |
||
function |
function NextRule30Byte:NativeInt; |
||
//64-BIT can use many registers |
|||
asm |
|||
//32-Bit still fast |
|||
var |
|||
run, prev,next: Uint64; |
|||
myOne : UInt64; |
|||
Begin |
|||
run := Rule30_State; |
|||
result := 0; |
|||
myOne := 1; |
|||
//Unrolling and inlining Next_State_Rule_30 by hand |
|||
result := (result+result) OR (run AND myOne); |
|||
next := ROLQword(run,1); |
|||
Prev := RORQword(run,1); |
|||
run := (next OR run) XOR prev; |
|||
result := (result+result) OR (run AND myOne); |
|||
end; |
|||
next := ROLQword(run,1); |
|||
Prev := RORQword(run,1); |
|||
run := (next OR run) XOR prev; |
|||
result := (result+result) OR (run AND myOne); |
|||
function Next_State_Rule_30(a:pUint32):Uint32;assembler; |
|||
next := ROLQword(run,1); |
|||
//EAX = a , EDX free to use |
|||
Prev := RORQword(run,1); |
|||
//EBX Rule30_State[0] |
|||
run := (next OR run) XOR prev; |
|||
//ESI index 0..LimitArr-1 |
|||
result := (result+result) OR (run AND myOne); |
|||
//EAX value |
|||
next := ROLQword(run,1); |
|||
//ECX value one bit to the right |
|||
Prev := RORQword(run,1); |
|||
//EDX value one bit to the left |
|||
run := (next OR run) XOR prev; |
|||
//EDI next value |
|||
asm |
|||
push EBX; push ESI;push EDI; |
|||
result := (result+result) OR (run AND myOne); |
|||
MOV EBX,EAX |
|||
next := ROLQword(run,1); |
|||
MOV ESI,Limit32Arr*SizeOfRegister |
|||
Prev := RORQword(run,1); |
|||
ADD ESI,EBX |
|||
run := (next OR run) XOR prev; |
|||
result := (result+result) OR (run AND myOne); |
|||
MOV ECX,Dword Ptr [ESI]; // the highest position into previous |
|||
next := ROLQword(run,1); |
|||
MOV EAX,Dword Ptr [EBX]; // the lowest |
|||
Prev := RORQword(run,1); |
|||
MOV Dword Ptr [ESI+SizeOfRegister],EAX; // into one behind the end |
|||
run := (next OR run) XOR prev; |
|||
result := (result+result) OR (run AND myOne); |
|||
@Loop: |
|||
next := ROLQword(run,1); |
|||
MOV EDI,Dword Ptr [EBX+SizeOfRegister]; // the next |
|||
Prev := RORQword(run,1); |
|||
run := (next OR run) XOR prev; |
|||
result := (result+result) OR (run AND myOne); |
|||
BT ECX,31 // MSB of prev |
|||
next := ROLQword(run,1); |
|||
MOV ECX,EAX |
|||
Prev := RORQword(run,1); |
|||
RCL ECX,1 // shift MSB into LSB |
|||
Rule30_State := (next OR run) XOR prev; |
|||
end; |
|||
BT EDI,0 // das LSB of next |
|||
MOV EDX,EAX |
|||
RCR EDX,1 // shift LSB into MSB |
|||
OR EDX,EAX // POS[i] OR POS[i+1] |
|||
XOR ECX,EDX // POS[i] XOR (POS[i] OR POS[i+1]) |
|||
MOV Dword Ptr [EBX],ECX; // save |
|||
ADD EBX,SizeOfRegister // next Pos |
|||
cmp EBX,ESI |
|||
MOV ECX,EAX // running to previous |
|||
MOV EAX,EDI // next to running |
|||
JBE @Loop |
|||
POP EDI;POP ESI;POP EBX; |
|||
end ['EBX','ESI','EDI']; |
|||
procedure Speedtest; |
procedure Speedtest; |
||
var |
var |
||
T1,T0 : INt64; |
|||
i: NativeInt; |
|||
Begin |
Begin |
||
writeln('Speedtest for statesize of ', |
writeln('Speedtest for statesize of ',64,' bits'); |
||
//Warm up start to wake up CPU takes some time |
|||
For i := 100*1000*1000-1 downto 0 do |
|||
Next_State_Rule_30; |
|||
T0 := GetCPU_Time; |
|||
InitRule30_State; |
InitRule30_State; |
||
T0 := time; |
|||
For i := maxRounds-1 downto 0 do |
For i := maxRounds-1 downto 0 do |
||
NextRule30Byte; |
|||
dummy(@Rule30_State[0]); |
|||
T1 := |
T1 := GetCPU_Time; |
||
writeln(NextRule30Byte); |
|||
writeln('Dummy calls ',FormatDateTime('HH:NN:SS.zzz',T1-T0)); |
|||
writeln('cycles per Byte : ',(T1-t0)/maxRounds:0:2); |
|||
// Takte pro Durchlauf |
|||
writeln('cycles per call : ',((T1-t0)*86400*CpuF)/(maxRounds):0:2); |
|||
Ausgabe; |
|||
T0 := time; |
|||
For i := maxRounds-1 downto 0 do |
|||
Next_State_Rule_30(@Rule30_State[0]); |
|||
T1 := time; |
|||
Ausgabe; |
|||
writeln(maxRounds,' calls take ',FormatDateTime('HH:NN:SS.zzz',T1-T0)); |
|||
writeln('cycles per call : ',((T1-t0)*86400*CpuF)/maxRounds:0:2); |
|||
writeln; |
writeln; |
||
end; |
end; |
||
Line 457: | Line 648: | ||
procedure Task; |
procedure Task; |
||
var |
var |
||
i: integer; |
|||
Begin |
Begin |
||
writeln('The task '); |
writeln('The task '); |
||
InitRule30_State; |
InitRule30_State; |
||
For |
For i := 1 to rounds do |
||
write(NextRule30Byte:4); |
|||
Begin |
|||
b := 0; |
|||
For j := 7 downto 0 do |
|||
Begin |
|||
b := (b+b) OR (Rule30_State[0] AND 1); |
|||
Next_State_Rule_30(@Rule30_State[0]); |
|||
end; |
|||
write(b:4); |
|||
end; |
|||
writeln; |
|||
writeln; |
writeln; |
||
end; |
end; |
||
Line 478: | Line 660: | ||
SpeedTest; |
SpeedTest; |
||
Task; |
Task; |
||
readln; |
write(' <ENTER> ');readln; |
||
end.</syntaxhighlight> |
|||
end. |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre>//compiled 64-Bit |
||
Speedtest for statesize of 64 bits |
|||
Dummy calls 00:00:00.140 |
|||
44 |
|||
cycles per call : 5.18 |
|||
cycles per Byte : 30.95 |
|||
0_00000000 0_00000000 0_00000000 0_00000000 0_00000000 0_00000000 0_00000000 1_00000001D_00000000 |
|||
247_11110111 53_00110101 233_11101001 101_01100101 155_10011011 150_10010110 206_11001110 177_10110001D_11110111 |
|||
The task |
|||
100000000 calls take 00:00:00.445 |
|||
220 197 147 174 117 97 149 171 100 151 |
|||
cycles per call : 16.46 |
|||
<ENTER> |
|||
//compiled 32-Bit |
|||
Speedtest for statesize of 64 bits |
|||
44 |
|||
cycles per Byte : 128.56 |
|||
The task |
The task |
||
220 197 147 174 117 97 149 171 100 151 |
220 197 147 174 117 97 149 171 100 151 |
||
<ENTER></pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans| |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="perl">package Automaton { |
||
sub new { |
sub new { |
||
my $class = shift; |
my $class = shift; |
||
Line 531: | Line 719: | ||
} |
} |
||
print $sum, $n == 10 ? "\n" : " "; |
print $sum, $n == 10 ? "\n" : " "; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
|||
<pre>220 197 147 174 117 97 149 171 240 241</pre> |
|||
=={{header|Perl 6}}== |
|||
<lang perl6>class Automaton { |
|||
has $.rule; |
|||
has @.cells; |
|||
has @.code = $!rule.fmt('%08b').flip.comb».Int; |
|||
method gist { "|{ @!cells.map({+$_ ?? '#' !! ' '}).join }|" } |
|||
method succ { |
|||
self.new: :$!rule, :@!code, :cells( |
|||
@!code[ |
|||
4 «*« @!cells.rotate(-1) |
|||
»+« 2 «*« @!cells |
|||
»+« @!cells.rotate(1) |
|||
] |
|||
) |
|||
} |
|||
} |
|||
my Automaton $a .= new: :rule(30), :cells( flat 1, 0 xx 100 ); |
|||
say :2[$a++.cells[0] xx 8] xx 10;</lang> |
|||
{{out}} |
{{out}} |
||
<pre>220 197 147 174 117 97 149 171 240 241</pre> |
<pre>220 197 147 174 117 97 149 171 240 241</pre> |
||
Line 564: | Line 727: | ||
and with the changes marked [2] C++, Haskell, Perl, Python, Ruby, Scheme, and Sidef, but completely different to Rust and Tcl. |
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. |
No attempt to optimise. |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>--string s = ".........#.........", --(original) |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
string s = "...............................#"& |
|||
<span style="color: #000080;font-style:italic;">--string s = ".........#.........", --(original)</span> |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"...............................#"</span><span style="color: #0000FF;">&</span> |
|||
--string s = "#"&repeat('.',100), -- [2] |
|||
<span style="color: #008000;">"................................"</span><span style="color: #0000FF;">,</span> |
|||
t=s, r = "........" |
|||
<span style="color: #000080;font-style:italic;">--string s = "#"&repeat('.',100), -- [2]</span> |
|||
integer rule = 30, k, l = length(s), w = 0 |
|||
<span style="color: #000000;">t</span><span style="color: #0000FF;">=</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"........"</span> |
|||
for i=1 to 8 do |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">rule</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">30</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">w</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
r[i] = iff(mod(rule,2)?'#':'.') |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">8</span> <span style="color: #008080;">do</span> |
|||
rule = floor(rule/2) |
|||
<span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rule</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)?</span><span style="color: #008000;">'#'</span><span style="color: #0000FF;">:</span><span style="color: #008000;">'.'</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<span style="color: #000000;">rule</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rule</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> |
|||
sequence res = {} |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
for i=0 to 80 do |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
w = w*2 + (s[32]='#') |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">80</span> <span style="color: #008080;">do</span> |
|||
-- w = w*2 + (s[1]='#') -- [2] |
|||
<span style="color: #000000;">w</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">w</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span> <span style="color: #0000FF;">+</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">32</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">'#'</span><span style="color: #0000FF;">)</span> |
|||
if mod(i+1,8)=0 then res&=w w=0 end if |
|||
<span style="color: #000080;font-style:italic;">-- w = w*2 + (s[1]='#') -- [2]</span> |
|||
for j=1 to l do |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">&=</span><span style="color: #000000;">w</span> <span style="color: #000000;">w</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
k = (s[iff(j=1?l:j-1)]='#')*4 |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span> |
|||
+ (s[ j ]='#')*2 |
|||
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">?</span><span style="color: #000000;">l</span><span style="color: #0000FF;">:</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)]=</span><span style="color: #008000;">'#'</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">4</span> |
|||
+ (s[iff(j=l?1:j+1)]='#')+1 |
|||
<span style="color: #0000FF;">+</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span> <span style="color: #000000;">j</span> <span style="color: #0000FF;">]=</span><span style="color: #008000;">'#'</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">2</span> |
|||
t[j] = r[k] |
|||
<span style="color: #0000FF;">+</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">l</span><span style="color: #0000FF;">?</span><span style="color: #000000;">1</span><span style="color: #0000FF;">:</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)]=</span><span style="color: #008000;">'#'</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span> |
|||
end for |
|||
<span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> |
|||
s = t |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end for |
|||
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">t</span> |
|||
?res</lang> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 600: | Line 766: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Python: With zero padded ends=== |
===Python: With zero padded ends=== |
||
< |
<syntaxhighlight lang="python">from elementary_cellular_automaton import eca, eca_wrap |
||
def rule30bytes(lencells=100): |
def rule30bytes(lencells=100): |
||
Line 609: | Line 775: | ||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
print([b for i,b in zip(range(10), rule30bytes())])</ |
print([b for i,b in zip(range(10), rule30bytes())])</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 616: | Line 782: | ||
===Python: With wrapping of end cells=== |
===Python: With wrapping of end cells=== |
||
< |
<syntaxhighlight lang="python">def rule30bytes(lencells=100): |
||
cells = '1' + '0' * (lencells - 1) |
cells = '1' + '0' * (lencells - 1) |
||
gen = eca_wrap(cells, 30) |
gen = eca_wrap(cells, 30) |
||
while True: |
while True: |
||
yield int(''.join(next(gen)[0] for i in range(8)), 2))</ |
yield int(''.join(next(gen)[0] for i in range(8)), 2))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 629: | Line 795: | ||
Implementation of [[Elementary cellular automaton]] is saved in "Elementary_cellular_automata.rkt" |
Implementation of [[Elementary cellular automaton]] is saved in "Elementary_cellular_automata.rkt" |
||
< |
<syntaxhighlight lang="racket">#lang racket |
||
;; below is the code from the parent task |
;; below is the code from the parent task |
||
(require "Elementary_cellular_automata.rkt") |
(require "Elementary_cellular_automata.rkt") |
||
Line 668: | Line 834: | ||
(number->string (C30-rand-64 256) 16) |
(number->string (C30-rand-64 256) 16) |
||
(number->string (C30-rand-64 256) 16) |
(number->string (C30-rand-64 256) 16) |
||
(number->string (C30-rand-64 256) 16))</ |
(number->string (C30-rand-64 256) 16))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 677: | Line 843: | ||
"6d85153a987dad6f013bc6159a41bf95b9d9b14af87733e17c702a3dc9052172" |
"6d85153a987dad6f013bc6159a41bf95b9d9b14af87733e17c702a3dc9052172" |
||
"fc6fd302f5ea8f2fba6f476cfe9d090dc877dbd558e5afba49044d05b14d258"</pre> |
"fc6fd302f5ea8f2fba6f476cfe9d090dc877dbd558e5afba49044d05b14d258"</pre> |
||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
<syntaxhighlight lang="raku" line>class Automaton { |
|||
has $.rule; |
|||
has @.cells handles <AT-POS>; |
|||
has @.code = $!rule.fmt('%08b').flip.comb».Int; |
|||
method gist { "|{ @!cells.map({+$_ ?? '#' !! ' '}).join }|" } |
|||
method succ { |
|||
self.new: :$!rule, :@!code, :cells( |
|||
@!code[ |
|||
4 «*« @!cells.rotate(-1) |
|||
»+« 2 «*« @!cells |
|||
»+« @!cells.rotate(1) |
|||
] |
|||
) |
|||
} |
|||
} |
|||
my Automaton $a .= new: :rule(30), :cells( flat 1, 0 xx 100 ); |
|||
say :2[$a++[0] xx 8] xx 10;</syntaxhighlight> |
|||
{{out}} |
|||
<pre>220 197 147 174 117 97 149 171 240 241</pre> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">size = 100 |
||
eca = ElemCellAutomat.new("1"+"0"*(size-1), 30) |
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)}</ |
eca.take(80).map{|line| line[0]}.each_slice(8){|bin| p bin.join.to_i(2)}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 695: | Line 887: | ||
241 |
241 |
||
</pre> |
</pre> |
||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang="rust"> |
||
//Assuming the code from the Elementary cellular automaton task is in the namespace. |
//Assuming the code from the Elementary cellular automaton task is in the namespace. |
||
fn main() { |
fn main() { |
||
Line 718: | Line 911: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
157 209 228 58 87 195 212 106 147 244 |
157 209 228 58 87 195 212 106 147 244 |
||
</pre> |
</pre> |
||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
< |
<syntaxhighlight lang="scheme"> |
||
; uses SRFI-1 library http://srfi.schemers.org/srfi-1/srfi-1.html |
; uses SRFI-1 library http://srfi.schemers.org/srfi-1/srfi-1.html |
||
Line 744: | Line 938: | ||
(random-r30 10) |
(random-r30 10) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 753: | Line 947: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">var auto = Automaton(30, [1] + 100.of(0)); |
||
10.times { |
10.times { |
||
Line 762: | Line 956: | ||
}; |
}; |
||
say sum; |
say sum; |
||
};</ |
};</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 779: | Line 973: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
{{works with|Tcl|8.6}} |
{{works with|Tcl|8.6}} |
||
< |
<syntaxhighlight lang="tcl">oo::class create RandomGenerator { |
||
superclass ElementaryAutomaton |
superclass ElementaryAutomaton |
||
variable s |
variable s |
||
Line 795: | Line 989: | ||
return [scan [join $bits ""] %b] |
return [scan [join $bits ""] %b] |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Demonstrating: |
Demonstrating: |
||
< |
<syntaxhighlight lang="tcl">set rng [RandomGenerator new 31] |
||
for {set r {}} {[llength $r]<10} {} { |
for {set r {}} {[llength $r]<10} {} { |
||
lappend r [$rng rand] |
lappend r [$rng rand] |
||
} |
} |
||
puts [join $r ,]</ |
puts [join $r ,]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
220,197,147,174,241,126,135,130,143,234 |
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. |
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|Wren}}== |
|||
{{trans|Go}} |
|||
{{libheader|Wren-big}} |
|||
As Wren cannot deal accurately with 64-bit unsigned integers and bit-wise operations thereon, we need to use BigInt here. |
|||
<syntaxhighlight lang="wren">import "./big" for BigInt |
|||
var n = 64 |
|||
var pow2 = Fn.new { |x| BigInt.one << x } |
|||
var evolve = Fn.new { |state, rule| |
|||
for (p in 0..9) { |
|||
var b = BigInt.zero |
|||
for (q in 7..0) { |
|||
var st = state.copy() |
|||
b = b | ((st & 1) << q) |
|||
state = BigInt.zero |
|||
for (i in 0...n) { |
|||
var t1 = (i > 0) ? st >> (i-1) : st >> 63 |
|||
var t2 = (i == 0) ? st << 1 : (i == 1) ? st << 63 : st << (n+1-i) |
|||
var t3 = (t1 | t2) & 7 |
|||
if ((pow2.call(t3) & rule) != BigInt.zero) state = state | pow2.call(i) |
|||
} |
|||
} |
|||
System.write(" %(b)") |
|||
} |
|||
System.print() |
|||
} |
|||
evolve.call(BigInt.one, 30)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
220 197 147 174 117 97 149 171 100 151 |
|||
</pre> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
No attempts at extra credit and not fast. |
No attempts at extra credit and not fast. |
||
< |
<syntaxhighlight lang="zkl">fcn rule(n){ n=n.toString(2); "00000000"[n.len() - 8,*] + n } |
||
fcn applyRule(rule,cells){ |
fcn applyRule(rule,cells){ |
||
cells=String(cells[-1],cells,cells[0]); // wrap edges |
cells=String(cells[-1],cells,cells[0]); // wrap edges |
||
Line 821: | Line 1,051: | ||
} |
} |
||
n |
n |
||
}</ |
}</syntaxhighlight> |
||
Note that "var" in a function is "static" in C, ie function local variables, initialized once. |
Note that "var" in a function is "static" in C, ie function local variables, initialized once. |
||
< |
<syntaxhighlight lang="zkl">do(10){ rand30().print(","); }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>220,197,147,174,117,97,149,171,100,151,</pre> |
<pre>220,197,147,174,117,97,149,171,100,151,</pre> |
Latest revision as of 09:10, 17 March 2024
You are encouraged to solve this task according to the task description, using any language you may know.
Rule 30 is considered to be chaotic enough to generate good pseudo-random numbers. As a matter of fact, for a long time rule 30 was 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
11l
V n = 64
F pow2(x)
R UInt64(1) << x
F evolve(UInt64 =state; rule)
L 10
V b = UInt64(0)
L(q) (7 .. 0).step(-1)
V st = state
b [|]= (st [&] 1) << q
state = 0
L(i) 0 .< :n
V t = ((st >> (i - 1)) [|] (st << (:n + 1 - i))) [&] 7
I (rule [&] pow2(t)) != 0
state [|]= pow2(i)
print(‘ ’b, end' ‘’)
print()
evolve(1, 30)
- Output:
220 197 147 174 117 97 149 171 100 151
C
64-bits array size, cyclic borders.
#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;
}
- Output:
220 197 147 174 117 97 149 171 100 151
C++
We'll re-write the code of the parent task here.
#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;
}
- 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.
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;
}
- Output:
[220, 197, 147, 174, 117, 97, 149, 171, 100, 151] 44
Run-time: less than two seconds with the ldc2 compiler.
FreeBASIC
Const n As Uinteger = 64
#define pow2(x) Culng(1) Shl x
Sub Evolve(state As Integer, rule As Integer)
Dim As Integer i, p, q
Dim As Ulongint b, st, t1, t2, t3
For p = 0 To 9
b = 0
For q = 7 To 0 Step -1
st = state
b Or= (st And 1) Shl q
state = 0
For i = 0 To n - 1
t1 = Iif(i > 0, st Shr (i - 1), st Shr 63)
Select Case i
Case 0: t2 = st Shl 1
Case 1: t2 = st Shl 63
Case Else: t2 = st Shl (n + 1 - i)
End Select
t3 = 7 And (t1 Or t2)
If (rule And pow2(t3)) <> 0 Then state Or= pow2(i)
Next i
Next q
Print Using "####"; b;
Next p
Print
End Sub
Evolve(1, 30)
Sleep
- Output:
220 197 147 174 117 97 149 171 100 151
F#
This task uses Elementary cellular automaton#The_Function
// Generate random numbers using Rule 30. Nigel Galloway: August 1st., 2019
eca 30 [|yield 1; yield! Array.zeroCreate 99|]|>Seq.chunkBySize 8|>Seq.map(fun n->n|>Array.mapi(fun n g->g.[0]<<<(7-n))|>Array.sum)|>Seq.take 10|>Seq.iter(printf "%d "); printfn ""
- Output:
220 197 147 174 117 97 149 171 240 241
Go
package main
import "fmt"
const n = 64
func pow2(x uint) uint64 {
return uint64(1) << x
}
func evolve(state uint64, rule int) {
for p := 0; p < 10; p++ {
b := uint64(0)
for q := 7; q >= 0; q-- {
st := state
b |= (st & 1) << uint(q)
state = 0
for i := uint(0); i < n; i++ {
var t1, t2, t3 uint64
if i > 0 {
t1 = st >> (i - 1)
} else {
t1 = st >> 63
}
if i == 0 {
t2 = st << 1
} else if i == 1 {
t2 = st << 63
} else {
t2 = st << (n + 1 - i)
}
t3 = 7 & (t1 | t2)
if (uint64(rule) & pow2(uint(t3))) != 0 {
state |= pow2(i)
}
}
}
fmt.Printf("%d ", b)
}
fmt.Println()
}
func main() {
evolve(1, 30)
}
- Output:
220 197 147 174 117 97 149 171 100 151
Haskell
Assume the comonadic solution given at Elementary cellular automaton#Haskell is packed in a module CellularAutomata
import CellularAutomata (fromList, rule, runCA)
import Control.Comonad
import Data.List (unfoldr)
rnd = fromBits <$> unfoldr (pure . splitAt 8) bits
where
size = 80
bits =
extract
<$> runCA
(rule 30)
(fromList (1 : replicate size 0))
fromBits = foldl ((+) . (2 *)) 0
- Output:
λ> take 10 rnd [220,197,147,174,117,97,149,171,240,241]
Using the rule 30 CA it is possible to determine the RandomGen
instance which could be utilized by the Random
class:
import System.Random
instance RandomGen (Cycle Int) where
next c =
let x = c =>> step (rule 30)
in (fromBits (view x), x)
split = (,) <*> (fromList . reverse . view)
λ> let r30 = fromList [1,0,1,0,1,0,1,0,1,0,1,0,1] :: Cycle Int λ> take 15 $ randoms r30 [7509,4949,2517,2229,2365,2067,6753,5662,5609,7576,2885,3017,2912,5081,2356] λ> take 30 $ randomRs ('A','J') r30 "DHJHHFJHBDDFCBHACHDEHDHFBAEJFE"
We can compare it with standard generator on a small integer range, using simple bin counter:
λ> let bins lst = [ (n, length (filter (==n) lst)) | n <- nub lst] λ> bins . take 10000 . randomRs ('A','J') $ r30 [('D',1098),('H',1097),('J',1093),('F',850),('B',848),('C',1014),('A',1012),('E',1011),('G',1253),('I',724)] λ> bins . take 10000 . randomRs ('A','J') <$> getStdGen [('G',975),('B',1035),('F',970),('J',1034),('I',956),('H',984),('C',1009),('E',1023),('A',1009),('D',1005)]
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'''
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'
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
Java
public class ElementaryCellularAutomatonRandomNumberGenerator {
public static void main(String[] aArgs) {
final int seed = 989898989;
evolve(seed, 30);
}
private static void evolve(int aState, int aRule) {
long state = aState;
for ( int i = 0; i <= 9; i++ ) {
int b = 0;
for ( int q = 7; q >= 0; q-- ) {
long stateCopy = state;
b |= ( stateCopy & 1 ) << q;
state = 0;
for ( int j = 0; j < BIT_COUNT; j++ ) {
long t = ( stateCopy >>> ( j - 1 ) ) | ( stateCopy << ( BIT_COUNT + 1 - j ) ) & 7;
if ( ( aRule & ( 1L << t ) ) != 0 ) {
state |= 1 << j;
}
}
}
System.out.print(" " + b);
}
System.out.println();
}
private static final int BIT_COUNT = 64;
}
- Output:
231 223 191 126 253 251 247 239 223 191
jq
Works with jq and gojq, the C and Go implementations of jq
The following also works with jaq, the Rust implementation of jq, provided the "include" directive is replaced with the set of definitions from the parent task, and that a suitable alternative to 100*"0" is presented.
include "elementary-cellular-automaton" {search : "."};
# If using jq, the def of _nwise can be omitted.
def _nwise($n):
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end;
n;
# Input: an array of bits represented by 0s, 1s, "0"s, or "1"s
# Output: the corresponding decimal on the assumption that the leading bits are least significant,
# e.g. [0,1] => 2
def binary2number:
reduce (.[]|tonumber) as $x ({p:1}; .n += .p * $x | .p *= 2) | .n;
("1" + 100 * "0" ) | [automaton(30; 80) | .[0:1]] | [_nwise(8) | reverse | binary2number]
- Output:
[220,197,147,174,117,97,149,171,240,241]
Julia
function evolve(state, rule, N=64)
B(x) = UInt64(1) << x
for p in 0:9
b = UInt64(0)
for q in 7:-1:0
st = UInt64(state)
b |= (st & 1) << q
state = UInt64(0)
for i in 0:N-1
t1 = (i > 0) ? st >> (i - 1) : st >> (N - 1)
t2 = (i == 0) ? st << 1 : (i == 1) ? st << (N - 1) : st << (N + 1 - i)
if UInt64(rule) & B(7 & (t1 | t2)) != 0
state |= B(i)
end
end
end
print("$b ")
end
println()
end
evolve(1, 30)
- Output:
220 197 147 174 117 97 149 171 100 151
Kotlin
// version 1.1.51
const val N = 64
fun pow2(x: Int) = 1L shl x
fun evolve(state: Long, rule: Int) {
var state2 = state
for (p in 0..9) {
var b = 0
for (q in 7 downTo 0) {
val st = state2
b = (b.toLong() or ((st and 1L) shl q)).toInt()
state2 = 0L
for (i in 0 until N) {
val t = ((st ushr (i - 1)) or (st shl (N + 1 - i)) and 7L).toInt()
if ((rule.toLong() and pow2(t)) != 0L) state2 = state2 or pow2(i)
}
}
print(" $b")
}
println()
}
fun main(args: Array<String>) {
evolve(1, 30)
}
- Output:
220 197 147 174 117 97 149 171 100 151
Mathematica / Wolfram Language
FromDigits[#, 2] & /@ Partition[Flatten[CellularAutomaton[30, {{1}, 0}, {200, 0}]], 8]
- Output:
{220, 197, 147, 174, 117, 97, 149, 171, 240, 241, 92, 18, 199, 27, 104, 8, 251, 167, 29, 112, 100, 103, 159, 129, 253}
Nim
const N = 64
template pow2(x: uint): uint = 1u shl x
proc evolve(state: uint; rule: Positive) =
var state = state
for _ in 1..10:
var b = 0u
for q in countdown(7, 0):
let st = state
b = b or (st and 1) shl q
state = 0
for i in 0u..<N:
let t = (st shr (i - 1) or st shl (N + 1 - i)) and 7
if (rule.uint and pow2(t)) != 0: state = state or pow2(i)
stdout.write ' ', b
echo ""
evolve(1, 30)
- Output:
220 197 147 174 117 97 149 171 100 151
Pascal
Using ROR and ROL is as fast as assembler and more portable.
Try it online! counting CPU-Cycles 32 vs 31 on Ryzen Zen1 per Byte -> 100Mb/s
Program Rule30;
//http://en.wikipedia.org/wiki/Next_State_Rule_30;
//http://mathworld.wolfram.com/Rule30.html
{$IFDEF FPC}
{$Mode Delphi}{$ASMMODE INTEL}
{$OPTIMIZATION ON,ALL}
// {$CODEALIGN proc=1}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
uses
SysUtils;
const
maxRounds = 2*1000*1000;
rounds = 10;
var
Rule30_State : Uint64;
function GetCPU_Time: int64;
type
TCpu = record
HiCpu,
LoCpu : Dword;
end;
var
Cput : TCpu;
begin
asm
RDTSC;
MOV Dword Ptr [CpuT.LoCpu],EAX
MOV Dword Ptr [CpuT.HiCpu],EDX
end;
with Cput do
result := int64(HiCPU) shl 32 + LoCpu;
end;
procedure InitRule30_State;inline;
begin
Rule30_State:= 1;
end;
procedure Next_State_Rule_30;inline;
var
run, prev,next: Uint64;
begin
run := Rule30_State;
Prev := RORQword(run,1);
next := ROLQword(run,1);
Rule30_State := (next OR run) XOR prev;
end;
function NextRule30Byte:NativeInt;
//64-BIT can use many registers
//32-Bit still fast
var
run, prev,next: Uint64;
myOne : UInt64;
Begin
run := Rule30_State;
result := 0;
myOne := 1;
//Unrolling and inlining Next_State_Rule_30 by hand
result := (result+result) OR (run AND myOne);
next := ROLQword(run,1);
Prev := RORQword(run,1);
run := (next OR run) XOR prev;
result := (result+result) OR (run AND myOne);
next := ROLQword(run,1);
Prev := RORQword(run,1);
run := (next OR run) XOR prev;
result := (result+result) OR (run AND myOne);
next := ROLQword(run,1);
Prev := RORQword(run,1);
run := (next OR run) XOR prev;
result := (result+result) OR (run AND myOne);
next := ROLQword(run,1);
Prev := RORQword(run,1);
run := (next OR run) XOR prev;
result := (result+result) OR (run AND myOne);
next := ROLQword(run,1);
Prev := RORQword(run,1);
run := (next OR run) XOR prev;
result := (result+result) OR (run AND myOne);
next := ROLQword(run,1);
Prev := RORQword(run,1);
run := (next OR run) XOR prev;
result := (result+result) OR (run AND myOne);
next := ROLQword(run,1);
Prev := RORQword(run,1);
run := (next OR run) XOR prev;
result := (result+result) OR (run AND myOne);
next := ROLQword(run,1);
Prev := RORQword(run,1);
Rule30_State := (next OR run) XOR prev;
end;
procedure Speedtest;
var
T1,T0 : INt64;
i: NativeInt;
Begin
writeln('Speedtest for statesize of ',64,' bits');
//Warm up start to wake up CPU takes some time
For i := 100*1000*1000-1 downto 0 do
Next_State_Rule_30;
T0 := GetCPU_Time;
InitRule30_State;
For i := maxRounds-1 downto 0 do
NextRule30Byte;
T1 := GetCPU_Time;
writeln(NextRule30Byte);
writeln('cycles per Byte : ',(T1-t0)/maxRounds:0:2);
writeln;
end;
procedure Task;
var
i: integer;
Begin
writeln('The task ');
InitRule30_State;
For i := 1 to rounds do
write(NextRule30Byte:4);
writeln;
end;
Begin
SpeedTest;
Task;
write(' <ENTER> ');readln;
end.
- Output:
//compiled 64-Bit Speedtest for statesize of 64 bits 44 cycles per Byte : 30.95 The task 220 197 147 174 117 97 149 171 100 151 <ENTER> //compiled 32-Bit Speedtest for statesize of 64 bits 44 cycles per Byte : 128.56 The task 220 197 147 174 117 97 149 171 100 151 <ENTER>
Perl
package Automaton {
sub new {
my $class = shift;
my $rule = [ reverse split //, sprintf "%08b", shift ];
return bless { rule => $rule, cells => [ @_ ] }, $class;
}
sub next {
my $this = shift;
my @previous = @{$this->{cells}};
$this->{cells} = [
@{$this->{rule}}[
map {
4*$previous[($_ - 1) % @previous]
+ 2*$previous[$_]
+ $previous[($_ + 1) % @previous]
} 0 .. @previous - 1
]
];
return $this;
}
use overload
q{""} => sub {
my $this = shift;
join '', map { $_ ? '#' : ' ' } @{$this->{cells}}
};
}
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" : " ";
}
- Output:
220 197 147 174 117 97 149 171 240 241
Phix
Making the minimum possible changes to Elementary_cellular_automaton#Phix, output matches C, D, Go, J, Kotlin, Racket, and zkl, 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.
with javascript_semantics --string s = ".........#.........", --(original) string s = "...............................#"& "................................", --string s = "#"&repeat('.',100), -- [2] t=s, r = "........" integer rule = 30, k, l = length(s), w = 0 for i=1 to 8 do r[i] = iff(mod(rule,2)?'#':'.') rule = floor(rule/2) end for sequence res = {} for i=0 to 80 do w = w*2 + (s[32]='#') -- w = w*2 + (s[1]='#') -- [2] if mod(i+1,8)=0 then res&=w w=0 end if for j=1 to l do k = (s[iff(j=1?l:j-1)]='#')*4 + (s[ j ]='#')*2 + (s[iff(j=l?1:j+1)]='#')+1 t[j] = r[k] end for s = t end for pp(res)
- Output:
{220,197,147,174,117,97,149,171,100,151}
- Output:
with the changes marked [2]
{220,197,147,174,117,97,149,171,240,241}
Python
Python: With zero padded ends
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())])
- Output:
[255, 255, 255, 255, 255, 255, 255, 255, 255, 255]
!
Python: With wrapping of end cells
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))
- 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
;; below is the code from the parent task
(require "Elementary_cellular_automata.rkt")
(require racket/fixnum)
;; This is the RNG automaton
(define (CA30-random-generator
#:rule [rule 30] ; rule 30 is random, maybe you're interested in using others
;; width of the CA... this is implemented as a number of words plus,
;; maybe, another word containing the spare bits
#:bits [bits 256])
(define-values [full-words more-bits]
(quotient/remainder bits usable-bits/fixnum))
(define wrap-rule
(and (positive? more-bits) (wrap-rule-truncate-left-word more-bits)))
(define next-gen (CA-next-generation 30 #:wrap-rule wrap-rule))
(define v (make-fxvector (+ full-words (if more-bits 1 0))))
(fxvector-set! v 0 1) ; this bit will always have significance
(define (next-word)
(define-values [v+ o] (next-gen v 0))
(begin0 (fxvector-ref v 0) (set! v v+)))
(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
;; To match the other examples on this page, the automaton is 30+30+4 bits long
;; (i.e. 64 bits)
(define C30-rand-64 (CA30-random-generator #:bits 64))
;; this should be the list from "C"
(for/list ([i 10]) (C30-rand-64 8))
; we also do big numbers...
(number->string (C30-rand-64 256) 16)
(number->string (C30-rand-64 256) 16)
(number->string (C30-rand-64 256) 16)
(number->string (C30-rand-64 256) 16))
- Output:
(220 197 147 174 117 97 149 171 100 151) "ecd9fbcdcc34604d833950deb58447124b98706e74ccc74d9337cb4e53f38c5e" "9c8b6471a4bc2cb3508f10b6635e4eb959ad8bbe484480695e8ddb5795f956a" "6d85153a987dad6f013bc6159a41bf95b9d9b14af87733e17c702a3dc9052172" "fc6fd302f5ea8f2fba6f476cfe9d090dc877dbd558e5afba49044d05b14d258"
Raku
(formerly Perl 6)
class Automaton {
has $.rule;
has @.cells handles <AT-POS>;
has @.code = $!rule.fmt('%08b').flip.comb».Int;
method gist { "|{ @!cells.map({+$_ ?? '#' !! ' '}).join }|" }
method succ {
self.new: :$!rule, :@!code, :cells(
@!code[
4 «*« @!cells.rotate(-1)
»+« 2 «*« @!cells
»+« @!cells.rotate(1)
]
)
}
}
my Automaton $a .= new: :rule(30), :cells( flat 1, 0 xx 100 );
say :2[$a++[0] xx 8] xx 10;
- Output:
220 197 147 174 117 97 149 171 240 241
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)}
- Output:
220 197 147 174 117 97 149 171 240 241
Rust
//Assuming the code from the Elementary cellular automaton task is in the namespace.
fn main() {
struct WolfGen(ElementaryCA);
impl WolfGen {
fn new() -> WolfGen {
let (_, ca) = ElementaryCA::new(30);
WolfGen(ca)
}
fn next(&mut self) -> u8 {
let mut out = 0;
for i in 0..8 {
out |= ((1 & self.0.next())<<i)as u8;
}
out
}
}
let mut gen = WolfGen::new();
for _ in 0..10 {
print!("{} ", gen.next());
}
}
- Output:
157 209 228 58 87 195 212 106 147 244
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)
- Output:
(220 197 147 174 117 97 149 171 240 241)
Sidef
var auto = Automaton(30, [1] + 100.of(0));
10.times {
var sum = 0;
8.times {
sum = (2*sum + auto.cells[0]);
auto.next;
};
say sum;
};
- Output:
220 197 147 174 117 97 149 171 240 241
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]
}
}
Demonstrating:
set rng [RandomGenerator new 31]
for {set r {}} {[llength $r]<10} {} {
lappend r [$rng rand]
}
puts [join $r ,]
- 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.
Wren
As Wren cannot deal accurately with 64-bit unsigned integers and bit-wise operations thereon, we need to use BigInt here.
import "./big" for BigInt
var n = 64
var pow2 = Fn.new { |x| BigInt.one << x }
var evolve = Fn.new { |state, rule|
for (p in 0..9) {
var b = BigInt.zero
for (q in 7..0) {
var st = state.copy()
b = b | ((st & 1) << q)
state = BigInt.zero
for (i in 0...n) {
var t1 = (i > 0) ? st >> (i-1) : st >> 63
var t2 = (i == 0) ? st << 1 : (i == 1) ? st << 63 : st << (n+1-i)
var t3 = (t1 | t2) & 7
if ((pow2.call(t3) & rule) != BigInt.zero) state = state | pow2.call(i)
}
}
System.write(" %(b)")
}
System.print()
}
evolve.call(BigInt.one, 30)
- Output:
220 197 147 174 117 97 149 171 100 151
zkl
No attempts at extra credit and not fast.
fcn rule(n){ n=n.toString(2); "00000000"[n.len() - 8,*] + n }
fcn applyRule(rule,cells){
cells=String(cells[-1],cells,cells[0]); // wrap edges
(cells.len() - 2).pump(String,'wrap(n){ rule[7 - cells[n,3].toInt(2)] })
}
fcn rand30{
var r30=rule(30), cells="0"*63 + 1; // 64 bits (8 bytes), arbitrary
n:=0;
do(8){
n=n*2 + cells[-1]; // append bit 0
cells=applyRule(r30,cells); // next state
}
n
}
Note that "var" in a function is "static" in C, ie function local variables, initialized once.
do(10){ rand30().print(","); }
- Output:
220,197,147,174,117,97,149,171,100,151,