Oct 27 - new RNG
Code: Select all
/'
Low-Granularity Complex Sequence Generator dev framework - 2018 Oct 27 - by dafhi
- primarily
lets you "zoom out" of basic 'Random Number Generators' like LCG.
- how
Built on top of my n-bit integer class MiniBits, the 'csg framework'
relies on the shift amount and its relationship to state size.
Five models are provided - LCG, PCG, csg_ii, dodicat_4 and xorShift128p
- updates
re-introduced source information
License: Use and abuse
'/
type seq_state as ulongint
type seq_return as ulong
type MiniBits
/' n-bit integer class - 2018 Sep 15 - by dafhi
- code sample
dim as MiniBits a = type(1,8)
a.rotate -4
print a.hi ': 2
a.cbits = 16
a = -1
print a ': 65535
- useful bits
u = full bit mask (2^cBits - 1)
mask_lo = bit mask of "low word"
mask_hi = bit mask ..
lo_shift = cBits / 2
'/
declare constructor( as seq_state = 0, as ubyte = 0)
declare constructor( as MiniBits)
declare operator let( as seq_state)
declare operator let( as MiniBits)
declare operator cast as seq_state
declare operator cast as string
declare property cBits as ubyte
declare property cBits( as ubyte)
declare property lo as seq_return ' 2018 Sep 11
declare property hi as seq_return
declare property lo( as seq_return) ' 2018 Sep 14 (untested)
declare property hi( as seq_return)
declare function ror(as byte) as seq_state
declare sub rotate(as byte) '2018 Sep 14 - renamed from ror
'' meh. read-only
as seq_state u
as seq_state mask_lo, mask_hi '2018 Sep 14
as integer lo_shift '2018 Sep 14
private:
as seq_state b, _cbits, temp
as integer hi_shift
End Type
constructor MiniBits(i as seq_state, b as ubyte)
cBits = b: this = i
End Constructor
constructor MiniBits(i as MiniBits)
constructor i.b
End Constructor
operator MiniBits.let(i as MiniBits)
if _cBits = 0 then cBits = i.cBits '' 2018 Sep 13
this = i.b
End Operator
operator MiniBits.let(i as seq_state)
b = i and u
End Operator
operator MiniBits.cast as seq_state
return b
End Operator
operator MiniBits.cast as string
return str(type<seq_state>(this))
End Operator
property MiniBits.lo as seq_return
return b and mask_lo '2018 Sep 14
End Property
property MiniBits.hi as seq_return
return b shr hi_shift '2018 Sep 14
End Property
property MiniBits.lo(i as seq_return) '2018 Sep 14
b = b and mask_hi or i and mask_lo
End Property
property MiniBits.hi(i as seq_return) '2018 Sep 14
b = ( (i shl lo_shift) and mask_hi or (b and mask_lo) )and u
End Property
property MiniBits.cBits(i as ubyte) '2018 Sep 14 - update 2
_cbits = i: u = ( culngint(1)shl (_cbits-1) ) * 2 - 1
lo_shift = _cbits \ 2
hi_shift = _cbits - lo_shift
mask_lo = 2 ^ lo_shift - 1
mask_hi = u xor mask_lo
End Property
property MiniBits.cBits as ubyte
return _cbits
End Property
function MiniBits.ror(i as byte) as seq_state
i -= _cbits * int(i / _cbits)
return (b shl(_cbits-i)or b shr i)and u
End Function
sub MiniBits.rotate(i as byte)
i -= _cbits * int(i / _cbits) '2018 Sep 15
b = (b shl(_cbits-i)or b shr i)and u
End Sub
/' -------------------------------------------
Complex Sequence Generator - 2018 Sep 16
'/
type csg_vars extends object
/'
useful bits
seed = .u * rnd
'/
declare operator cast as seq_return
declare operator cast as minibits
declare operator cast as string
declare property name( as string)
declare property name as string
as double scale ' 2018 Sep 15
as seq_state u ' 2018 Sep 15
as MiniBits m_return, state '' likely to be used in most algorithms
'' if 2nd parameter unused, assume seed as first parameter
declare sub if_seed_request(as ubyte = 32, as ubyte = 0)
private:
as string _name
declare abstract sub iterate
End Type
operator csg_vars.cast as seq_return
iterate: return m_return
End Operator
operator csg_vars.cast as minibits
iterate: return m_return
End Operator
operator csg_vars.cast as string
iterate: return str(m_return)
End Operator
property csg_vars.name as string
return _name
End Property
property csg_vars.name(i as string)
_name = i
End Property
sub csg_vars.if_seed_request(seed_or_cbits_of_return as ubyte, state_cbits as ubyte)
' Determine whether first parm is a seed, and poke accordingly
' - 2018 Sep 14 -
if state.cbits = 0 then
if state_cbits = 0 then
state.cBits = 64: m_return.cBits = 32
state = seed_or_cbits_of_return
else
state.cBits = state_cbits: m_return.cBits = seed_or_cbits_of_return
endif
elseif state_cbits = 0 then
state = seed_or_cbits_of_return
EndIf
'' 2018 Sep 15
u = state.u: scale = state.cBits / 64
End Sub
namespace CSG_Collection
type LCG extends csg_vars
declare constructor ( as seq_state = 32, as ubyte )
as longint mul '' unsigned messes up custom while
as longint add
private:
declare sub iterate
End Type
constructor LCG(seed_or_retval_cbits as seq_state, state_cbits as ubyte)
if_seed_request seed_or_retval_cbits, state_cbits
if mul = 0 then mul = 6364136223846793005ull '' https://en.wikipedia.org/wiki/Permuted_congruential_generator
if add = 0 then add = 1442695040888963407ull
base.name = "LCG"
End Constructor
sub LCG.iterate
state = mul * state + add
m_return = state
End Sub
type PCG extends csg_vars '' pcg-random.org
declare constructor( as seq_state = 32, as ubyte = 0)
as longint mul '' 2018 Sep 12 .. unsigned messes up custom while
as longint add
private:
declare sub iterate
as minibits x
as ubyte count
' precalcs
as ubyte hi_shr, lo_shr, xor_shr
end type
constructor PCG(seed_or_cbits_of_return as seq_state, state_cbits as ubyte)
if_seed_request seed_or_cbits_of_return, state_cbits
x = state
if state = 0 then state = &h4d595df4d0f33173
if mul = 0 then mul = 6364136223846793005ull
if add = 0 then add = 1442695040888963407ull
count = sqr(m_return.cbits) - .5 ' '59' from c source
hi_shr = state.cbits - count
lo_shr = m_return.cbits - count
xor_shr = (state.cbits - lo_shr) \ 2
base.name = "PCG"
End Constructor
sub PCG.iterate
x = state
count = x shr hi_shr
state = mul * x + add
x xor= x shr xor_shr
x shr= lo_shr
m_return = x
m_return.rotate count
End Sub
' 2018 Oct 20 - Complex Sequenge Generator II - by dafhi
type CSG_ii extends csg_vars
declare constructor ( as seq_state, as ubyte)
as longint mul
as longint add
as byte ror
private:
declare sub iterate
as minibits a
as minibits b
End Type
constructor CSG_ii(seed_or_cbits_of_return as seq_state, state_cbits as ubyte)
if_seed_request seed_or_cbits_of_return, state_cbits
a = state
b = a
if mul = 0 then mul = 6364136223846793005ull
if add = 0 then add = 1442695040888963407ull
if ror = 0 then ror = 1
base.name = "CSG ii"
End Constructor
sub CSG_ii.iterate
a += 1 - (state = 0) ''2018 Sep 13 - (state = 0)
' state.rotate ror ''2018 Oct 20
state = mul * state + add
state xor= a
m_return = state
/'
CSG ver 1:
state = mul * ( state.ror( n ) + add )
'/
End Sub
/' csg 3 - by dafhi
pro: avg period ~2^68
con: multiplier search given seed mechanics
'/
type CSG_3 extends csg_vars ' 2018 Oct 27
declare constructor ( as seq_state, as ubyte)
as longint mul, seed
private:
declare sub iterate
as minibits a
End Type
constructor CSG_3(seed_or_cbits_of_return as seq_state, state_cbits as ubyte)
if_seed_request seed_or_cbits_of_return, state_cbits
a = state
if state = 0 then state = &h4d595df4d0f33173
if mul = 0 then mul = 107 '' good result across different scales
base.name = "CSG 3"
End Constructor
sub CSG_3.iterate
a += 1 - (state = seed) '' high period even without - (state = seed)
state xor= a
state *= mul
state xor= state shr 1
m_return = state
End Sub
'' https://www.freebasic.net/forum/viewtopic.php?f=3&t=26996&start=210#p252076
type dodicat_4 extends csg_vars
declare constructor (as seq_state=32, as ubyte=0)
as longint mul '' unsigned messes up custom while
as longint add
as byte b_ror
as byte c_ror
as byte d_ror
as MiniBits a,b,c,d,e
declare sub seed(i as seq_state)
private:
declare sub iterate
End Type
constructor dodicat_4(ret_bits as seq_state, state_cbits as ubyte)
if_seed_request ret_bits, state_cbits
a = state
b = a
c = a
d = a
e = a
b_ror = 25 * scale
c_ror = 53 * scale
base.name = "dodicat 4"
End Constructor
sub dodicat_4.seed(i as seq_state)
a = 40538668781 * scale
b = i
c = i
d = i
for i = 1 to 20
iterate
Next
End Sub
sub dodicat_4.iterate
e = a - b.ror( b_ror )
a = b xor c.ror( c_ror )
b = c + d
c = d + e
d = e + a
m_return = d
End Sub
'https://www.freebasic.net/forum/viewtopic.php?f=3&t=26996&start=195#p252040
'https://www.freebasic.net/forum/viewtopic.php?f=3&t=26996&start=195#p252048
'https://en.wikipedia.org/wiki/Xorshift
type xorShift128p extends csg_vars
declare constructor (as seq_state=32, as ubyte=0)
as longint mul '' unsigned messes up custom while
as longint add
as ubyte x_shl
as ubyte x_shr
as ubyte y_shr
as MiniBits m_x, m_y
as MiniBits sta(1)
private:
declare sub iterate
End Type
constructor xorShift128p(ret_bits as seq_state, state_cbits as ubyte)
if_seed_request ret_bits, state_cbits
m_x = state 'bit length
m_y = state
x_shl = 23 * scale
x_shr = 18 * scale '' 2018 Sep 16
y_shr = 5 * scale ''
for i as integer = 0 to ubound( sta )
sta(i) = state
sta(i) = rnd() * state.u
next
for i as integer = 1 to 100
iterate
next
base.name = "xorShift128p"
End Constructor
sub xorShift128p.iterate
m_x = sta( 0 )
m_y = sta( 1 )
sta( 0 ) = m_y
m_x xor= m_x shl x_shl
sta( 1 ) = m_x xor m_y xor ( m_x shr x_shr ) xor ( m_y shr y_shr )
m_return = ( sta( 1 ) + m_y )
End Sub
End Namespace
/' -----------------------------------------------------
By the way ..
I currently know of only 2 ways of obtaining output
1. cast(csg_vars, LCG)
2. use wrapper procedures like the two below
------------------------------------------------------ '/
''
sub test_print(_algo as csg_vars, c as ushort = 100)
? _algo.name
for i as long = 1 to c
? _algo; " ";
Next: ?: ?
End Sub
''
sub test_gfx(_algo as csg_vars, dummy as integer=0)
const GrayScale = 1 + 256 + 65536
dim as integer w,h
dim as single mul = 185 / _algo.m_return.u
ScreenInfo w,h', bpp,num_pages, pitch, rate, driver_name
'' 2018 Sep 15
'if _algo.m_return.cBits = _algo.state.cBits then mul *= 2
for y as integer = 0 to h-1
for x as integer = 0 to w-1
dim as ulong c = _algo * mul
pset (x,y), c * grayscale
Next
Next
locate 70, 45
? _algo.name
sleep 4000
End Sub
' --------------
using CSG_Collection
var state_bits = 6
var out_bits = state_bits / 2
? state_bits; "-bits"
?
? " CSG_Collection"
?
var print_len = 80
#if 0
#define test test_print
#else
#define test test_gfx
screenres 800,600,32
print_len = 0
#EndIf
var key = "", j=0, Nr = 3
randomize
for i as long = 1 to 20 * Nr
j = (j + 1) mod (Nr + 1)
select case j
case 1
var csg = csg_3(out_bits, state_bits)
csg.state = rnd * (csg.u+1) - .5
csg.seed = rnd * (csg.u+1) - .5
csg.mul = 1 + 2 * int(rnd * (csg.u-1))
test csg, print_len
case 2
var pcg = PCG(out_bits, state_bits)
pcg.state = rnd * pcg.u
test pcg, print_len
case 3
var d4 = dodicat_4(out_bits, state_bits)
d4.seed rnd * d4.u
test d4, print_len
end select
key = inkey
if key=chr(27) then exit for
next