mercredi 30 janvier 2019

ES6 : rolling and testing my own PRNG hash hex key generator?

for building some VNodes based app, I need a function that can generate pseudo random numbers, used as unique IDs, with a 3 or 4 bytes sizes.

Think a random RGB or RBBA, CSS-like string colors like : 'bada55' or '900dcafe'... User could seed the generator by picking a random pixel in a PNG image, for example.

Due to functionnal aspects of my app, generator must a pure function avpoding side effects like : using Math.random...

I'm not aware of artithmetic theories (my courses are so far in past...) but I decided to roll a custom PRNG, using Multiply-With-Carry (MWC) paradigm, and test it empirically with some prime coeffs, and random colors seeds.

My idea is to test it with 1-byte, 2-bytes, 3-bytes, and then 4-bytes outputs : my feelings are :

  • identifiying "good" primes and potential 'bad' seeds when number of bytes is lower
  • and try to test it against a cresing number of bytes

Sadly, performances seems to be poor, but I can't figure what is going wrong... Does anyone have an idea ?

Here's the generators code:

// length of internal state and output
const MAX_CELLS = 2  /// 1, 2, 3, 4

// for output formatting
const fmt = n => {
  const s = n.toString(16)

  if(s.length === 0) return '00'
  if(s.length === 1) return '0' + s

  // lower digits
  return s.substr(s.length - 2, 2)
}

// the lib exports a 'next' function inside it
export const createMWC = params => {

  const Z0 = new Array(MAX_CELLS) // from seed
  const Zi = new Array(MAX_CELLS) // state
  const Xi = new Array(MAX_CELLS) // temp
  const Ci = new Array(MAX_CELLS) // carries

  const M = (params && params.modulus)    ? params.modulus : Math.pow(256, MAX_CELLS)
  const A = (params && params.multiplier) ? params.multiplier : 197
  const C = (params && params.increment)  ? params.increment : 1
  const seed = (params && params.seed) ? params.seed : ('00').repeat(MAX_CELLS)

  for(let i = 0; i < MAX_CELLS; i++) {
    Zi[i] = parseInt(('' + seed).substr(2  * i, 2), 16)
    Z0[i] = Zi[i]
    Ci[i] = (C * i) % M
  }

  // the generator function
  const next = () => {
    turns++

    // main loop
    for (let i = 0; i < MAX_CELLS; i++) {
      Xi[i] = A * Zi[i] + (i > 0 ? Ci[i - 1] : Ci[MAX_CELLS - 1])
      Ci[i] = Math.floor((A * Zi[i] + Ci[i]) /  M)
      Zi[i] = Xi[i] % M
    }

    //if (Zi === Z0) {
    //  throw new Error ('CYCLED at i=' + turns)
    //}

    let output = Zi.map(n => fmt(n)).join('')

    return output
  }

  let turns = 0
  let carry = 0

  return { next }

  } // end of createMWC function
} // end of ES6 module




Aucun commentaire:

Enregistrer un commentaire