JKISS32, High quality PRNG with RealRandom seed, save a COG.

Heater.Heater. Posts: 21,213
edited 2018-03-13 - 07:48:49 in Propeller 1
There has been much talk of random numbers here recently, both real and pseudo. What with Cessnapilot's suggestion to use CNT as a random source at start up and Bit's (was it?) request for a random shuffling algorithm.

This reignited my long standing fascination for such things and the result is my Christmas break project was one super-duper random number generator for the Propeller which is attached here.

The simple idea is:
1) We would quite often like to use genuine random numbers form some random source. At least so that our programs don't behave the same way on every run as they might with Spins random operator. An easy way to do that is with Chip's magical RealRandom object. BUT that consumes a whole valuable COG for such a simple task.
2) So we could start up RealRandom, get real random seed from it, shut it down to save a COG and then use the seed for Spins built in random operator in our applications.
3) BUT whilst we are at it why not use a pseudo random number generator with a huge repetition period and probably more random looking sequences? That way we would be hard pressed to tell the difference between using RealRandom all the time or a randomly seeded PRNG.

Most high quality PRNGs use unsigned arithmetic and/or 64 bit arithmetic and/or multiplies and are therefore not very Spin friendly. Luckly over Christmas I found the JKISS32 algorithm by David Jones, based on ideas by the late George Marsaglia, an expert in PRNG's. JKISS32 uses 32 bit signed arithmetic, only uses a handful of lines of Spin and has a period of ~2^121. That is the "random" number sequence it generates will only start to repeat after about 2600000000000000000000000000000000000 numbers !!! (if I have counted my zeros correctly). JKISS32 has been tested with some serious statistical tools to check the quality of it's "randomness" and passed with flying colours.

P.S. Again I have to say I don't imply that Spin's random operator is faulty but sometimes we might like to have better. For example Bit's shuffling project could do with very long period PRNG. Also it can be beneficial to not use built in system RNG's and use you own, this way when you move your code from system to system you can be sure of consistent high quality results.

