Pseudo-random numbers/Xorshift star: Difference between revisions
(11 intermediate revisions by 11 users not shown) | |||
Line 27: | Line 27: | ||
/* Let u64 denote an unsigned 64 bit integer type. */ |
/* Let u64 denote an unsigned 64 bit integer type. */ |
||
/* Let u32 denote an unsigned 32 bit integer type. */ |
/* Let u32 denote an unsigned 32 bit integer type. */ |
||
class Xorshift_star |
class Xorshift_star |
||
u64 state /* Must be seeded to non-zero initial value */ |
u64 state /* Must be seeded to non-zero initial value */ |
||
u64 const = HEX '2545F4914F6CDD1D' |
u64 const = HEX '2545F4914F6CDD1D' |
||
method seed(u64 num): |
method seed(u64 num): |
||
state = num |
state = num |
||
Line 87: | Line 86: | ||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="11l">T XorShiftStar |
||
UInt64 state |
UInt64 state |
||
Line 113: | Line 112: | ||
L 100'000 |
L 100'000 |
||
hist[Int(random_gen.next_float() * 5)]++ |
hist[Int(random_gen.next_float() * 5)]++ |
||
print(hist)</ |
print(hist)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 127: | Line 126: | ||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
Raises Unseeded_Error exception if state is not initialized before generating a pseudo-random value. |
Raises Unseeded_Error exception if state is not initialized before generating a pseudo-random value. |
||
< |
<syntaxhighlight lang="ada">with Interfaces; use Interfaces; |
||
with Ada.Text_IO; use Ada.Text_IO; |
with Ada.Text_IO; use Ada.Text_IO; |
||
Line 179: | Line 178: | ||
end Main; |
end Main; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{output}} |
{{output}} |
||
<pre> |
<pre> |
||
Line 198: | Line 197: | ||
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}} |
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}} |
||
Will generate a runtime error if state is not initialised before use. |
Will generate a runtime error if state is not initialised before use. |
||
< |
<syntaxhighlight lang="algol68">BEGIN # generate some pseudo random numbers using Xorshift star # |
||
# note that although LONG INT is 64 bits in Algol 68G, LONG BITS is longer than 64 bits # |
# note that although LONG INT is 64 bits in Algol 68G, LONG BITS is longer than 64 bits # |
||
LONG BITS state; |
LONG BITS state; |
||
Line 236: | Line 235: | ||
print( ( newline ) ) |
print( ( newline ) ) |
||
END |
END |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 248: | Line 247: | ||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<syntaxhighlight lang="c">#include <math.h> |
||
#include <stdint.h> |
#include <stdint.h> |
||
#include <stdio.h> |
#include <stdio.h> |
||
Line 299: | Line 298: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3540625527 |
<pre>3540625527 |
||
Line 315: | Line 314: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="cpp">#include <array> |
||
#include <cstdint> |
#include <cstdint> |
||
#include <iostream> |
#include <iostream> |
||
Line 368: | Line 367: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3540625527 |
<pre>3540625527 |
||
Line 384: | Line 383: | ||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang="d">import std.math; |
||
import std.stdio; |
import std.stdio; |
||
Line 433: | Line 432: | ||
writeln(i, ": ", v); |
writeln(i, ": ", v); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3540625527 |
<pre>3540625527 |
||
Line 446: | Line 445: | ||
3: 20031 |
3: 20031 |
||
4: 20007</pre> |
4: 20007</pre> |
||
=={{header|Delphi}}== |
|||
{{libheader| System.SysUtils}} |
|||
{{libheader| System.Math}} |
|||
{{Trans|Go}} |
|||
<syntaxhighlight lang="delphi"> |
|||
program Xorshift_star; |
|||
{$APPTYPE CONSOLE} |
|||
uses |
|||
System.SysUtils, |
|||
System.Math; |
|||
type |
|||
TXorshiftStar = record |
|||
private |
|||
state: uint64; |
|||
const |
|||
k = $2545F4914F6CDD1D; |
|||
public |
|||
constructor Create(aState: uint64); |
|||
procedure Seed(aState: uint64); |
|||
function NextInt: uint32; |
|||
function NextFloat: Extended; |
|||
end; |
|||
{ TXorshiftStar } |
|||
constructor TXorshiftStar.Create(aState: uint64); |
|||
begin |
|||
Seed(aState); |
|||
end; |
|||
function TXorshiftStar.NextFloat: Extended; |
|||
begin |
|||
Result := NextInt() / $100000000; |
|||
end; |
|||
function TXorshiftStar.NextInt: uint32; |
|||
var |
|||
x: UInt64; |
|||
begin |
|||
x := state; |
|||
x := x xor (x shr 12); |
|||
x := x xor (x shl 25); |
|||
x := x xor (x shr 27); |
|||
state := x; |
|||
Result := uint32((x * k) shr 32); |
|||
end; |
|||
procedure TXorshiftStar.Seed(aState: uint64); |
|||
begin |
|||
state := aState; |
|||
end; |
|||
begin |
|||
var randomGen := TXorshiftStar.Create(1234567); |
|||
for var i := 0 to 4 do |
|||
writeln(randomGen.NextInt); |
|||
var counts := [0, 0, 0, 0, 0]; |
|||
randomGen.seed(987654321); |
|||
for var i := 1 to 100000 do |
|||
begin |
|||
var j := Floor(randomGen.nextFloat() * 5); |
|||
inc(counts[j]); |
|||
end; |
|||
writeln(#10'The counts for 100,000 repetitions are:'); |
|||
for var i := 0 to 4 do |
|||
writeln(format(' %d : %d', [i, counts[i]])); |
|||
{$IFNDEF UNIX} Readln; {$ENDIF} |
|||
end.</syntaxhighlight> |
|||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
===The Functions=== |
===The Functions=== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Xorshift star. Nigel Galloway: August 14th., 2020 |
// Xorshift star. Nigel Galloway: August 14th., 2020 |
||
let fN=(fun(n:uint64)->n^^^(n>>>12))>>(fun n->n^^^(n<<<25))>>(fun n->n^^^(n>>>27)) |
let fN=(fun(n:uint64)->n^^^(n>>>12))>>(fun n->n^^^(n<<<25))>>(fun n->n^^^(n>>>27)) |
||
let Xstar32=Seq.unfold(fun n->let n=fN n in Some(uint32((n*0x2545F4914F6CDD1DUL)>>>32),n)) |
let Xstar32=Seq.unfold(fun n->let n=fN n in Some(uint32((n*0x2545F4914F6CDD1DUL)>>>32),n)) |
||
let XstarF n=Xstar32 n|>Seq.map(fun n->(float n)/4294967296.0) |
let XstarF n=Xstar32 n|>Seq.map(fun n->(float n)/4294967296.0) |
||
</syntaxhighlight> |
|||
</lang> |
|||
===The Tasks=== |
===The Tasks=== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
Xstar32 1234567UL|>Seq.take 5|>Seq.iter(printfn "%d") |
Xstar32 1234567UL|>Seq.take 5|>Seq.iter(printfn "%d") |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 467: | Line 544: | ||
3809424708 |
3809424708 |
||
</pre> |
</pre> |
||
< |
<syntaxhighlight lang="fsharp"> |
||
XstarF 987654321UL|>Seq.take 100000|>Seq.countBy(fun n->int(n*5.0))|>Seq.iter(printf "%A");printfn "" |
XstarF 987654321UL|>Seq.take 100000|>Seq.countBy(fun n->int(n*5.0))|>Seq.iter(printf "%A");printfn "" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 476: | Line 553: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang="factor">USING: accessors kernel literals math math.statistics |
||
prettyprint sequences ; |
prettyprint sequences ; |
||
Line 506: | Line 583: | ||
987654321 >>state |
987654321 >>state |
||
100,000 [ dup next-float 5 * >integer ] replicate nip |
100,000 [ dup next-float 5 * >integer ] replicate nip |
||
histogram .</ |
histogram .</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 516: | Line 593: | ||
H{ { 0 20103 } { 1 19922 } { 2 19937 } { 3 20031 } { 4 20007 } } |
H{ { 0 20103 } { 1 19922 } { 2 19937 } { 3 20031 } { 4 20007 } } |
||
</pre> |
</pre> |
||
=={{header|FreeBASIC}}== |
|||
<syntaxhighlight lang="vbnet">#define floor(x) ((x*2.0-0.5) Shr 1) |
|||
Const As Ulongint mask64 = &HFFFFFFFFFFFFFFFF |
|||
Const As Ulongint mask32 = &HFFFFFFFF |
|||
Const As Ulongint cte = &H2545F4914F6CDD1D |
|||
Dim Shared As Ulongint state |
|||
Sub seed(num As Ulongint) |
|||
state = num And mask64 |
|||
End Sub |
|||
Function next_int() As Ulongint |
|||
Dim As Ulongint x = state |
|||
x = (x Xor (x Shr 12)) And mask64 |
|||
x = (x Xor (x Shl 25)) And mask64 |
|||
x = (x Xor (x Shr 27)) And mask64 |
|||
state = x |
|||
Dim As Ulongint answer = (((x * cte) And mask64) Shr 32) And mask32 |
|||
Return answer |
|||
End Function |
|||
Function next_float() As Double |
|||
Return next_int() / (2 ^ 32) |
|||
End Function |
|||
Dim As Integer i, hist(4) |
|||
seed(1234567) |
|||
For i = 1 To 5 |
|||
Print next_int() |
|||
Next i |
|||
Print !"\nThe counts for 100,000 repetitions are:" |
|||
seed(987654321) |
|||
For i = 1 To 100000 |
|||
hist(floor(next_float() * 5)) += 1 |
|||
Next i |
|||
For i = 0 To 4 |
|||
Print Using "hist(#) = #####"; i; hist(i) |
|||
Next i |
|||
Sleep</syntaxhighlight> |
|||
{{out}} |
|||
<pre>3540625527 |
|||
2750739987 |
|||
4037983143 |
|||
1993361440 |
|||
3809424708 |
|||
The counts for 100,000 repetitions are: |
|||
hist(0) = 20103 |
|||
hist(1) = 19922 |
|||
hist(2) = 19937 |
|||
hist(3) = 20031 |
|||
hist(4) = 20007</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 563: | Line 698: | ||
fmt.Printf(" %d : %d\n", i, counts[i]) |
fmt.Printf(" %d : %d\n", i, counts[i]) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 580: | Line 715: | ||
4 : 20007 |
4 : 20007 |
||
</pre> |
</pre> |
||
=={{header|Haskell}}== |
|||
Implement given algorithm as an instance of <code>RandomGen</code> class. |
|||
<syntaxhighlight lang="haskell">import Data.Bits |
|||
import Data.Word |
|||
import System.Random |
|||
import Data.List |
|||
newtype XorShift = XorShift Word64 |
|||
instance RandomGen XorShift where |
|||
next (XorShift state) = (out newState, XorShift newState) |
|||
where |
|||
newState = (\z -> z `xor` (z `shiftR` 27)) . |
|||
(\z -> z `xor` (z `shiftL` 25)) . |
|||
(\z -> z `xor` (z `shiftR` 12)) $ state |
|||
out x = fromIntegral $ (x * 0x2545f4914f6cdd1d) `shiftR` 32 |
|||
split _ = error "XorShift is not splittable" |
|||
randoms' :: RandomGen g => g -> [Int] |
|||
randoms' = unfoldr (pure . next) |
|||
toFloat n = fromIntegral n / (2^32 - 1)</syntaxhighlight> |
|||
Direct usage of generator: |
|||
<pre>*Main> mapM_ print $ take 5 $ randoms' (XorShift 1234567) |
|||
3540625527 |
|||
2750739987 |
|||
4037983143 |
|||
1993361440 |
|||
3809424708 |
|||
*Main> let hist = map length . group . sort |
|||
*Main> hist . take 100000 $ (floor . (*5) . toFloat) <$> (randoms' (XorShift 987654321)) |
|||
[20103,19922,19937,20031,20007]</pre> |
|||
Using <code>Random</code> class gives different results due to internal shuffling: |
|||
<pre>*Main> mapM_ print $ take 5 $ randoms (XorShift 1234567) |
|||
2750739987 |
|||
1993361440 |
|||
1794978290 |
|||
626183142 |
|||
2911384526 |
|||
*Main> let hist = map length . group . sort |
|||
*Main> hist . take 100000 $ (floor . (*5)) <$> (randoms (XorShift 987654321) :: [Float]) |
|||
[20263,19783,19949,19957,20048]</pre> |
|||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang="java">public class XorShiftStar { |
||
private static final long MAGIC = Long.parseUnsignedLong("2545F4914F6CDD1D", 16); |
private static final long MAGIC = Long.parseUnsignedLong("2545F4914F6CDD1D", 16); |
||
private long state; |
private long state; |
||
Line 629: | Line 815: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3540625527 |
<pre>3540625527 |
||
Line 642: | Line 828: | ||
3: 20031 |
3: 20031 |
||
4: 20007</pre> |
4: 20007</pre> |
||
=={{header|jq}}== |
|||
'''Adapted from [[#Wren|Wren]]''' |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
The following program |
|||
uses the [[:Category:jq/bitwise.jq | "bitwise" module]]. |
|||
<syntaxhighlight lang="jq"> |
|||
include "bitwise" {search: "."}; # see above |
|||
def Const: 2685821657736338717; # i.e. 0x2545F4914F6CDD1D |
|||
def Mask64: 18446744073709551615; # i.e. (1 | leftshift(64)) - 1 |
|||
def Mask32: 4294967295; # i.e. (1 | leftshift(32)) - 1 |
|||
# Emit a suitable {state} object |
|||
def seed($num): |
|||
{state: bitwise_and($num; Mask64)}; |
|||
# Input: {state} |
|||
# Output: {state, nextInt} |
|||
def nextInt: |
|||
.state |= bitwise_and(bitwise_xor(.; rightshift(12)); Mask64) |
|||
| .state |= bitwise_and(bitwise_xor(.; leftshift( 25)); Mask64) |
|||
| .state |= bitwise_and(bitwise_xor(.; rightshift(27)); Mask64) |
|||
| .nextInt = bitwise_and( bitwise_and(.state * Const; Mask64) | rightshift(32); Mask32) ; |
|||
# Input: {state} |
|||
# Output: {state, nextInt, nextFloat} |
|||
def nextFloat: |
|||
nextInt |
|||
| .nextFloat = (.nextInt / (pow(2;32))); |
|||
def task1: |
|||
foreach range(0; 5) as $i (seed(1234567); |
|||
nextInt; |
|||
.nextInt); |
|||
def task2($max): |
|||
reduce range(0; $max) as $i (seed(987654321); |
|||
nextFloat |
|||
| ((.nextFloat * 5)|floor) as $n |
|||
| .counts[$n] += 1) |
|||
| "\nThe counts for \($max) repetitions are:", |
|||
(range(0; 5) as $i | "\($i) : \(.counts[$i])") ; |
|||
task1, "", task2(100000) |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<pre> |
|||
3540625527 |
|||
2750739987 |
|||
4037983143 |
|||
1993361440 |
|||
3809424708 |
|||
The counts for 100000 repetitions are: |
|||
0 : 20103 |
|||
1 : 19922 |
|||
2 : 19937 |
|||
3 : 20031 |
|||
4 : 20007 |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="julia">const mask32 = (0x1 << 32) - 1 |
||
const CONST = 0x2545F4914F6CDD1D |
const CONST = 0x2545F4914F6CDD1D |
||
Line 682: | Line 931: | ||
testXorShiftStar() |
testXorShiftStar() |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
3540625527 |
3540625527 |
||
Line 691: | Line 940: | ||
0: 20103 1: 19922 2: 19937 3: 20031 4: 20007 |
0: 20103 1: 19922 2: 19937 3: 20031 4: 20007 |
||
</pre> |
</pre> |
||
=={{header|Kotlin}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="scala">import kotlin.math.floor |
|||
class XorShiftStar { |
|||
private var state = 0L |
|||
fun seed(num: Long) { |
|||
state = num |
|||
} |
|||
fun nextInt(): Int { |
|||
var x = state |
|||
x = x xor (x ushr 12) |
|||
x = x xor (x shl 25) |
|||
x = x xor (x ushr 27) |
|||
state = x |
|||
return (x * MAGIC shr 32).toInt() |
|||
} |
|||
fun nextFloat(): Float { |
|||
return nextInt().toUInt().toFloat() / (1L shl 32) |
|||
} |
|||
companion object { |
|||
private const val MAGIC = 0x2545F4914F6CDD1D |
|||
} |
|||
} |
|||
fun main() { |
|||
val rng = XorShiftStar() |
|||
rng.seed(1234567) |
|||
println(rng.nextInt().toUInt()) |
|||
println(rng.nextInt().toUInt()) |
|||
println(rng.nextInt().toUInt()) |
|||
println(rng.nextInt().toUInt()) |
|||
println(rng.nextInt().toUInt()) |
|||
println() |
|||
rng.seed(987654321) |
|||
val counts = arrayOf(0, 0, 0, 0, 0) |
|||
for (i in 1..100000) { |
|||
val j = floor(rng.nextFloat() * 5.0).toInt() |
|||
counts[j]++ |
|||
} |
|||
for (iv in counts.withIndex()) { |
|||
println("${iv.index}: ${iv.value}") |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>3540625527 |
|||
2750739987 |
|||
4037983143 |
|||
1993361440 |
|||
3809424708 |
|||
0: 20103 |
|||
1: 19922 |
|||
2: 19937 |
|||
3: 20031 |
|||
4: 20007</pre> |
|||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="lua">function create() |
||
local g = { |
local g = { |
||
magic = 0x2545F4914F6CDD1D, |
magic = 0x2545F4914F6CDD1D, |
||
Line 734: | Line 1,047: | ||
for i,v in pairs(counts) do |
for i,v in pairs(counts) do |
||
print(i..': '..v) |
print(i..': '..v) |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3540625527 |
<pre>3540625527 |
||
Line 747: | Line 1,060: | ||
3: 20031 |
3: 20031 |
||
4: 20007</pre> |
4: 20007</pre> |
||
=={{header|Nim}}== |
|||
<syntaxhighlight lang="nim">import algorithm, sequtils, strutils, tables |
|||
const C = 0x2545F4914F6CDD1Du64 |
|||
type XorShift = object |
|||
state: uint64 |
|||
func seed(gen: var XorShift; num: uint64) = |
|||
gen.state = num |
|||
func nextInt(gen: var XorShift): uint32 = |
|||
var x = gen.state |
|||
x = x xor x shr 12 |
|||
x = x xor x shl 25 |
|||
x = x xor x shr 27 |
|||
gen.state = x |
|||
result = uint32((x * C) shr 32) |
|||
func nextFloat(gen: var XorShift): float = |
|||
gen.nextInt().float / float(0xFFFFFFFFu32) |
|||
when isMainModule: |
|||
var gen: XorShift |
|||
gen.seed(1234567) |
|||
for _ in 1..5: |
|||
echo gen.nextInt() |
|||
echo "" |
|||
gen.seed(987654321) |
|||
var counts: CountTable[int] |
|||
for _ in 1..100_000: |
|||
counts.inc int(gen.nextFloat() * 5) |
|||
echo sorted(toSeq(counts.pairs)).mapIt($it[0] & ": " & $it[1]).join(", ")</syntaxhighlight> |
|||
{{out}} |
|||
<pre>3540625527 |
|||
2750739987 |
|||
4037983143 |
|||
1993361440 |
|||
3809424708 |
|||
0: 20103, 1: 19922, 2: 19937, 3: 20031, 4: 20007</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
no warnings 'portable'; |
no warnings 'portable'; |
||
Line 786: | Line 1,147: | ||
$rng = Xorshift_star->new(seed => 987654321); |
$rng = Xorshift_star->new(seed => 987654321); |
||
$h{int 5 * $rng->next_float}++ for 1 .. 100_000; |
$h{int 5 * $rng->next_float}++ for 1 .. 100_000; |
||
say "$_ $h{$_}" for sort keys %h;</ |
say "$_ $h{$_}" for sort keys %h;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Seed: 1234567, first 5 values: |
<pre>Seed: 1234567, first 5 values: |
||
Line 804: | Line 1,165: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
As per [[Pseudo-random_numbers/PCG32#Phix]], resorting to mpfr/gmp |
As per [[Pseudo-random_numbers/PCG32#Phix]], resorting to mpfr/gmp |
||
{{libheader|Phix/mpfr}} |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
mpz const = mpz_init("0x2545F4914F6CDD1D"), |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
state = mpz_init(), |
|||
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
|||
b64 = mpz_init("0x10000000000000000"), -- (truncate to 64 bits) |
|||
<span style="color: #004080;">mpz</span> <span style="color: #000000;">cmult</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"0x2545F4914F6CDD1D"</span><span style="color: #0000FF;">),</span> |
|||
b32 = mpz_init("0x100000000"), -- (truncate to 32 bits) |
|||
<span style="color: #000000;">state</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span> |
|||
tmp = mpz_init(), |
|||
<span style="color: #000000;">b64</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"0x10000000000000000"</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- (truncate to 64 bits)</span> |
|||
x = mpz_init() |
|||
<span style="color: #000000;">b32</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"0x100000000"</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- (truncate to 32 bits)</span> |
|||
<span style="color: #000000;">tmp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span> |
|||
procedure seed(integer num) |
|||
<span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span> |
|||
mpz_set_si(state,num) |
|||
end procedure |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">seed</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">num</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">mpz_set_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">state</span><span style="color: #0000FF;">,</span><span style="color: #000000;">num</span><span style="color: #0000FF;">)</span> |
|||
function next_int() |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
mpz_set(x,state) -- x := state |
|||
mpz_tdiv_q_2exp(tmp, x, 12) -- tmp := trunc(x/2^12) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">next_int</span><span style="color: #0000FF;">()</span> |
|||
mpz_xor(x, x, tmp) -- x := xor_bits(x,tmp) |
|||
<span style="color: #7060A8;">mpz_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">state</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- x := state</span> |
|||
mpz_mul_2exp(tmp, x, 25) -- tmp := x * 2^25. |
|||
<span style="color: #7060A8;">mpz_tdiv_q_2exp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">12</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- tmp := trunc(x/2^12)</span> |
|||
mpz_xor(x, x, tmp) -- x := xor_bits(x,tmp) |
|||
<span style="color: #7060A8;">mpz_xor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tmp</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- x := xor_bits(x,tmp)</span> |
|||
mpz_fdiv_r(x, x, b64) -- x := remainder(x,b64) |
|||
<span style="color: #7060A8;">mpz_mul_2exp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">25</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- tmp := x * 2^25.</span> |
|||
mpz_tdiv_q_2exp(tmp, x, 27) -- tmp := trunc(x/2^27) |
|||
<span style="color: #7060A8;">mpz_xor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tmp</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- x := xor_bits(x,tmp)</span> |
|||
mpz_xor(x, x, tmp) -- x := xor_bits(x,tmp) |
|||
<span style="color: #7060A8;">mpz_fdiv_r</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b64</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- x := remainder(x,b64) </span> |
|||
mpz_fdiv_r(state, x, b64) -- state := remainder(x,b64) |
|||
<span style="color: #7060A8;">mpz_tdiv_q_2exp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">27</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- tmp := trunc(x/2^27)</span> |
|||
mpz_mul(x,x,const) -- x *= const |
|||
<span style="color: #7060A8;">mpz_xor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tmp</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- x := xor_bits(x,tmp)</span> |
|||
mpz_tdiv_q_2exp(x, x, 32) -- x := trunc(x/2^32) |
|||
<span style="color: #7060A8;">mpz_fdiv_r</span><span style="color: #0000FF;">(</span><span style="color: #000000;">state</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b64</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- state := remainder(x,b64) </span> |
|||
mpz_fdiv_r(x, x, b32) -- x := remainder(x,b32) |
|||
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cmult</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- x *= cmult</span> |
|||
return mpz_get_atom(x) |
|||
<span style="color: #7060A8;">mpz_tdiv_q_2exp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">32</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- x := trunc(x/2^32)</span> |
|||
end function |
|||
<span style="color: #7060A8;">mpz_fdiv_r</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b32</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- x := remainder(x,b32) </span> |
|||
<span style="color: #008080;">return</span> <span style="color: #7060A8;">mpz_get_atom</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span> |
|||
function next_float() |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
return next_int() / (1 << 32) |
|||
end function |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">next_float</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">next_int</span><span style="color: #0000FF;">()</span> <span style="color: #0000FF;">/</span> <span style="color: #000000;">#100000000</span> |
|||
seed(1234567) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
for i=1 to 5 do |
|||
printf(1,"%d\n",next_int()) |
|||
<span style="color: #000000;">seed</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1234567</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<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;">5</span> <span style="color: #008080;">do</span> |
|||
seed(987654321) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">next_int</span><span style="color: #0000FF;">())</span> |
|||
sequence r = repeat(0,5) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
for i=1 to 100000 do |
|||
<span style="color: #000000;">seed</span><span style="color: #0000FF;">(</span><span style="color: #000000;">987654321</span><span style="color: #0000FF;">)</span> |
|||
r[floor(next_float()*5)+1] += 1 |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<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;">100000</span> <span style="color: #008080;">do</span> |
|||
?r</lang> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">next_float</span><span style="color: #0000FF;">()*</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span> |
|||
<span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">r</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 857: | Line 1,223: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python">mask64 = (1 << 64) - 1 |
||
mask32 = (1 << 32) - 1 |
mask32 = (1 << 32) - 1 |
||
const = 0x2545F4914F6CDD1D |
const = 0x2545F4914F6CDD1D |
||
Line 896: | Line 1,262: | ||
for i in range(100_000): |
for i in range(100_000): |
||
hist[int(random_gen.next_float() *5)] += 1 |
hist[int(random_gen.next_float() *5)] += 1 |
||
print(hist)</ |
print(hist)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 912: | Line 1,278: | ||
Raku does not have unsigned Integers at this time (Integers are arbitrary sized) so use explicit bit masks during bitwise operations. All constants are encapsulated inside the class. |
Raku does not have unsigned Integers at this time (Integers are arbitrary sized) so use explicit bit masks during bitwise operations. All constants are encapsulated inside the class. |
||
<lang |
<syntaxhighlight lang="raku" line>class Xorshift-star { |
||
has $!state; |
has $!state; |
||
Line 942: | Line 1,308: | ||
say "\nSeed: default; first five Int values"; |
say "\nSeed: default; first five Int values"; |
||
$rng = Xorshift-star.new; |
$rng = Xorshift-star.new; |
||
.say for $rng.next-int xx 5;</ |
.say for $rng.next-int xx 5;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Seed: 1234567; first five Int values |
<pre>Seed: 1234567; first five Int values |
||
Line 963: | Line 1,329: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
< |
<syntaxhighlight lang="rexx">/*REXX program generates pseudo─random numbers using the XOR─shift─star method. */ |
||
numeric digits 200 /*ensure enough decimal digs for mult. */ |
numeric digits 200 /*ensure enough decimal digs for mult. */ |
||
parse arg n reps pick seed1 seed2 . /*obtain optional arguments from the CL*/ |
parse arg n reps pick seed1 seed2 . /*obtain optional arguments from the CL*/ |
||
Line 1,012: | Line 1,378: | ||
xor: parse arg a, b; $= /*perform a bit─wise XOR. */ |
xor: parse arg a, b; $= /*perform a bit─wise XOR. */ |
||
do !=1 for length(a); $= $ || (substr(a,!,1) && substr(b,!,1) ) |
do !=1 for length(a); $= $ || (substr(a,!,1) && substr(b,!,1) ) |
||
end /*!*/; return $</ |
end /*!*/; return $</syntaxhighlight> |
||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
Line 1,034: | Line 1,400: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
Using Ruby 3.0 end-les method def: |
Using Ruby 3.0 end-les method def: |
||
< |
<syntaxhighlight lang="ruby">class Xorshift_star |
||
MASK64 = (1 << 64) - 1 |
MASK64 = (1 << 64) - 1 |
||
MASK32 = (1 << 32) - 1 |
MASK32 = (1 << 32) - 1 |
||
Line 1,059: | Line 1,425: | ||
tally = Hash.new(0) |
tally = Hash.new(0) |
||
100_000.times{ tally[(random_gen.next_float*5).floor] += 1 } |
100_000.times{ tally[(random_gen.next_float*5).floor] += 1 } |
||
puts tally.sort.map{|ar| ar.join(": ") }</ |
puts tally.sort.map{|ar| ar.join(": ") }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,073: | Line 1,439: | ||
4: 20007 |
4: 20007 |
||
</pre> |
</pre> |
||
=={{header|Rust}}== |
|||
{{trans|C++}} |
|||
<syntaxhighlight lang="Rust"> |
|||
struct XorShiftStar { |
|||
magic: u64, |
|||
state: u64, |
|||
} |
|||
impl XorShiftStar { |
|||
fn new() -> Self { |
|||
Self { |
|||
magic: 0x2545_F491_4F6C_DD1D, |
|||
state: 0, |
|||
} |
|||
} |
|||
fn seed(&mut self, num: u64) { |
|||
self.state = num; |
|||
} |
|||
fn next_int(&mut self) -> u32 { |
|||
let mut x = self.state; |
|||
x ^= x >> 12; |
|||
x ^= x << 25; |
|||
x ^= x >> 27; |
|||
self.state = x; |
|||
((x.wrapping_mul(self.magic)) >> 32) as u32 |
|||
} |
|||
fn next_float(&mut self) -> f32 { |
|||
self.next_int() as f32 / (1u64 << 32) as f32 |
|||
} |
|||
} |
|||
fn main() { |
|||
let mut rng = XorShiftStar::new(); |
|||
rng.seed(1234567); |
|||
println!("{}", rng.next_int()); |
|||
println!("{}", rng.next_int()); |
|||
println!("{}", rng.next_int()); |
|||
println!("{}", rng.next_int()); |
|||
println!("{}", rng.next_int()); |
|||
println!(); |
|||
let mut counts = [0; 5]; |
|||
rng.seed(987654321); |
|||
for _ in 0..100000 { |
|||
let j = (rng.next_float() * 5.0).floor() as usize; |
|||
counts[j] += 1; |
|||
} |
|||
for (i, count) in counts.iter().enumerate() { |
|||
println!("{}: {}", i, count); |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
3540625527 |
|||
2750739987 |
|||
4037983143 |
|||
1993361440 |
|||
3809424708 |
|||
0: 20103 |
|||
1: 19922 |
|||
2: 19937 |
|||
3: 20031 |
|||
4: 20007 |
|||
</pre> |
|||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Perl}} |
{{trans|Perl}} |
||
< |
<syntaxhighlight lang="ruby">class Xorshift_star(state) { |
||
define ( |
define ( |
||
Line 1,102: | Line 1,539: | ||
var rng = Xorshift_star(987654321) |
var rng = Xorshift_star(987654321) |
||
var histogram = Bag(1e5.of { floor(5*rng.next_float) }...) |
var histogram = Bag(1e5.of { floor(5*rng.next_float) }...) |
||
histogram.pairs.sort.each { .join(": ").say }</ |
histogram.pairs.sort.each { .join(": ").say }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,115: | Line 1,552: | ||
4: 20007 |
4: 20007 |
||
</pre> |
</pre> |
||
=={{header|Swift}}== |
|||
<syntaxhighlight lang="swift">import Foundation |
|||
struct XorshiftStar { |
|||
private let magic: UInt64 = 0x2545F4914F6CDD1D |
|||
private var state: UInt64 |
|||
init(seed: UInt64) { |
|||
state = seed |
|||
} |
|||
mutating func nextInt() -> UInt64 { |
|||
state ^= state &>> 12 |
|||
state ^= state &<< 25 |
|||
state ^= state &>> 27 |
|||
return (state &* magic) &>> 32 |
|||
} |
|||
mutating func nextFloat() -> Float { |
|||
return Float(nextInt()) / Float(1 << 32) |
|||
} |
|||
} |
|||
extension XorshiftStar: RandomNumberGenerator, IteratorProtocol, Sequence { |
|||
mutating func next() -> UInt64 { |
|||
return nextInt() |
|||
} |
|||
mutating func next() -> UInt64? { |
|||
return nextInt() |
|||
} |
|||
} |
|||
for (i, n) in XorshiftStar(seed: 1234567).lazy.enumerated().prefix(5) { |
|||
print("\(i): \(n)") |
|||
} |
|||
var gen = XorshiftStar(seed: 987654321) |
|||
var counts = [Float: Int]() |
|||
for _ in 0..<100_000 { |
|||
counts[floorf(gen.nextFloat() * 5), default: 0] += 1 |
|||
} |
|||
print(counts)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>0: 3540625527 |
|||
1: 2750739987 |
|||
2: 4037983143 |
|||
3: 1993361440 |
|||
4: 3809424708 |
|||
[1.0: 19922, 4.0: 20007, 3.0: 20031, 2.0: 19937, 0.0: 20103]</pre> |
|||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
Line 1,120: | Line 1,614: | ||
{{libheader|Wren-big}} |
{{libheader|Wren-big}} |
||
As Wren doesn't have a 64-bit integer type, we use BigInt instead. |
As Wren doesn't have a 64-bit integer type, we use BigInt instead. |
||
< |
<syntaxhighlight lang="wren">import "./big" for BigInt |
||
var Const = BigInt.fromBaseString("2545F4914F6CDD1D", 16) |
var Const = BigInt.fromBaseString("2545F4914F6CDD1D", 16) |
||
Line 1,155: | Line 1,649: | ||
} |
} |
||
System.print("\nThe counts for 100,000 repetitions are:") |
System.print("\nThe counts for 100,000 repetitions are:") |
||
for (i in 0..4) System.print(" %(i) : %(counts[i])")</ |
for (i in 0..4) System.print(" %(i) : %(counts[i])")</syntaxhighlight> |
||
{{out}} |
{{out}} |
Latest revision as of 01:45, 29 May 2024
You are encouraged to solve this task according to the task description, using any language you may know.
- Some definitions to help in the explanation
- Floor operation
- https://en.wikipedia.org/wiki/Floor_and_ceiling_functions
- Greatest integer less than or equal to a real number.
- https://en.wikipedia.org/wiki/Floor_and_ceiling_functions
- Bitwise Logical shift operators (c-inspired)
- https://en.wikipedia.org/wiki/Bitwise_operation#Bit_shifts
- Binary bits of value shifted left or right, with zero bits shifted in where appropriate.
- Examples are shown for 8 bit binary numbers; most significant bit to the left.
- https://en.wikipedia.org/wiki/Bitwise_operation#Bit_shifts
- << Logical shift left by given number of bits.
- E.g Binary 00110101 << 2 == Binary 11010100
- << Logical shift left by given number of bits.
- >> Logical shift right by given number of bits.
- E.g Binary 00110101 >> 2 == Binary 00001101
- >> Logical shift right by given number of bits.
- ^ Bitwise exclusive-or operator
- https://en.wikipedia.org/wiki/Exclusive_or
- Bitwise comparison for if bits differ
- E.g Binary 00110101 ^ Binary 00110011 == Binary 00000110
- Xorshift_star Generator (pseudo-code)
/* Let u64 denote an unsigned 64 bit integer type. */ /* Let u32 denote an unsigned 32 bit integer type. */ class Xorshift_star u64 state /* Must be seeded to non-zero initial value */ u64 const = HEX '2545F4914F6CDD1D' method seed(u64 num): state = num end method method next_int(): u64 x = state x = x ^ (x >> 12) x = x ^ (x << 25) x = x ^ (x >> 27) state = x u32 answer = ((x * const) >> 32) return answer end method method next_float(): return float next_int() / (1 << 32) end method end class
- Xorshift use
random_gen = instance Xorshift_star random_gen.seed(1234567) print(random_gen.next_int()) /* 3540625527 */ print(random_gen.next_int()) /* 2750739987 */ print(random_gen.next_int()) /* 4037983143 */ print(random_gen.next_int()) /* 1993361440 */ print(random_gen.next_int()) /* 3809424708 */
- Task
- Generate a class/set of functions that generates pseudo-random
numbers as shown above.
- Show that the first five integers genrated with the seed 1234567
are as shown above
- Show that for an initial seed of 987654321, the counts of 100_000 repetitions of
floor(random_gen.next_float() * 5)
- Is as follows:
0: 20103, 1: 19922, 2: 19937, 3: 20031, 4: 20007
- Show your output here, on this page.
11l
T XorShiftStar
UInt64 state
F seed(seed_state)
.state = seed_state
F next_int() -> UInt32
V x = .state
x (+)= x >> 12
x (+)= x << 25
x (+)= x >> 27
.state = x
R (x * 2545'F491'4F6C'DD1D) >> 32
F next_float()
R Float(.next_int()) / 2.0^32
V random_gen = XorShiftStar()
random_gen.seed(1234567)
L 5
print(random_gen.next_int())
random_gen.seed(987654321)
V hist = Dict(0.<5, i -> (i, 0))
L 100'000
hist[Int(random_gen.next_float() * 5)]++
print(hist)
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 [0 = 20103, 1 = 19922, 2 = 19937, 3 = 20031, 4 = 20007]
Ada
Raises Unseeded_Error exception if state is not initialized before generating a pseudo-random value.
with Interfaces; use Interfaces;
with Ada.Text_IO; use Ada.Text_IO;
procedure Main is
const : constant Unsigned_64 := 16#2545_F491_4F6C_DD1D#;
state : Unsigned_64 := 0;
Unseeded_Error : exception;
procedure seed (num : Unsigned_64) is
begin
state := num;
end seed;
function Next_Int return Unsigned_32 is
x : Unsigned_64 := state;
begin
if state = 0 then
raise Unseeded_Error;
end if;
x := x xor (x / 2**12);
x := x xor (x * 2**25);
x := x xor (x / 2**27);
state := x;
return Unsigned_32 ((x * const) / 2**32);
end Next_Int;
function Next_Float return Long_Float is
begin
return Long_Float (Next_Int) / 2.0**32;
end Next_Float;
counts : array (0 .. 4) of Natural := (others => 0);
J : Natural;
begin
seed (1_234_567);
for I in 1 .. 5 loop
Put_Line (Unsigned_32'Image (Next_Int));
end loop;
seed (987_654_321);
for I in 1 .. 100_000 loop
J := Natural (Long_Float'Floor (Next_Float * 5.0));
counts (J) := counts (J) + 1;
end loop;
New_Line;
for I in counts'Range loop
Put_Line (I'Image & " :" & counts (I)'Image);
end loop;
end Main;
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 0 : 20103 1 : 19922 2 : 19937 3 : 20031 4 : 20007
ALGOL 68
Will generate a runtime error if state is not initialised before use.
BEGIN # generate some pseudo random numbers using Xorshift star #
# note that although LONG INT is 64 bits in Algol 68G, LONG BITS is longer than 64 bits #
LONG BITS state;
LONG INT const = ABS LONG 16r2545f4914f6cdd1d;
LONG INT one shl 32 = ABS ( LONG 16r1 SHL 32 );
# sets the state to the specified seed value #
PROC seed = ( LONG INT num )VOID: state := BIN num;
# XOR and assign convenience operator #
PRIO XORAB = 1;
OP XORAB = ( REF LONG BITS x, LONG BITS v )REF LONG BITS: x := ( x XOR v ) AND LONG 16rffffffffffffffff;
# gets the next pseudo random integer #
PROC next int = LONG INT:
BEGIN
LONG BITS x := state;
x XORAB ( x SHR 12 );
x XORAB ( x SHL 25 );
x XORAB ( x SHR 27 );
state := x;
SHORTEN ABS ( 16rffffffff AND BIN ( ABS x * LENG const ) SHR 32 )
END # next int # ;
# gets the next pseudo random real #
PROC next float = LONG REAL: next int / one shl 32;
BEGIN # task test cases #
seed( 1234567 );
print( ( whole( next int, 0 ), newline ) ); # 3540625527 #
print( ( whole( next int, 0 ), newline ) ); # 2750739987 #
print( ( whole( next int, 0 ), newline ) ); # 4037983143 #
print( ( whole( next int, 0 ), newline ) ); # 1993361440 #
print( ( whole( next int, 0 ), newline ) ); # 3809424708 #
# count the number of occurances of 0..4 in a sequence of pseudo random reals scaled to be in [0..5) #
seed( 987654321 );
[ 0 : 4 ]INT counts; FOR i FROM LWB counts TO UPB counts DO counts[ i ] := 0 OD;
TO 100 000 DO counts[ SHORTEN ENTIER ( next float * 5 ) ] +:= 1 OD;
FOR i FROM LWB counts TO UPB counts DO
print( ( whole( i, -2 ), ": ", whole( counts[ i ], -6 ) ) )
OD;
print( ( newline ) )
END
END
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 0: 20103 1: 19922 2: 19937 3: 20031 4: 20007
C
#include <math.h>
#include <stdint.h>
#include <stdio.h>
static uint64_t state;
static const uint64_t STATE_MAGIC = 0x2545F4914F6CDD1D;
void seed(uint64_t num) {
state = num;
}
uint32_t next_int() {
uint64_t x;
uint32_t answer;
x = state;
x = x ^ (x >> 12);
x = x ^ (x << 25);
x = x ^ (x >> 27);
state = x;
answer = ((x * STATE_MAGIC) >> 32);
return answer;
}
float next_float() {
return (float)next_int() / (1LL << 32);
}
int main() {
int counts[5] = { 0, 0, 0, 0, 0 };
int i;
seed(1234567);
printf("%u\n", next_int());
printf("%u\n", next_int());
printf("%u\n", next_int());
printf("%u\n", next_int());
printf("%u\n", next_int());
printf("\n");
seed(987654321);
for (i = 0; i < 100000; i++) {
int j = (int)floor(next_float() * 5.0);
counts[j]++;
}
for (i = 0; i < 5; i++) {
printf("%d: %d\n", i, counts[i]);
}
return 0;
}
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 0: 20103 1: 19922 2: 19937 3: 20031 4: 20007
C++
#include <array>
#include <cstdint>
#include <iostream>
class XorShiftStar {
private:
const uint64_t MAGIC = 0x2545F4914F6CDD1D;
uint64_t state;
public:
void seed(uint64_t num) {
state = num;
}
uint32_t next_int() {
uint64_t x;
uint32_t answer;
x = state;
x = x ^ (x >> 12);
x = x ^ (x << 25);
x = x ^ (x >> 27);
state = x;
answer = ((x * MAGIC) >> 32);
return answer;
}
float next_float() {
return (float)next_int() / (1LL << 32);
}
};
int main() {
auto rng = new XorShiftStar();
rng->seed(1234567);
std::cout << rng->next_int() << '\n';
std::cout << rng->next_int() << '\n';
std::cout << rng->next_int() << '\n';
std::cout << rng->next_int() << '\n';
std::cout << rng->next_int() << '\n';
std::cout << '\n';
std::array<int, 5> counts = { 0, 0, 0, 0, 0 };
rng->seed(987654321);
for (int i = 0; i < 100000; i++) {
int j = (int)floor(rng->next_float() * 5.0);
counts[j]++;
}
for (size_t i = 0; i < counts.size(); i++) {
std::cout << i << ": " << counts[i] << '\n';
}
return 0;
}
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 0: 20103 1: 19922 2: 19937 3: 20031 4: 20007
D
import std.math;
import std.stdio;
class XorShiftStar {
private immutable MAGIC = 0x2545F4914F6CDD1D;
private ulong state;
public void seed(ulong num) {
state = num;
}
public uint nextInt() {
ulong x;
uint answer;
x = state;
x = x ^ (x >> 12);
x = x ^ (x << 25);
x = x ^ (x >> 27);
state = x;
answer = ((x * MAGIC) >> 32);
return answer;
}
public float nextFloat() {
return cast(float) nextInt() / (1L << 32);
}
}
void main() {
auto rng = new XorShiftStar();
rng.seed(1234567);
writeln(rng.nextInt);
writeln(rng.nextInt);
writeln(rng.nextInt);
writeln(rng.nextInt);
writeln(rng.nextInt);
writeln;
int[5] counts;
rng.seed(987654321);
foreach (_; 0 .. 100_000) {
auto j = cast(int) floor(rng.nextFloat * 5.0);
counts[j]++;
}
foreach (i, v; counts) {
writeln(i, ": ", v);
}
}
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 0: 20103 1: 19922 2: 19937 3: 20031 4: 20007
Delphi
program Xorshift_star;
{$APPTYPE CONSOLE}
uses
System.SysUtils,
System.Math;
type
TXorshiftStar = record
private
state: uint64;
const
k = $2545F4914F6CDD1D;
public
constructor Create(aState: uint64);
procedure Seed(aState: uint64);
function NextInt: uint32;
function NextFloat: Extended;
end;
{ TXorshiftStar }
constructor TXorshiftStar.Create(aState: uint64);
begin
Seed(aState);
end;
function TXorshiftStar.NextFloat: Extended;
begin
Result := NextInt() / $100000000;
end;
function TXorshiftStar.NextInt: uint32;
var
x: UInt64;
begin
x := state;
x := x xor (x shr 12);
x := x xor (x shl 25);
x := x xor (x shr 27);
state := x;
Result := uint32((x * k) shr 32);
end;
procedure TXorshiftStar.Seed(aState: uint64);
begin
state := aState;
end;
begin
var randomGen := TXorshiftStar.Create(1234567);
for var i := 0 to 4 do
writeln(randomGen.NextInt);
var counts := [0, 0, 0, 0, 0];
randomGen.seed(987654321);
for var i := 1 to 100000 do
begin
var j := Floor(randomGen.nextFloat() * 5);
inc(counts[j]);
end;
writeln(#10'The counts for 100,000 repetitions are:');
for var i := 0 to 4 do
writeln(format(' %d : %d', [i, counts[i]]));
{$IFNDEF UNIX} Readln; {$ENDIF}
end.
F#
The Functions
// Xorshift star. Nigel Galloway: August 14th., 2020
let fN=(fun(n:uint64)->n^^^(n>>>12))>>(fun n->n^^^(n<<<25))>>(fun n->n^^^(n>>>27))
let Xstar32=Seq.unfold(fun n->let n=fN n in Some(uint32((n*0x2545F4914F6CDD1DUL)>>>32),n))
let XstarF n=Xstar32 n|>Seq.map(fun n->(float n)/4294967296.0)
The Tasks
Xstar32 1234567UL|>Seq.take 5|>Seq.iter(printfn "%d")
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708
XstarF 987654321UL|>Seq.take 100000|>Seq.countBy(fun n->int(n*5.0))|>Seq.iter(printf "%A");printfn ""
- Output:
(4, 20007)(2, 19937)(3, 20031)(0, 20103)(1, 19922)
Factor
USING: accessors kernel literals math math.statistics
prettyprint sequences ;
CONSTANT: mask64 $[ 1 64 shift 1 - ]
CONSTANT: mask32 $[ 1 32 shift 1 - ]
CONSTANT: const 0x2545F4914F6CDD1D
! Restrict seed value to positive integers.
PREDICATE: positive < integer 0 > ;
ERROR: seed-nonpositive seed ;
TUPLE: xorshift* { state positive initial: 1 } ;
: <xorshift*> ( seed -- xorshift* )
dup positive? [ seed-nonpositive ] unless
mask64 bitand xorshift* boa ;
: twiddle ( m n -- n ) dupd shift bitxor mask64 bitand ;
: next-int ( obj -- n )
dup state>> -12 twiddle 25 twiddle -27 twiddle tuck swap
state<< const * mask64 bitand -32 shift mask32 bitand ;
: next-float ( obj -- x ) next-int 1 32 shift /f ;
! ---=== Task ===---
1234567 <xorshift*> 5 [ dup next-int . ] times
987654321 >>state
100,000 [ dup next-float 5 * >integer ] replicate nip
histogram .
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 H{ { 0 20103 } { 1 19922 } { 2 19937 } { 3 20031 } { 4 20007 } }
FreeBASIC
#define floor(x) ((x*2.0-0.5) Shr 1)
Const As Ulongint mask64 = &HFFFFFFFFFFFFFFFF
Const As Ulongint mask32 = &HFFFFFFFF
Const As Ulongint cte = &H2545F4914F6CDD1D
Dim Shared As Ulongint state
Sub seed(num As Ulongint)
state = num And mask64
End Sub
Function next_int() As Ulongint
Dim As Ulongint x = state
x = (x Xor (x Shr 12)) And mask64
x = (x Xor (x Shl 25)) And mask64
x = (x Xor (x Shr 27)) And mask64
state = x
Dim As Ulongint answer = (((x * cte) And mask64) Shr 32) And mask32
Return answer
End Function
Function next_float() As Double
Return next_int() / (2 ^ 32)
End Function
Dim As Integer i, hist(4)
seed(1234567)
For i = 1 To 5
Print next_int()
Next i
Print !"\nThe counts for 100,000 repetitions are:"
seed(987654321)
For i = 1 To 100000
hist(floor(next_float() * 5)) += 1
Next i
For i = 0 To 4
Print Using "hist(#) = #####"; i; hist(i)
Next i
Sleep
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 The counts for 100,000 repetitions are: hist(0) = 20103 hist(1) = 19922 hist(2) = 19937 hist(3) = 20031 hist(4) = 20007
Go
package main
import (
"fmt"
"math"
)
const CONST = 0x2545F4914F6CDD1D
type XorshiftStar struct{ state uint64 }
func XorshiftStarNew(state uint64) *XorshiftStar { return &XorshiftStar{state} }
func (xor *XorshiftStar) seed(state uint64) { xor.state = state }
func (xor *XorshiftStar) nextInt() uint32 {
x := xor.state
x = x ^ (x >> 12)
x = x ^ (x << 25)
x = x ^ (x >> 27)
xor.state = x
return uint32((x * CONST) >> 32)
}
func (xor *XorshiftStar) nextFloat() float64 {
return float64(xor.nextInt()) / (1 << 32)
}
func main() {
randomGen := XorshiftStarNew(1234567)
for i := 0; i < 5; i++ {
fmt.Println(randomGen.nextInt())
}
var counts [5]int
randomGen.seed(987654321)
for i := 0; i < 1e5; i++ {
j := int(math.Floor(randomGen.nextFloat() * 5))
counts[j]++
}
fmt.Println("\nThe counts for 100,000 repetitions are:")
for i := 0; i < 5; i++ {
fmt.Printf(" %d : %d\n", i, counts[i])
}
}
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 The counts for 100,000 repetitions are: 0 : 20103 1 : 19922 2 : 19937 3 : 20031 4 : 20007
Haskell
Implement given algorithm as an instance of RandomGen
class.
import Data.Bits
import Data.Word
import System.Random
import Data.List
newtype XorShift = XorShift Word64
instance RandomGen XorShift where
next (XorShift state) = (out newState, XorShift newState)
where
newState = (\z -> z `xor` (z `shiftR` 27)) .
(\z -> z `xor` (z `shiftL` 25)) .
(\z -> z `xor` (z `shiftR` 12)) $ state
out x = fromIntegral $ (x * 0x2545f4914f6cdd1d) `shiftR` 32
split _ = error "XorShift is not splittable"
randoms' :: RandomGen g => g -> [Int]
randoms' = unfoldr (pure . next)
toFloat n = fromIntegral n / (2^32 - 1)
Direct usage of generator:
*Main> mapM_ print $ take 5 $ randoms' (XorShift 1234567) 3540625527 2750739987 4037983143 1993361440 3809424708 *Main> let hist = map length . group . sort *Main> hist . take 100000 $ (floor . (*5) . toFloat) <$> (randoms' (XorShift 987654321)) [20103,19922,19937,20031,20007]
Using Random
class gives different results due to internal shuffling:
*Main> mapM_ print $ take 5 $ randoms (XorShift 1234567) 2750739987 1993361440 1794978290 626183142 2911384526 *Main> let hist = map length . group . sort *Main> hist . take 100000 $ (floor . (*5)) <$> (randoms (XorShift 987654321) :: [Float]) [20263,19783,19949,19957,20048]
Java
public class XorShiftStar {
private static final long MAGIC = Long.parseUnsignedLong("2545F4914F6CDD1D", 16);
private long state;
public void seed(long num) {
state = num;
}
public int nextInt() {
long x;
int answer;
x = state;
x = x ^ (x >>> 12);
x = x ^ (x << 25);
x = x ^ (x >>> 27);
state = x;
answer = (int) ((x * MAGIC) >> 32);
return answer;
}
public float nextFloat() {
return (float) Integer.toUnsignedLong(nextInt()) / (1L << 32);
}
public static void main(String[] args) {
var rng = new XorShiftStar();
rng.seed(1234567);
System.out.println(Integer.toUnsignedString(rng.nextInt()));
System.out.println(Integer.toUnsignedString(rng.nextInt()));
System.out.println(Integer.toUnsignedString(rng.nextInt()));
System.out.println(Integer.toUnsignedString(rng.nextInt()));
System.out.println(Integer.toUnsignedString(rng.nextInt()));
System.out.println();
int[] counts = {0, 0, 0, 0, 0};
rng.seed(987654321);
for (int i = 0; i < 100_000; i++) {
int j = (int) Math.floor(rng.nextFloat() * 5.0);
counts[j]++;
}
for (int i = 0; i < counts.length; i++) {
System.out.printf("%d: %d\n", i, counts[i]);
}
}
}
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 0: 20103 1: 19922 2: 19937 3: 20031 4: 20007
jq
Adapted from Wren
Works with gojq, the Go implementation of jq
The following program uses the "bitwise" module.
include "bitwise" {search: "."}; # see above
def Const: 2685821657736338717; # i.e. 0x2545F4914F6CDD1D
def Mask64: 18446744073709551615; # i.e. (1 | leftshift(64)) - 1
def Mask32: 4294967295; # i.e. (1 | leftshift(32)) - 1
# Emit a suitable {state} object
def seed($num):
{state: bitwise_and($num; Mask64)};
# Input: {state}
# Output: {state, nextInt}
def nextInt:
.state |= bitwise_and(bitwise_xor(.; rightshift(12)); Mask64)
| .state |= bitwise_and(bitwise_xor(.; leftshift( 25)); Mask64)
| .state |= bitwise_and(bitwise_xor(.; rightshift(27)); Mask64)
| .nextInt = bitwise_and( bitwise_and(.state * Const; Mask64) | rightshift(32); Mask32) ;
# Input: {state}
# Output: {state, nextInt, nextFloat}
def nextFloat:
nextInt
| .nextFloat = (.nextInt / (pow(2;32)));
def task1:
foreach range(0; 5) as $i (seed(1234567);
nextInt;
.nextInt);
def task2($max):
reduce range(0; $max) as $i (seed(987654321);
nextFloat
| ((.nextFloat * 5)|floor) as $n
| .counts[$n] += 1)
| "\nThe counts for \($max) repetitions are:",
(range(0; 5) as $i | "\($i) : \(.counts[$i])") ;
task1, "", task2(100000)
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 The counts for 100000 repetitions are: 0 : 20103 1 : 19922 2 : 19937 3 : 20031 4 : 20007
Julia
const mask32 = (0x1 << 32) - 1
const CONST = 0x2545F4914F6CDD1D
mutable struct XorShiftStar
state::UInt64
end
XorShiftStar(_seed=0x0) = XorShiftStar(UInt(_seed))
seed(x::XorShiftStar, num) = begin x.state = UInt64(num) end
"""return random int between 0 and 2**32"""
function next_int(x::XorShiftStar)
x.state = x.state ⊻ (x.state >> 12)
x.state = x.state ⊻ (x.state << 25)
x.state = x.state ⊻ (x.state >> 27)
return ((x.state * CONST) >> 32) & mask32
end
"""return random float between 0 and 1"""
next_float(x::XorShiftStar) = next_int(x) / (1 << 32)
function testXorShiftStar()
random_gen = XorShiftStar()
seed(random_gen, 1234567)
for i in 1:5
println(next_int(random_gen))
end
seed(random_gen, 987654321)
hist = fill(0, 5)
for _ in 1:100_000
hist[Int(floor(next_float(random_gen) * 5)) + 1] += 1
end
foreach(n -> print(n - 1, ": ", hist[n], " "), 1:5)
end
testXorShiftStar()
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 0: 20103 1: 19922 2: 19937 3: 20031 4: 20007
Kotlin
import kotlin.math.floor
class XorShiftStar {
private var state = 0L
fun seed(num: Long) {
state = num
}
fun nextInt(): Int {
var x = state
x = x xor (x ushr 12)
x = x xor (x shl 25)
x = x xor (x ushr 27)
state = x
return (x * MAGIC shr 32).toInt()
}
fun nextFloat(): Float {
return nextInt().toUInt().toFloat() / (1L shl 32)
}
companion object {
private const val MAGIC = 0x2545F4914F6CDD1D
}
}
fun main() {
val rng = XorShiftStar()
rng.seed(1234567)
println(rng.nextInt().toUInt())
println(rng.nextInt().toUInt())
println(rng.nextInt().toUInt())
println(rng.nextInt().toUInt())
println(rng.nextInt().toUInt())
println()
rng.seed(987654321)
val counts = arrayOf(0, 0, 0, 0, 0)
for (i in 1..100000) {
val j = floor(rng.nextFloat() * 5.0).toInt()
counts[j]++
}
for (iv in counts.withIndex()) {
println("${iv.index}: ${iv.value}")
}
}
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 0: 20103 1: 19922 2: 19937 3: 20031 4: 20007
Lua
function create()
local g = {
magic = 0x2545F4914F6CDD1D,
state = 0,
seed = function(self, num)
self.state = num
end,
next_int = function(self)
local x = self.state
x = x ~ (x >> 12)
x = x ~ (x << 25)
x = x ~ (x >> 27)
self.state = x
local answer = (x * self.magic) >> 32
return answer
end,
next_float = function(self)
return self:next_int() / (1 << 32)
end
}
return g
end
local g = create()
g:seed(1234567)
print(g:next_int())
print(g:next_int())
print(g:next_int())
print(g:next_int())
print(g:next_int())
print()
local counts = {[0]=0, [1]=0, [2]=0, [3]=0, [4]=0}
g:seed(987654321)
for i=1,100000 do
local j = math.floor(g:next_float() * 5.0)
counts[j] = counts[j] + 1
end
for i,v in pairs(counts) do
print(i..': '..v)
end
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 0: 20103 1: 19922 2: 19937 3: 20031 4: 20007
Nim
import algorithm, sequtils, strutils, tables
const C = 0x2545F4914F6CDD1Du64
type XorShift = object
state: uint64
func seed(gen: var XorShift; num: uint64) =
gen.state = num
func nextInt(gen: var XorShift): uint32 =
var x = gen.state
x = x xor x shr 12
x = x xor x shl 25
x = x xor x shr 27
gen.state = x
result = uint32((x * C) shr 32)
func nextFloat(gen: var XorShift): float =
gen.nextInt().float / float(0xFFFFFFFFu32)
when isMainModule:
var gen: XorShift
gen.seed(1234567)
for _ in 1..5:
echo gen.nextInt()
echo ""
gen.seed(987654321)
var counts: CountTable[int]
for _ in 1..100_000:
counts.inc int(gen.nextFloat() * 5)
echo sorted(toSeq(counts.pairs)).mapIt($it[0] & ": " & $it[1]).join(", ")
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 0: 20103, 1: 19922, 2: 19937, 3: 20031, 4: 20007
Perl
use strict;
use warnings;
no warnings 'portable';
use feature 'say';
use Math::AnyNum qw(:overload);
package Xorshift_star {
sub new {
my ($class, %opt) = @_;
bless {state => $opt{seed}}, $class;
}
sub next_int {
my ($self) = @_;
my $state = $self->{state};
$state ^= $state >> 12;
$state ^= $state << 25 & (2**64 - 1);
$state ^= $state >> 27;
$self->{state} = $state;
($state * 0x2545F4914F6CDD1D) >> 32 & (2**32 - 1);
}
sub next_float {
my ($self) = @_;
$self->next_int / 2**32;
}
}
say 'Seed: 1234567, first 5 values:';
my $rng = Xorshift_star->new(seed => 1234567);
say $rng->next_int for 1 .. 5;
my %h;
say "\nSeed: 987654321, values histogram:";
$rng = Xorshift_star->new(seed => 987654321);
$h{int 5 * $rng->next_float}++ for 1 .. 100_000;
say "$_ $h{$_}" for sort keys %h;
- Output:
Seed: 1234567, first 5 values: 3540625527 2750739987 4037983143 1993361440 3809424708 Seed: 987654321, values histogram: 0 20103 1 19922 2 19937 3 20031 4 20007
Phix
As per Pseudo-random_numbers/PCG32#Phix, resorting to mpfr/gmp
with javascript_semantics include mpfr.e mpz cmult = mpz_init("0x2545F4914F6CDD1D"), state = mpz_init(), b64 = mpz_init("0x10000000000000000"), -- (truncate to 64 bits) b32 = mpz_init("0x100000000"), -- (truncate to 32 bits) tmp = mpz_init(), x = mpz_init() procedure seed(integer num) mpz_set_si(state,num) end procedure function next_int() mpz_set(x,state) -- x := state mpz_tdiv_q_2exp(tmp, x, 12) -- tmp := trunc(x/2^12) mpz_xor(x, x, tmp) -- x := xor_bits(x,tmp) mpz_mul_2exp(tmp, x, 25) -- tmp := x * 2^25. mpz_xor(x, x, tmp) -- x := xor_bits(x,tmp) mpz_fdiv_r(x, x, b64) -- x := remainder(x,b64) mpz_tdiv_q_2exp(tmp, x, 27) -- tmp := trunc(x/2^27) mpz_xor(x, x, tmp) -- x := xor_bits(x,tmp) mpz_fdiv_r(state, x, b64) -- state := remainder(x,b64) mpz_mul(x,x,cmult) -- x *= cmult mpz_tdiv_q_2exp(x, x, 32) -- x := trunc(x/2^32) mpz_fdiv_r(x, x, b32) -- x := remainder(x,b32) return mpz_get_atom(x) end function function next_float() return next_int() / #100000000 end function seed(1234567) for i=1 to 5 do printf(1,"%d\n",next_int()) end for seed(987654321) sequence r = repeat(0,5) for i=1 to 100000 do integer idx = floor(next_float()*5)+1 r[idx] += 1 end for ?r
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 {20103,19922,19937,20031,20007}
Python
mask64 = (1 << 64) - 1
mask32 = (1 << 32) - 1
const = 0x2545F4914F6CDD1D
class Xorshift_star():
def __init__(self, seed=0):
self.state = seed & mask64
def seed(self, num):
self.state = num & mask64
def next_int(self):
"return random int between 0 and 2**32"
x = self.state
x = (x ^ (x >> 12)) & mask64
x = (x ^ (x << 25)) & mask64
x = (x ^ (x >> 27)) & mask64
self.state = x
answer = (((x * const) & mask64) >> 32) & mask32
return answer
def next_float(self):
"return random float between 0 and 1"
return self.next_int() / (1 << 32)
if __name__ == '__main__':
random_gen = Xorshift_star()
random_gen.seed(1234567)
for i in range(5):
print(random_gen.next_int())
random_gen.seed(987654321)
hist = {i:0 for i in range(5)}
for i in range(100_000):
hist[int(random_gen.next_float() *5)] += 1
print(hist)
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 {0: 20103, 1: 19922, 2: 19937, 3: 20031, 4: 20007}
Raku
Raku does not have unsigned Integers at this time (Integers are arbitrary sized) so use explicit bit masks during bitwise operations. All constants are encapsulated inside the class.
class Xorshift-star {
has $!state;
submethod BUILD ( Int :$seed where * > 0 = 1 ) { $!state = $seed }
method next-int {
$!state +^= $!state +> 12;
$!state +^= $!state +< 25 +& (2⁶⁴ - 1);
$!state +^= $!state +> 27;
($!state * 0x2545F4914F6CDD1D) +> 32 +& (2³² - 1)
}
method next-rat { self.next-int / 2³² }
}
# Test next-int
say 'Seed: 1234567; first five Int values';
my $rng = Xorshift-star.new( :seed(1234567) );
.say for $rng.next-int xx 5;
# Test next-rat (since these are rational numbers by default)
say "\nSeed: 987654321; first 1e5 Rat values histogram";
$rng = Xorshift-star.new( :seed(987654321) );
say ( ($rng.next-rat * 5).floor xx 100_000 ).Bag;
# Test with default seed
say "\nSeed: default; first five Int values";
$rng = Xorshift-star.new;
.say for $rng.next-int xx 5;
- Output:
Seed: 1234567; first five Int values 3540625527 2750739987 4037983143 1993361440 3809424708 Seed: 987654321; first 1e5 Rat values histogram Bag(0(20103), 1(19922), 2(19937), 3(20031), 4(20007)) Seed: default; first five Int values 1206177355 2882512552 3117485455 1303648416 241277360
REXX
/*REXX program generates pseudo─random numbers using the XOR─shift─star method. */
numeric digits 200 /*ensure enough decimal digs for mult. */
parse arg n reps pick seed1 seed2 . /*obtain optional arguments from the CL*/
if n=='' | n=="," then n= 5 /*Not specified? Then use the default.*/
if reps=='' | reps=="," then reps= 100000 /* " " " " " " */
if pick=='' | pick=="," then pick= 5 /* " " " " " " */
if seed1=='' | seed1=="," then seed1= 1234567 /* " " " " " " */
if seed2=='' | seed2=="," then seed2= 987654321 /* " " " " " " */
const= x2d(2545f4914f6cdd1d) /*initialize the constant to be used. */
o.12= copies(0, 12) /*construct 12 bits of zeros. */
o.25= copies(0, 25) /* " 25 " " " */
o.27= copies(0, 27) /* " 27 " " " */
w= max(3, length(n) ) /*for aligning the left side of output.*/
state= seed1 /* " the state to seed #1. */
do j=1 for n
if j==1 then do; say center('n', w) " pseudo─random number"
say copies('═', w) " ══════════════════════════"
end
say right(j':', w)" " right(commas(next()), 18) /*display a random number*/
end /*j*/
say
if reps==0 then exit 0 /*stick a fork in it, we're all done. */
say center('#', w) " count of pseudo─random #"
say copies('═', w) " ══════════════════════════"
state= seed2 /* " the state to seed #2. */
@.= 0; div= pick / 2**32 /*convert division to inverse multiply.*/
do k=1 for reps
parse value next()*div with _ '.' /*get random #, floor of a "division". */
@._= @._ + 1 /*bump the counter for this random num.*/
end /*k*/
do #=0 for pick
say right(#':', w)" " right(commas(@.#), 14) /*show count of a random num.*/
end /*#*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
b2d: parse arg ?; return x2d( b2x(?) ) /*convert bin ──► decimal. */
d2b: parse arg ?; return right( x2b( d2x(?) ), 64, 0) /*convert dec ──► 64 bit bin.*/
commas: parse arg _; do ?=length(_)-3 to 1 by -3; _= insert(',', _, ?); end; return _
/*──────────────────────────────────────────────────────────────────────────────────────*/
next: procedure expose state const o.; x= d2b(state) /*convert STATE to binary. */
x = xor(x, left( o.12 || x, 64) ) /*shift right 12 bits and XOR*/
x = xor(x, right( x || o.25, 64) ) /* " left 25 " " " */
x = xor(x, left( o.27 || x, 64) ) /* " right 27 " " " */
state= b2d(x) /*set STATE to the latest X.*/
return b2d( left( d2b(state * const), 32) ) /*return a pseudo─random num.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
xor: parse arg a, b; $= /*perform a bit─wise XOR. */
do !=1 for length(a); $= $ || (substr(a,!,1) && substr(b,!,1) )
end /*!*/; return $
- output when using the default inputs:
n pseudo─random number ═══ ══════════════════════════ 1: 3,540,625,527 2: 2,750,739,987 3: 4,037,983,143 4: 1,993,361,440 5: 3,809,424,708 # count of pseudo─random # ═══ ══════════════════════════ 0: 20,103 1: 19,922 2: 19,937 3: 20,031 4: 20,007
Ruby
Using Ruby 3.0 end-les method def:
class Xorshift_star
MASK64 = (1 << 64) - 1
MASK32 = (1 << 32) - 1
def initialize(seed = 0) = @state = seed & MASK64
def next_int
x = @state
x = x ^ (x >> 12)
x = (x ^ (x << 25)) & MASK64
x = x ^ (x >> 27)
@state = x
(((x * 0x2545F4914F6CDD1D) & MASK64) >> 32) & MASK32
end
def next_float = next_int.fdiv((1 << 32))
end
random_gen = Xorshift_star.new(1234567)
5.times{ puts random_gen.next_int}
random_gen = Xorshift_star.new(987654321)
tally = Hash.new(0)
100_000.times{ tally[(random_gen.next_float*5).floor] += 1 }
puts tally.sort.map{|ar| ar.join(": ") }
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 0: 20103 1: 19922 2: 19937 3: 20031 4: 20007
Rust
struct XorShiftStar {
magic: u64,
state: u64,
}
impl XorShiftStar {
fn new() -> Self {
Self {
magic: 0x2545_F491_4F6C_DD1D,
state: 0,
}
}
fn seed(&mut self, num: u64) {
self.state = num;
}
fn next_int(&mut self) -> u32 {
let mut x = self.state;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
self.state = x;
((x.wrapping_mul(self.magic)) >> 32) as u32
}
fn next_float(&mut self) -> f32 {
self.next_int() as f32 / (1u64 << 32) as f32
}
}
fn main() {
let mut rng = XorShiftStar::new();
rng.seed(1234567);
println!("{}", rng.next_int());
println!("{}", rng.next_int());
println!("{}", rng.next_int());
println!("{}", rng.next_int());
println!("{}", rng.next_int());
println!();
let mut counts = [0; 5];
rng.seed(987654321);
for _ in 0..100000 {
let j = (rng.next_float() * 5.0).floor() as usize;
counts[j] += 1;
}
for (i, count) in counts.iter().enumerate() {
println!("{}: {}", i, count);
}
}
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 0: 20103 1: 19922 2: 19937 3: 20031 4: 20007
Sidef
class Xorshift_star(state) {
define (
mask32 = (2**32 - 1),
mask64 = (2**64 - 1),
)
method next_int {
state ^= (state >> 12)
state ^= (state << 25 & mask64)
state ^= (state >> 27)
(state * 0x2545F4914F6CDD1D) >> 32 & mask32
}
method next_float {
self.next_int / (mask32+1)
}
}
say 'Seed: 1234567, first 5 values:';
var rng = Xorshift_star(1234567)
say 5.of { rng.next_int }
say "\nSeed: 987654321, values histogram:";
var rng = Xorshift_star(987654321)
var histogram = Bag(1e5.of { floor(5*rng.next_float) }...)
histogram.pairs.sort.each { .join(": ").say }
- Output:
Seed: 1234567, first 5 values: [3540625527, 2750739987, 4037983143, 1993361440, 3809424708] Seed: 987654321, values histogram: 0: 20103 1: 19922 2: 19937 3: 20031 4: 20007
Swift
import Foundation
struct XorshiftStar {
private let magic: UInt64 = 0x2545F4914F6CDD1D
private var state: UInt64
init(seed: UInt64) {
state = seed
}
mutating func nextInt() -> UInt64 {
state ^= state &>> 12
state ^= state &<< 25
state ^= state &>> 27
return (state &* magic) &>> 32
}
mutating func nextFloat() -> Float {
return Float(nextInt()) / Float(1 << 32)
}
}
extension XorshiftStar: RandomNumberGenerator, IteratorProtocol, Sequence {
mutating func next() -> UInt64 {
return nextInt()
}
mutating func next() -> UInt64? {
return nextInt()
}
}
for (i, n) in XorshiftStar(seed: 1234567).lazy.enumerated().prefix(5) {
print("\(i): \(n)")
}
var gen = XorshiftStar(seed: 987654321)
var counts = [Float: Int]()
for _ in 0..<100_000 {
counts[floorf(gen.nextFloat() * 5), default: 0] += 1
}
print(counts)
- Output:
0: 3540625527 1: 2750739987 2: 4037983143 3: 1993361440 4: 3809424708 [1.0: 19922, 4.0: 20007, 3.0: 20031, 2.0: 19937, 0.0: 20103]
Wren
As Wren doesn't have a 64-bit integer type, we use BigInt instead.
import "./big" for BigInt
var Const = BigInt.fromBaseString("2545F4914F6CDD1D", 16)
var Mask64 = (BigInt.one << 64) - BigInt.one
var Mask32 = (BigInt.one << 32) - BigInt.one
class XorshiftStar {
construct new(state) {
_state = state & Mask64
}
seed(num) { _state = num & Mask64}
nextInt {
var x = _state
x = (x ^ (x >> 12)) & Mask64
x = (x ^ (x << 25)) & Mask64
x = (x ^ (x >> 27)) & Mask64
_state = x
return (((x * Const) & Mask64) >> 32) & Mask32
}
nextFloat { nextInt.toNum / 2.pow(32) }
}
var randomGen = XorshiftStar.new(BigInt.new(1234567))
for (i in 0..4) System.print(randomGen.nextInt)
var counts = List.filled(5, 0)
randomGen.seed(BigInt.new(987654321))
for (i in 1..1e5) {
var i = (randomGen.nextFloat * 5).floor
counts[i] = counts[i] + 1
}
System.print("\nThe counts for 100,000 repetitions are:")
for (i in 0..4) System.print(" %(i) : %(counts[i])")
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 The counts for 100,000 repetitions are: 0 : 20103 1 : 19922 2 : 19937 3 : 20031 4 : 20007