Pseudo-random numbers/Splitmix64: Difference between revisions
Content added Content deleted
m (→{{header|Wren}}: Minor tidy) |
|||
Line 732: | Line 732: | ||
} |
} |
||
exec test(0x1000:8)</syntaxhighlight> |
exec test(0x1000:8)</syntaxhighlight> |
||
=={{header|jq}}== |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
'''Adapted from [[#Wren|Wren]]''' |
|||
This entry assumes sufficiently precise integer arithmetic, e.g. as provided by gojq, |
|||
which supports infinite-precision integer arithmetic. |
|||
Unfortunately, though, gojq does not support efficient bitwise operations, and using |
|||
the following to generate 100,000 random numbers takes about 17 minutes on a 3GHz machine. |
|||
The main significance of this entry is thus to increase confidence in the correctness of the |
|||
definitions as well as in the Go implementation of jq. |
|||
In the following, a 'bitarray' is a 0/1 array, and when integers are represented by bitarrays, the first bit is the least-significant one. Unless otherwise indicated, the bitwise operations work on bitarrays. |
|||
'''Generic utilities''' |
|||
<syntaxhighlight lang="jq"> |
|||
# Input: a string in base $b (2 to 35 inclusive) |
|||
# Output: a JSON number, being the decimal value corresponding to the input. |
|||
def frombase($b): |
|||
def decimalValue: |
|||
if 48 <= . and . <= 57 then . - 48 |
|||
elif 65 <= . and . <= 90 then . - 55 # (10+.-65) |
|||
elif 97 <= . and . <= 122 then . - 87 # (10+.-97) |
|||
else "decimalValue" | error |
|||
end; |
|||
reduce (explode|reverse[]|decimalValue) as $x ({p:1}; |
|||
.value += (.p * $x) |
|||
| .p *= $b) |
|||
| .value ; |
|||
# To take advantage of gojq's arbitrary-precision integer arithmetic: |
|||
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in); |
|||
# If the input and $j are integers, then the result will be an integer. |
|||
def div($j): |
|||
(. - (. % j)) / $j; |
|||
# Convert an integer to a bitarray, least significant bit first |
|||
def bitwise: |
|||
recurse( if . >= 2 then div(2) else empty end) | . % 2; |
|||
# Essentially the inverse of bitwise, |
|||
# i.e. interpret an array of 0s and 1s (with least-significant-bit first ) as a decimal |
|||
def to_int: |
|||
. as $in |
|||
# state: [sum, power] |
|||
| reduce .[] as $i ([0, 1]; .[1] as $p | [.[0] + $p * $i, ($p * 2)]) |
|||
| .[0]; |
|||
# $x and $y and output are bitarrays |
|||
def xor($x;$y): |
|||
def lxor(a;b): |
|||
if (a==1 or b==1) and ((a==1 and b==1)|not) then 1 |
|||
elif a == null then b |
|||
elif b == null then a |
|||
else 0 |
|||
end; |
|||
if $x == [0] then $y |
|||
elif $y == [0] then $x |
|||
else |
|||
[ range(0; [($x|length), ($y|length)] | max) as $i |
|||
| lxor($x[$i]; $y[$i]) ] |
|||
end ; |
|||
# $x and $y and output are bitarrays |
|||
def xand($x;$y): |
|||
def lxand(a;b): |
|||
(a==1 and b==1) | 1 // 0; |
|||
if $x == [0] or $y == [0] then [0] |
|||
else |
|||
[range(0; [($x|length), ($y|length)] | min) as $i |
|||
| lxand($x[$i]; $y[$i]) ] |
|||
end ; |
|||
# shift right |
|||
def right($n): .[$n:]; |
|||
def mask64: .[:64]; |
|||
# input and output: a bitarray |
|||
def mult($int): |
|||
($int * to_int) | [bitwise]; |
|||
def plus($int): |
|||
($int + to_int) | [bitwise]; |
|||
def tabulate(stream): |
|||
reduce stream as $i ([]; .[$i] += 1) |
|||
| range(0;length) as $i |
|||
| " \($i) : \(.[$i] // 0)" ; |
|||
</syntaxhighlight> |
|||
'''Splitmix64''' |
|||
<syntaxhighlight lang="jq"> |
|||
# input: a bitarray |
|||
def nextInt: |
|||
def Const1: "9e3779b97f4a7c15" | frombase(16) ; |
|||
def Const2: "bf58476d1ce4e5b9" | frombase(16) ; |
|||
def Const3: "94d049bb133111eb" | frombase(16) ; |
|||
(plus(Const1) | mask64) |
|||
| . as $state |
|||
| xor(.; right(30)) | mult(Const2) | mask64 |
|||
| xor(.; right(27)) | mult(Const3) | mask64 |
|||
| xor(.; right(31)) | mask64 |
|||
| ., ($state|nextInt) ; |
|||
def randomInt64: [bitwise] | nextInt | to_int; |
|||
def randomReal: |
|||
pow(2;64) as $d |
|||
| [bitwise] | nextInt | to_int / $d; |
|||
### The tasks |
|||
(limit(5; 1234567 | randomInt64)), |
|||
"\nThe counts for 100,000 repetitions are:", |
|||
tabulate( limit(100; 987654321 | randomReal * 5 | floor) ) |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<pre> |
|||
6457827717110365317 |
|||
3203168211198807973 |
|||
9817491932198370423 |
|||
4593380528125082431 |
|||
16408922859458223821 |
|||
The counts for 100,000 repetitions are: |
|||
0 : 20027 |
|||
1 : 19892 |
|||
2 : 20073 |
|||
3 : 19978 |
|||
4 : 20030 |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |