Random number in PASM

Bean

In the PropBASIC compiler I'm using the same code to generate a random number as spin uses. But it's not working right, it seems to be random for a little while (maybe 50 or so calls) then it gets "stuck" and generates the same number everytime.

I must admit I'm not sure what the code is doing, but I though I copied it's function exactly but I can't seem to see where I went wrong.

 
                min         seed,#1                          '    RANDOM seed, x
                mov         __temp1,#32                     
                mov         __temp2,#%10111                 
    IF_NZ       ror         __temp2,#1                      
__L0002                                                     
                test        seed,__temp2 WC                 
    IF_Z        rcr         seed,#1                         
    IF_NZ       rcl         seed,#1                         
                djnz        __temp1,#__L0002 WC             
                mov         X,seed                          
 
 
 
:rnd                    min     x,#1                    '?var/var?
                        mov     y,#32
                        mov     a,#%10111
        if_nz           ror     a,#1
:rndlp                  test    x,a             wc
        if_z            rcr     x,#1
        if_nz           rcl     x,#1
                        djnz    y,#:rndlp       wc      'c=0
                        jmp     #:stack

 

The top code is generated by the PropBASIC compiler, the bottom code is from the interpreter.spin file that chip posted.
I'm not sure why the "if_nz" condition is on the "ror a,#1" line ??? It's not in even in the loop...

Bean.



▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Does that byte of memory hold "A", 65, $41 or %01000001 ?
Yes it does...


·

mctrivia

Google pseudo random number therom

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
24 bit LCD Breakout Board coming soon. $21.99 has backlight driver and touch sensitive decoder.

JonnyMac

Bean: It appears that the Z flag has been dealt with before going into the Spin version of the code; this assumption is based on the IF_Z and IF_NZ conditionals that appear in the listing. Perhaps you need to add a cmp instruction at the top to set/clear the Z flag. Just a thought.

cgracey

JonnyMac said...
Bean: It appears that the Z flag has been dealt with before going into the Spin version of the code; this assumption is based on the IF_Z and IF_NZ conditionals that appear in the listing. Perhaps you need to add a cmp instruction at the top to set/clear the Z flag. Just a thought.

That's right. The Z flag must hold the forward/reverse bit before you begin this code sequence.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔


Chip Gracey
Parallax, Inc.

Bean

Ahh, okay that makes sense.

I changed it to this, and it seems to be working now. Thanks.

                min         seed,#1                          '    RANDOM seed, x
                mov         __temp1,#32                     
                mov         __temp2,#%10111                 
                ror         __temp2,#1                      
__L0002                                                     
                test        seed,__temp2 WC                 
                rcl         seed,#1                         
                djnz        __temp1,#__L0002 WC             
                mov         X,seed                          

Bean

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Does that byte of memory hold "A", 65, $41 or %01000001 ?
Yes it does...


·

cgracey

Bean,
Here is a more efficient version:

 
                min         seed,#1                          '    RANDOM seed, x
                mov         __temp1,#32                     
__L0002                                                     
                test        seed,#%10111     WC                 
                rcr         seed,#1                         
                djnz        __temp1,#__L0002 WC             
                mov         X,seed                          
 
 

If you don't need all 32 bits changed, you can do this:

 
                min         seed,#1                          '    RANDOM seed, x
                test        seed,#%10111     WC                 
                rcr         seed,#1                         
                mov         X,seed

To break up·the LFSR·pattern, you could periodically do 'add seed,#1'.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔


Chip Gracey
Parallax, Inc.

Bean

Good suggestion Chip. I'll implement that.

While I have you, I have a problem with the Propeller Tool IDE.

When I compile a file, the PropBASIC IDE calls the propeller tool with the newly created filename. Problem is, if the propeller tool already has the old version of that file open, it doesn't reload it. So you must manually close the file everytime in the propeller tool IDE. Is there any chance of having the propeller tool reload the new version of the file ?

Bean.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Does that byte of memory hold "A", 65, $41 or %01000001 ?
Yes it does...


·

Phil Pilgrim (PhiPi)

Here's some output from various LFSRs using Chip's algo (simulated in Perl). Each is a scatter plot, where the X axis represents a value of the seed; the Y axis, the next value of the seed, based on the algorithm application stated. Each has 256 samples.

1. One LFSR transition:



2. One LFSR transition, and add one to the seed each time:



3. 32 LFSR transitions:



-Phil

Ahle2

In my SID emulator I had to use the most minimalistic random noise generation possible. (thanks to the limited space left and to make it fast enough)

Algorithm:
1. Add a value
2. Rotate the bits

    add        random, addValue
    ror        random, rotateValue

After many attempts I found out that addValue = $8080_8080 and rotateValue = #17 produces a very good result. (white noice)
By ear I found out that addValue = $9030_3090 and rotateValue = 16 is very close to the the noise generation of the real SID. (even though a real SID uses a MUCH more complex noise generation)

JonnyMac

I wonder if our pal Phil would be kind enough to provide a scatter graph of Ahle2's algorithm -- would be interesting to see just how random it is.

Lawson

If you need 32 random bits fast, I'd recommend using XORshift. (top of page 4 is the code I based my ASM on) I build one into a recent bit of ASM. The code uses 9 instructions with no loops plus 1 long of temp space and 1 long of result space. The code is a little bigger than an LFSR but faster once more than 5 random bits are needed.

Lawson

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Lunch cures all problems! have you had lunch?

mctrivia

Y is random value x is iteration number

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
24 bit LCD Breakout Board coming soon. $21.99 has backlight driver and touch sensitive decoder.

Dr_Acula

Interesting plots there PhiPi. One of the first programs I wrote was an x,y plot of MBASIC's random number generator. Which duly produced some lovely lines on the screen.

I've been pondering random numbers for some time. I want a network of boards to talk wirelessly after a random time. The problem is they all start off with the same seed and then all generate the same delay and all talk at once. It is not easy, as where do you get a truly random seed? From the time/date on a clock chip? From the temperature? From the delay to the first keypress (but that doesn't work if the board is autobooting and there is no user input). Is it worth devoting a pin on the propeller to reading the quantum noise of a transistor junction?

Some nifty code examples above that I might borrow, if I may.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
www.smarthome.viviti.com/propeller

mctrivia

Chips real random object works well. Takes a cog but you can use it to generate a seed then kill it.

Or use my I'd object for a seed.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
24 bit LCD Breakout Board coming soon. $21.99 has backlight driver and touch sensitive decoder.

Dr_Acula

