Pseudo-random numbers/Xorshift star: Difference between revisions
Thundergnat (talk | contribs) m (→{{header|Raku}}: Style tweaks) |
m (→{{header|Wren}}: Minor change, output unaffected.) |
||
Line 210: | Line 210: | ||
randomGen.seed(BigInt.new(987654321)) |
randomGen.seed(BigInt.new(987654321)) |
||
for (i in 1..1e5) { |
for (i in 1..1e5) { |
||
var i = (randomGen.nextFloat * 5).floor. |
var i = (randomGen.nextFloat * 5).floor.toInt |
||
counts[i] = counts[i] + 1 |
counts[i] = counts[i] + 1 |
||
} |
} |
Revision as of 16:59, 11 August 2020
- 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.
Python
<lang 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)</lang>
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 {0: 20103, 1: 19922, 2: 19937, 3: 20031, 4: 20007}
Raku
<lang perl6>class Xorshift-star {
has $!seed = 0; has $!state; constant mask64 = 2⁶⁴ - 1; constant const = 0x2545F4914F6CDD1D;
submethod BUILD( :$seed ) { $!seed = $seed }
method TWEAK { $!state = $!seed +& mask64 }
method next-int { $!state +^= ($!state +> 12) +& mask64; $!state +^= ($!state +< 25) +& mask64; $!state +^= ($!state +> 27) +& mask64; ((($!state * const) +& mask64) +> 32) +& (2³² - 1) }
method next-rat { self.next-int / 2³² }
}
- Test next-int
my $rng = Xorshift-star.new( :seed(1234567) ); .say for $rng.next-int xx 5;
- Test next-rat (since these are rational numbers by default)
$rng = Xorshift-star.new( :seed(987654321) ); say ( ($rng.next-rat * 5).floor xx 100_000 ).Bag;</lang>
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 Bag(0(20103) 1(19922) 2(19937) 3(20031) 4(20007))
Wren
As Wren doesn't have a 64-bit integer type, we use BigInt instead with BigRat for the floating point stuff. <lang ecmascript>import "/big" for BigInt, BigRat
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 { BigRat.new(nextInt, BigInt.one << 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.toInt counts[i] = counts[i] + 1
} System.print("\nThe counts for 100,000 repetitions are:") for (i in 0..4) System.print(" %(i) : %(counts[i])")</lang>
- Output:
3540625527 2750739987 4037983143 1993361440 3809424708 The counts for 100,000 repetitions are: 0 : 20103 1 : 19922 2 : 19937 3 : 20031 4 : 20007