Comments

  • JonnyMacJonnyMac Posts: 6,240
    edited 2011-12-31 - 10:41:49
    Very cool and very useful.

    Just a note on the demo: You're outputting to a terminal at 115.2K baud but left the clock and pll settings out of the code. Easy to add, but I'm sure a newbie miss it and ask why the terminal screen is filled with garbage.

    Also, the copy of RealRandom in the archive returns before the 5ms "warm-up."
    Jon McPhalen
    Hollywood, CA
    It's Jon or JonnyMac -- please do not call me Jonny.
  • bsnutbsnut Posts: 520
    edited 2011-12-31 - 11:18:48
    I agree with Jon how useful it will be. I think its wasteful to use a whole cog for such easy task like generating random numbers. You also put the random back in to random
    William Stefan
    The Basic Stamp Nut with some Spin
  • Cluso99Cluso99 Posts: 15,409
    edited 2011-12-31 - 11:32:53
    Neat work heater.

    Since the prop has optional carry calculation, does this affect the spin code because carry will not normally be changing ???
    My Prop boards: P8XBlade2, RamBlade, CpuBlade, TriBlade
    Prop OS (also see Sphinx, PropDos, PropCmd, Spinix)
    Website: www.clusos.com
    Prop Tools (Index) , Emulators (Index) , ZiCog (Z80)
  • Heater.Heater. Posts: 21,213
    edited 2011-12-31 - 12:28:45
    All sensible answers comming after I have finished toasting the new year here in Finland:)
  • mindrobotsmindrobots Posts: 6,506
    edited 2011-12-31 - 12:41:01
    Heater, you're a sensible man and have your priorities straight. Happy 2012!!

    Random numbers can wait one more day!
    MOV OUTA, PEACE <div>Rick </div><div>"I've stopped using programming languages with Garbage Collection, they keep deleting my source code!!"</div>
  • Phil Pilgrim (PhiPi)Phil Pilgrim (PhiPi) Posts: 22,442
    edited 2011-12-31 - 13:08:28
    Happy New Year, Heater!
    heater wrote:
    All sensible answers comming after I have finished toasting the new year here in Finland
    Immediately after, please. ('Just curious to see what "sensible answers" look like after several shots of Akvaviitti. :) )

    -Phil
    “Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away. -Antoine de Saint-Exupery
  • PublisonPublison Posts: 10,964
    edited 2011-12-31 - 13:28:08
    mindrobots wrote: »
    Heater, you're a sensible man and have your priorities straight. Happy 2012!!

    Random numbers can wait one more day!

    Or 2 or 5 or 7 or.....
    Infernal Machine
  • Heater.Heater. Posts: 21,213
    edited 2011-12-31 - 13:41:18
    Phil,
    No, no, this is not Sweden this is Finland. Here we drink Koskenkorva. But as an expat Brit I also need my whisky to see in the new year.
  • Cluso99Cluso99 Posts: 15,409
    edited 2011-12-31 - 14:13:28
    Happy New Year, Heater!

    Immediately after, please. ('Just curious to see what "sensible answers" look like after several shots of Akvaviitti. :) )

    -Phil

    Whisky or whatever, I do hope the sensible answers are not chosen at random ;)

    Happy New Year to all
    My Prop boards: P8XBlade2, RamBlade, CpuBlade, TriBlade
    Prop OS (also see Sphinx, PropDos, PropCmd, Spinix)
    Website: www.clusos.com
    Prop Tools (Index) , Emulators (Index) , ZiCog (Z80)
  • rogersydrogersyd Posts: 201
    edited 2012-01-01 - 08:00:20
    JonnyMac wrote: »
    Very cool and very useful.

    Just a note on the demo: You're outputting to a terminal at 115.2K baud but left the clock and pll settings out of the code. Easy to add, but I'm sure a newbie miss it and ask why the terminal screen is filled with garbage...."

    Ohhh THATS why my terminal is full of garbage. Very cool code indeed. Will be useful in my current project. Thanks!
  • Heater.Heater. Posts: 21,213
    edited 2012-01-01 - 20:24:01
    JonnyMac,

    Good point, clock settings are added to the new version now in the first post.

    I noticed that little problem with RealRandom. Well actually it's a major problem when used like this.That's not me it's in OBEX like that. The demo works around it by discarding all zeros returned by RealRandom at start up. Perhaps a longer delay would be better, not sure.

    Cluso,

    This is an "add-with-carry generator" but as you see the code does not use the Props carry directly (How could it in Spin or C?). But the carry c is just a variable set when t is less than zero and cleared otherwise. Note the "& 1" I had to add in there to get the same effect as the C version.


    Now the search is on for a PRNG with an even longer period. The ones I have found so far start to get much bigger code wise and/or use large arrays. I'm really not into translating the Mersenne Twister into Spin. http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
  • Heater.Heater. Posts: 21,213
    edited 2012-01-02 - 03:20:35
    I did some testing of JKISS32 with CessnaPilot's BUST program. (See OBEX #624).

    BUST does a bunch of statistical tests on number sequences to try and detect non-randomness. In each run 5 different tests are run over 100 sets of 1000 generated numbers. For real random data one would expect 23 of the tests to fail +/-6 or so. Out side that there is some question about the randomness of your source of numbers.

    JKISS32 has bee doing quite well in these tests with scores of 19, 17, 24, 33, 21, 25, 29 so far. That 33 is outside acceptable limits but as CessnaPilot notes in the BUST code "With randomness you can be never sure."

    Spin's built in random operator "?" is a dismal failure with scores of 40, 45, 45. Not one of them within acceptable limits. Hardly random at all:)

    This is all rather slow going so it's time to fill up and SD card with randomness and analyze it with the dieharder or similar test package.
Sign In or Register to comment.