mctrivia, that sounds interesting. Could be useful for Bean too. Do the seed generation at powerup (if it doesn't take too long)?

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
www.smarthome.viviti.com/propeller

cgracey

The reason I suggested INC'ing the seed (and I should have added "...while waiting for a button press, or some event, before iterating the LFSR routinely") was because INC'ing steps wildly through what would have been many varied-count LFSR iterations. This would ensure that you don't start your LFSR pattern at nearly the same place each time.

At the beginning of RealRandom.spin in the OBEX is·a hard-won description of real random phenomena and why it requires something·analog and chaotic·from beyond the digital domain.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔


Chip Gracey
Parallax, Inc.

Ahle2

@mctrivia

It's quite obvious that my algorithm doesn't produce white noise and you can easily see patterns in the graph.
That doesn't matter in my case, because I don't want to have white noise anyway.

What did you use to plot the graph, i want to play around with it myself.
It's not very hard to code my own graph application, but if there's an alternative i'm interested.

mctrivia

Excel

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
24 bit LCD Breakout Board coming soon. $21.99 has backlight driver and touch sensitive decoder.

lonesock

@mctrivia: I tried Ahle2's code as well, and saw much better distributions with no hint of the 2 clusters seen in your graph. Here is my test C++ code, perhaps I did something wrong?

#include <fstream>

///    Starting with 0 is rocky
unsigned int seed = 0x13579BDF;//314159;

unsigned int r_1( void )
{
    const unsigned int ror_val = 17;
    const unsigned int add_val = 0x80808080;
    seed += add_val;
    seed = (seed >> ror_val) | (seed << (32 - ror_val));
    return seed;
}

int main( int argc, char** argv )
{
    std::ofstream fout( "rndlog.csv" );
    fout << "i,r,r%N" << std::endl;
    for( int i = 0; i < 1000; ++i )
    {
        unsigned int v = r_1();
        //unsigned int v = r_2();
        fout << i << "," << v << "," << (v % 256) << std::endl;
    }
    fout.close();

    return 0;
}

Jonathan

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
lonesock
Piranha are people too.

Phil Pilgrim (PhiPi)

I've been trying to simulate that algo in Perl but am having a devil of a time with overflow issues. 'Still haven't got it figured out...

Chip,

Yup, I misunderstood the intent of your "add 1" comment

-Phil

Ahle2

lonesock said...
@mctrivia: I tried Ahle2's code as well, and saw much better distributions with no hint of the 2 clusters seen in your graph. Here is my test C++ code, perhaps I did something wrong?

#include <fstream>

///    Starting with 0 is rocky
unsigned int seed = 0x13579BDF;//314159;

unsigned int r_1( void )
{
    const unsigned int ror_val = 17;
    const unsigned int add_val = 0x80808080;
    seed += add_val;
    seed = (seed >> ror_val) | (seed << (32 - ror_val));
    return seed;
}

int main( int argc, char** argv )
{
    std::ofstream fout( "rndlog.csv" );
    fout << "i,r,r%N" << std::endl;
    for( int i = 0; i < 1000; ++i )
    {
        unsigned int v = r_1();
        //unsigned int v = r_2();
        fout << i << "," << v << "," << (v % 256) << std::endl;
    }
    fout.close();

    return 0;
}

Jonathan

I can't see anything wrong in the code above.
I will do my own little graph with c++ + SDL soon.

mctrivia

Maybe my math is rong. Will recheck at home tonight

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
24 bit LCD Breakout Board coming soon. $21.99 has backlight driver and touch sensitive decoder.

Ahle2

Here is my result.
X = Itteration
Y = 32 bit random number

lonesock

Almost more importantly, it still looks pretty good if you only take the bottom 8 bits, for example.

Jonathan

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
lonesock
Piranha are people too.

VIRAND

I've found XOR LFSRs to be more predictable than Pi.
I've found that either replacing or adding an ADD-with-carry makes more Noise and less patterns.
And seeds can't get more random than adding how many microseconds it takes someone to press a button,
which seems to fit with the absolutely deterministic nature of Logic, and also the popular
theory of the randomizing effects of an "observer" on quantum mechanical phenomena.

Seriously, some LFSRs sound like MUSIC, and simply changing an XOR to ADDC gets WHITE NOISE instead.

My first apparently somewhat successful attempted pseudorandom number generator went something like

A=A+1
B=B XOR A
D=D ADC B

but it was used to get a Star Trek warp drive effect, and tended to occasionally appear to send stars
flying out from the center in the same random direction just a wee bit too often (such as 2 to 4 in a row).
Then again, I think I've proved that out of all the numbers that come up in a game of chance such as
Roulette, the last number immediately repeats more often than anybody's favorite number comes up.

Doesn't the Spin "?" function have to cycle through all other numbers before repeating one?
It certainly tends to make comets instead of stars when you plot points from it.

mctrivia

here is my excel file. i must have gooffed on the math somewhere. the extension needs to be changed to xls had to change l to 1 to be allowed to upload

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
24 bit LCD Breakout Board coming soon. $21.99 has backlight driver and touch sensitive decoder.

mctrivia

Anyone want to try this?

// Create a length 624 array to store the state of the generator
 int[noparse][[/noparse]0..623] MT
 int index = 0
 
 // Initialize the generator from a seed
 function initializeGenerator(int seed) {
     MT[noparse][[/noparse]0] := seed
     for i from 1 to 623 { // loop over each other element
         MT[i] := last 32 bits of(1812433253 * (MT[noparse][[/noparse]i-1] xor (right shift by 30 bits(MT[noparse][[/noparse]i-1]))) + i) // 0x6c078965
     }
 }
 
 // Extract a tempered pseudorandom number based on the index-th value,
 // calling generateNumbers() every 624 numbers
 function extractNumber() {
     if index == 0 {
         generateNumbers()
     }
     
     int y := MT[noparse][[/noparse]index]
     y := y xor (right shift by 11 bits(y))
     y := y xor (left shift by 7 bits(y) and (2636928640)) // 0x9d2c5680
     y := y xor (left shift by 15 bits(y) and (4022730752)) // 0xefc60000
     y := y xor (right shift by 18 bits(y))
     
     index := (index + 1) mod 624
     return y
 }
 
 // Generate an array of 624 untempered numbers
 function generateNumbers() {
     for i from 0 to 623 {
         int y := 32nd bit of(MT[i]) + last 31 bits of(MT[noparse][[/noparse](i+1) mod 624])
         MT[i] := MT[noparse][[/noparse](i + 397) mod 624] xor (right shift by 1 bit(y))
         if (y mod 2) == 1 { // y is odd
             MT[i] := MT[i] xor (2567483615) // 0x9908b0df
         }
     }
 }
[/i][/i][/i][/i][/i]

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
24 bit LCD Breakout Board coming soon. $21.99 has backlight driver and touch sensitive decoder.

cgracey

About LFSRs:

The way to test an n-bit-long LFSR for maximal run length is to seed it with a non-0 value (like 1), then iterate it up to 2^n times with a fixed tap set. If the initial number reappears, before 2^n - 1 iterations, you have a dud. If you never get the initial number back, you have a dud. Duds get caught up in sub-maximal loops, which may or may not include the initial number. If you get the initial number back on the 2^n - 1th iteration, you have a maximal-length tap set, which is ideal. To get the initial number back at the 2^n - 1th iteration, the LFSR must have cycled through every non-0 possibility, which gives you the most bang for the number of bits in the LFSR.

Here's a page that lists maximal-length LFSR taps sets by LFSR bit length:


http://www.ece.cmu.edu/~koopman/lfsr/index.html

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔


Chip Gracey
Parallax, Inc.

Post Edited (Chip Gracey (Parallax)) : 12/2/2009 2:20:26 AM GMT

Rayman

With Prop2 we'll have mul and div...· Then, maybe you can convert something like this Spin one into PASM:

PRI RND(n):x|r2,r5            'x[noparse][[/noparse]i]=(192+179*x[noparse][[/noparse]i-1]) mod 577; x[noparse][[/noparse]1]=238
    'a basic LCG psuedo-random number generator
    'http://en.wikipedia.org/wiki/Linear_congruential_generator
    'generates a number 0..576 used to return number 0..n
    'n must be much less than 577
   x:=(192+179*RND1)//577
   RND1:=x
   x:=x*n/577

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
My Prop Info&Apps: ·http://www.rayslogic.com/propeller/propeller.htm

Lawson

Lawson said...
If you need 32 random bits fast, I'd recommend using XORshift. (top of page 4 is the code I based my ASM on) I build one into a recent bit of ASM. The code uses 9 instructions with no loops plus 1 long of temp space and 1 long of result space. The code is a little bigger than an LFSR but faster once more than 5 random bits are needed.

Lawson

The code I used for my XORshift RNG

'xor-shift RNG.  Uses temp1 as the seed/result.  Temp2 is mangled during execution.  I still need to test the quality of this.
xorshift      mov       temp2,  temp1           'copy input                     {make this just operate on a "seed" that it updates each time it's run}
              shl       temp2,  #13             'shift input copy by "c" = 13
              xor       temp1,  temp2           'xor shifted input with input
              mov       temp2,  temp1           'copy input
              shr       temp2,  #17             'shift input copy by "b" = 17
              xor       temp1,  temp2           'xor shifted input with input
              mov       temp2,  temp1           'copy input
              shl       temp2,  #5              'shift input copy by "a" = 5
              xor       temp1,  temp2           'xor shifted input with input
xorshift_ret  ret

'and the variables
temp1         res       1       'used for temporary values and parameter passing
temp2         res       1

It worked well enough for some test signal generation code.

Lawson

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Lunch cures all problems! have you had lunch?

lonesock

Ahle2 said...
In my SID emulator I had to use the most minimalistic random noise generation possible. (thanks to the limited space left and to make it fast enough)

Algorithm:
1. Add a value
2. Rotate the bits

    add        random, addValue
    ror        random, rotateValue

After many attempts I found out that addValue = $8080_8080 and rotateValue = #17 produces a very good result. (white noice)
By ear I found out that addValue = $9030_3090 and rotateValue = 16 is very close to the the noise generation of the real SID. (even though a real SID uses a MUCH more complex noise generation)

BTW, I found that adding "ror random,random" at the end made for a better distribution, specially if you accidentally start out with a seed of 0. (note: ROR will internally AND the rotation value with 31.) There are still certain bands that seem more likely to come up (with 25,000 values plotted), but to me this version looks a bit better than the original 2-instruction version.

Jonathan

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
lonesock
Piranha are people too.