csg dev framework

User projects written in or related to FreeBASIC.
dafhi
Posts: 1165
Joined: Jun 04, 2005 9:51

csg dev framework

Postby dafhi » Sep 12, 2018 3:30

https://github.com/dafhi/csg-dev-framework

Sep 16 - update 2 - updated with dodicat_4

Code: Select all

/'
    Low-Granularity Complex Sequence Generator dev framework - 2018 Sep 16 - 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, m_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 m_state.cbits = 0 then
      if state_cbits = 0 then
        m_state.cBits = 64:  m_return.cBits = 32
        m_state = seed_or_cbits_of_return
      else
        m_state.cBits = state_cbits:  m_return.cBits = seed_or_cbits_of_return
      endif
    elseif state_cbits = 0 then
      m_state = seed_or_cbits_of_return
    EndIf

    '' 2018 Sep 15
    u = m_state.u:  scale = m_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
      m_state = mul * m_state + add
      m_return = m_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 = m_state
     
      if m_state = 0 then m_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 = m_state.cbits - count
      lo_shr = m_return.cbits - count
      xor_shr = (m_state.cbits - lo_shr) \ 2
     
      base.name = "PCG"
 
  End Constructor
 
  sub PCG.iterate
     
      x = m_state
      count = x shr hi_shr
      m_state = mul * x + add
      x xor= x shr xor_shr
      x shr= lo_shr
      m_return = x
      m_return.rotate count
 
  End Sub
 
 
  ' 2018 Sep 13 - '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 = m_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 - (m_state = 0) ''2018 Sep 13  - (m_state = 0)
     
      m_state.rotate ror
     
      b = mul * m_state + add
     
      m_state  = b xor a
      m_return = b
 
      /'
          CSG ver 1:
         state = mul * ( state.ror( n ) + add )
      '/

  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 = m_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                   state(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 = m_state 'bit length
      m_y = m_state
     
      x_shl = 23 * scale
      x_shr = 18 * scale '' 2018 Sep 16
      y_shr = 5 * scale ''
     
      for i as integer = 0 to ubound( state )
        state(i) = m_state
        state(i) = rnd() * m_state.u
      next
     
      for i as integer = 1 to 100
        iterate
      next
     
      base.name = "xorShift128p"
     
  End Constructor
 
  sub xorShift128p.iterate
     
      m_x = state( 0 )
      m_y = state( 1 )
     
      state( 0 ) = m_y
      m_x xor= m_x shl x_shl
      state( 1 ) = m_x xor m_y xor ( m_x shr x_shr ) xor ( m_y shr y_shr )
     
      m_return = ( state( 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.m_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

for i as long = 1 to 20 * Nr
   
    j = (j + 1) mod (Nr + 1)
   
    select case j
    case 1
      var csg2 = csg_ii(state_bits, state_bits)
      csg2.m_state = rnd * csg2.u
      csg2.add = rnd * csg2.u
      csg2.mul = 3 + 2 * int( rnd * (csg2.u+1) / 2 )
      test csg2, print_len
    case 2
      var pcg = PCG(out_bits, state_bits)
      pcg.m_state = rnd * pcg.u
      test pcg, print_len
    case 3
      var d4 = dodicat_4(state_bits, state_bits)
      d4.seed rnd * d4.u
      test d4, print_len
    end select
   
    key = inkey
    if key=chr(27) then exit for

next
Last edited by dafhi on Sep 17, 2018 4:04, edited 40 times in total.
paul doe
Posts: 701
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: csg dev framework - pre-release

Postby paul doe » Sep 12, 2018 20:54

dafhi wrote:let me know if you find hiccups!

If I can figure out the purpose of the framework, since it looks more like something deltarho[1859] would understand/enjoy =D

Your coding style however, improved drastically on this one. Nice work! BTW, I saw your post on the other thread (before you deleted it). Hang on, we'll discuss those matters (and several more) in it's own topic soon enough. I think you'll find it interesting =D
paul doe
Posts: 701
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: csg dev framework - pre-release

Postby paul doe » Sep 15, 2018 3:49

Dafhi:

As we talked, I took a look at your code. Seems like the limit is in 54 state_bits. With 53 state_bits, you start to see anomalies in the output:

Code: Select all

 53-bits

 CSG_Collection

LCG
57114959 12217650 41058585 52468148 36098547 13694470 61717085 8808104 62710999 38102042 23396321 51256028 37838331 2697
0990 15766949 16230992 16654687 49053698 61145001 60442884 51598083 12228054 35062253 39348984 5986023 352490 60792945 1
3878316 9359627 27112766 35659573 6375584 11052399 12166866 33948217 12397652 42596371 46696870 42929533 67035976 481149
35 8843706 38618369 30220668 20899867 5419790 65727685 30530288 43519359 29286818 53381321 24003492 30130467 40358262 37
674253 11456408 43411207 464522 52882833 41890508 45261611 63407326 26869333 1990976 20797839 47788146 16225113 64130804
 5877299 4549958 42954909 48050152 18154775 184154 2464289 45021212 25887291 55126702 45503461 22797200
PCG
31381713 37913420 0 26205595 25544268 39271575 0 61743597 20440157 57150032 58927325 59393360 34294787 54232947 36688242
 66694077 11101634 46655369 6358737 0 55062528 28064038 22244511 1822959 46499201 61518696 7140212 30875115 4198100 2297
8979 10106569 7170095 58286645 0 0 18913818 0 32264092 51212781 2639669 0 21640942 61959758 37880948 0 56304255 42969965
 1511042 38558452 23887166 15037535 27244971 54690528 0 4068799 60724964 2167865 15498384 43771545 9212944 44872075 2257
3910 21475675 0 51059015 63561011 0 30113077 63320612 58872163 4851337 32238879 0 35353450 21171206 18794089 36275059 0
45269550 11215153

It's very unlikely that PCG will return so many zeros. With 54 state_bits, zeros everywhere:

Code: Select all

 54-bits

 CSG_Collection

LCG
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
PCG
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

What do you mean with 'investigate the period of a 'random number generator' on a micro scale'? I'm unfortunately very ill positioned on this one, but I'll try to help anyway <:whispers: we should try to draw deltarho's attention here!> =D
dafhi
Posts: 1165
Joined: Jun 04, 2005 9:51

Re: csg dev framework - pre-release

Postby dafhi » Sep 15, 2018 4:16

paul doe wrote:Dafhi:

As we talked, I took a look at your code. Seems like the limit is in 54 state_bits. With 53 state_bits, you start to see anomalies in the output:

hmm .. thank you for your time. I'll have a think
paul doe wrote:Dafhi:
What do you mean with 'investigate the period of a 'random number generator' on a micro scale'? I'm unfortunately very ill positioned on this one, but I'll try to help anyway <:whispers: we should try to draw deltarho's attention here!> =D

try

Code: Select all

var                       state_bits = 10

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
 
paul doe
Posts: 701
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: csg dev framework - pre-release

Postby paul doe » Sep 15, 2018 10:59

Ah, I see now. You're seeing the effect the period has in the PD. I was looking at the MiniBits class and try to figure it out. If I understand correctly, you're essentially using it for doing the operations on a bit by bit basis. Did you checked the equivalence of the output from the generators with the output from your CSG, with the same bitness?
dafhi
Posts: 1165
Joined: Jun 04, 2005 9:51

Re: csg dev framework - pre-release

Postby dafhi » Sep 15, 2018 11:56

Im using minibits to visualize the output across different scales. Essentially i can tile a reduced-bit pcg on-screen. Its also easy to note uniformity by the overall brightness. early on, i did find a winner and period wise, it smokes. Thanks for asking :D

Return to “Projects”

Who is online

Users browsing this forum: No registered users and 4 guests