Skip to content

Latest commit

 

History

History
227 lines (202 loc) · 11.8 KB

RESEARCH.md

File metadata and controls

227 lines (202 loc) · 11.8 KB
Raw

Research

These are my backed up notes as I tried out various random generators and read prio art.

TODO

  • Try out the suggested algorithm that supports random access random number generation that isn't expensive.

  • Tests

    • Shouldn't we be dividing by (MAX_U32-1), so that we can actually hit 1.0?
      • Need to think this out, want to make sure we are absolutely as close to unbiased in a direction as possible in generators such as (inclusive of both min/max) [-1,1] that want values between
    • Run exhaustive tests? (Maybe separately from main tests)
      • Run for both next/prev but also scramble/unscramble
    • Prelimary tests of calling generate.next 2^32 times took 70s, so it's entirely feasible to do exhaustive tests of properties
      • Note: To ensure every value was hit and only once: new Array(Math.pow(2,32)) fails, but using new Array(Math.pow(2,32)/32) and then using a u32 and bit checks should work

  • Add shuffling at some point

  • Cleanup API/module structure, support functional and OO styles

    • Functional:
    import {seed, next, prev, scramble, unscramble, range, percent, float, bits, integer} from 'arbitrary';
let state = seed(state|undefined); // undefined is equivalent to 0. any non positive integer throws an exception
const bitMask = bits(state, bitCount)
// Roll the state forward one step before generating more values
state = next(state);
// Create a new stream of random numbers by deriving a new state from the existing one
const fork = scramble(state);
const anotherNumber = integer(forkedState, 0, 10);
    • OO: 
      import {Generator} from 'arbitrary';
const generator = new Generator(state|undefined); // undefined is equivalent to 0. any non positive integer throws an exception

// Generate a number between 0 and bitCount^2 - 1 (Using current generator state, AND advancing the state);
generator.bits(bitCount);
// Step the generator forward one step
generator.next();
// Step the generator backwards one step
generator.next();
- generate

  • Random filling of 2d array (good for old school cross fade, but also for ray tracing?)

  • http://fabiensanglard.net/fizzlefade/index.php

  • Find a good two way 32 bit hash

  • Neat Hash algorithms

  • Goal builds an entire game world that is purely reversible

    • See if we can make card games reversible
    • Card game strategies
    • Character movement
    • Everything! (Or maybe make single simple game test beds. Especially classics like boids, A*, etc)

  • First test that this approach works for all number ranges

  • Then strip down use of Long library code

  • Really document and get it understood (Defer, maybe it's time to move on)

  • Now start thinking about a good API design

  • I prefer the var generate = arbitrary.Generator() and arbitrary.float(min|min,max)

  • Can we make it both play well with immutable style APIs and the convenience of a self mutating one?

  • Add an entry here (pointing to my implementation):

  • Consider making a generalized library for reversible applications (T-Functions (or is that just for bit oriented ones), T-Applications?)

  • Do try out xorshift

Generate random numbers.

Using LCG First

  • Verify algorithm works at each range of values (no small walks because of integer precision issues)
  • Make sure all math works as expected for u32, addition and multiplication operations need to wrap correctly
    • Pretty sure multiplication blows past the precision needed when the state is near the top of the value range
    • Also the addition of the increment should wrap in 32 bit space I believe (Actually maybe not)
  • Add u32
  • Add i32
  • Add u32Range
  • Add i32Range
  • Make sure that the if we add a true random number generator that pulls from say Math.random() that we log a warning to indicate that you should only use it once

LESSONS LEARNED SO FAR

  • Build everything with T-Functions (bijective operations on n-bit ring numbers)
  • You could likely build many structured generators such as spiral, hilbert space, random full coverage 2D sample, etc

Search for algorithms with some or all of the following properties:

  • algorithm is reversible (you can go back to a previous state given a current state)
  • algorithm is random access (you can provide an index [0, 2^32) that generates a good random value)
  • fast
  • maximum period length for state bit size (ie 32 bit state should generate 2^32 unique values before looping again)
  • lastly but less important: the usual ideal PRNG properties

Good References

TODO:

Installation

  npm install arbitrary

Usage

Basics

var arbitrary = require('arbitrary');

console.log(arbitrary.float());
console.log(arbitrary.integer());
console.log(arbitrary.shuffle([1, 2, 3, 4]));
console.log(arbitrary.choice([1, 2, 3, 4]));
console.log(arbitrary.sample([1, 2, 3, 4], 2));

Manage your own instances:

var arbitrary = require('arbitrary'),
    generate = new arbitrary.Generator();

console.log(generate.float());
console.log(generate.integer());
console.log(generate.shuffle([1, 2, 3, 4]));
console.log(generate.choice([1, 2, 3, 4]));
console.log(generate.sample([1, 2, 3, 4], 2));

Project Goals

  • Be able to easily clone a generator instance
  • Be able to step a generator backward (soft requirement, as it's 28 bytes for the total state. But that could add up if you want to go backwards in time and rollback generator state.)
  • Be efficient.
  • Provide Module Distributions
    • Vanilla .js file
    • Browserfy
    • Require
    • Bower

Todo

  • Add noise, shuffle, serialize(getState() instead?), deserialize(setState() instead?), functions. Also look for my other notes.
  • Should we add support for generating higher dimensional and compound objects like: Vector2D, Vector3D, rgb (compatible with svg/canvas/dom), rgba(compatible with svg/canvas/dom), normal2D, normal3D, quaternion, etc?
  • Checkout other PRNG libraries.
  • Explain the benefits better. Is performance reason enough? Probably, espcially in Javascript.
  • Reserve arbitrary npm module name
  • Use WebCryptoAPI instead of time for original seed? Doesn't really make sense considering security is not our use case.
  • Try porting to javascript using emscripten
  • If emscripten doesn't work out well or at all, port it manually to Javascript.
  • Write tests
    • Make sure integer range parameters make sense
    • Make sure shuffles shuffle every element (Also that the last element is sometimes shuffled to, not just from which is guaranteed from our looping approach)
    • Sanity check distribution, performance, and anything else that adds integrity
    • Should we start guaranteeing backward compatible determism? (This might be too high of a constraint)
    • What about just general cross environment determinism (ie, same seed same outputs in every browser and node etc)
  • Give a list of references and history lessong for the general MT work as well as the TinyMT implementation.
  • Read through: PCG, A Family of Better Random Number Generators

References