Not Prime!

[matthew180]

I've been using the same random number generator fin my assembly programs for about 25 years now, and I got it straight from the Tombstone City code that came with the E/A package. This is the code:

RAND16 EQU  >83C0
.
.
.
      LI   R4,28645
      MPY  @RAND16,R4
      AI   R5,31417
      MOV  R5,@RAND16

The address >830C is used because the console "OS" (if you can call it that) places the amount of time it took the user to press a key on the Mater Title Screen (or something like that anyway.) So, it makes for a truly random seed value. After that it falls down miserably.

 

Good random numbers usually start with prime numbers, since random numbers in computers are fake anyway (which is why we call them pseudo-random numbers), using primes help make them as random as possible (so I have read.) When I first used this code I had no idea what those numbers were for and why they were chosen, I was just happy to have some random looking numbers. In the last few projects I've done, when I was reviewing the code, I assumed they were at least prime, but I just checked and they are not!

 

Also, the code above has the non random feature of producing an odd number, then even, then odd, then even, etc. Not very random. Adamantyr posted a variation that he uses in his code that mixes up the bits depending on the current "tick" (a counter that is incremented every VSYNC), and this helps scramble things up and at the very least gets rid of the odd, even, odd nature of the original. Here is his code (taken from a previous post):

      LI   R4,23729
      MPY  @>83C0,R4
      AI   R5,31871
      MOV  @CLOCK,R0
      ANDI R0,>000F
      SRC  R5,0
      MOV  R5,@>83C0

The top part is the same, but after the addition he uses the bottom 4-bits of the tick counter to be a 0 to 15 bit circular shift of the random number. When you use a zero count with the shift instructions, the count is taken from R0. His numbers are a little different than the original ones from Tombstone City, but they are also not prime:

 

28645 is not prime. It is divisible by 5.

31417 is not prime. It is divisible by 89.

23729 is not prime. It is divisible by 61.

31871 is not prime. It is divisible by 7.

 

So, I've made a few modifications in an attempt to make this thing a little more random. Keep in mind that a RNG is deep math and science and I in no way pretend to have a solid grasp on any of this. I just know that the original RNG creates very *bad* random numbers, and this one produces numbers that look and act much more random.

RAND16 EQU  >83C0

. . .

*********************************************************************
*
* Generates a weak pseudo random number and places it in RAND16
*
* R4   - Destroyed
* R5   - 16-bit random number and stored in RAND16 for next round
*
RANDNO
      LI   R4,28643          * A prime number to multiply by
      MPY  @RAND16,R4        * Multiply by last random number
      AI   R5,31873          * Add a prime number
      MOV  R0,R4             * Save R0
      MOV  @TICK,R0          * Use the VSYNC tick to mix it up a little
      ANDI R0,>000F          * Check if shift count is 0
      JEQ  RAND01            * A 0 count means shift 16, which is a wash
      SRC  R5,0              * Mix up the number to break odd/even pattern
RAND01 MOV  R5,@RAND16        * Save this number for next time
      MOV  R4,R0             * Restore R0
      B    *R11
*// RANDNO

This is a slight variation on Adamantyr's code in that I'm checking if the number of bits to rotate is zero, since a zero count in R0 means shift 16 bits, which since the shift being used is circular (SRC), does nothing except take the max clock cycles for a shift instruction which is about 56 clocks. I also save and restore R0 (R0 has to be used because it is the only register that can hold a variable-based count for the shift instructions.)

 

This will be going into my assembly language tutorial, which is the main reason I was revisiting it. The demo I set up was not filling the screen randomly, there were definite patterns that make it easy to see how *not random* the original was.

 

Matthew

Edited May 26, 2010 by matthew180

[+adamantyr]

Also, the code above has the non random feature of producing an odd number, then even, then odd, then even, etc. Not very random. Adamantyr posted a variation that he uses in his code that mixes up the bits depending on the current "tick" (a counter that is incremented every VSYNC), and this helps scramble things up and at the very least gets rid of the odd, even, odd nature of the original. Here is his code (taken from a previous post):

      LI   R4,23729
      MPY  @>83C0,R4
      AI   R5,31871
      MOV  @CLOCK,R0
      ANDI R0,>000F
      SRC  R5,0
      MOV  R5,@>83C0

The top part is the same, but after the addition he uses the bottom 4-bits of the tick counter to be a 0 to 15 bit circular shift of the random number. When you use a zero count with the shift instructions, the count is taken from R0. His numbers are a little different than the original ones from Tombstone City, but they are also not prime:

 

28645 is not prime. It is divisible by 5.

31417 is not prime. It is divisible by 89.

23729 is not prime. It is divisible by 61.

31871 is not prime. It is divisible by 7.

 

I think the main point of the values isn't that they're prime, but that they're under 32767. I noticed when I tried bigger values in the high-positive/negative range, the random numbers ended up all being the same value or very low values consistently... I should have guessed that prime numbers were intended there, I'll try swapping my values for primes as well.

 

This is a slight variation on Adamantyr's code in that I'm checking if the number of bits to rotate is zero, since a zero count in R0 means shift 16 bits, which since the shift being used is circular (SRC), does nothing except take the max clock cycles for a shift instruction which is about 56 clocks. I also save and restore R0 (R0 has to be used because it is the only register that can hold a variable-based count for the shift instructions.)

 

Yeah, I knew about the shift 0 issue. If you don't use the circular shift, it has the added penalty of wiping out the register entirely! Why they did that and didn't build the check right into the op-code circuitry I wonder...

 

I skipped over a check because the 56 cycles of waiting wasn't a huge hit for me in my CRPG; most of my random generation is occurring in human-time scale, not computer time-scale.

 

Adamantyr

[danwinslow]

As far as I know, being prime or not has nothing to so with the 'randomness' of a sequence of numbers. Note that a number by itself has no quality of randomness at all...randomness applies to a *sequence*, not to a single number. In fact, a sequence of prime numbers is probably less random than a sequence of non-primes, due to the fact that there are more numbers that are not prime.

 

If you want evaluate your randomness, generate a huge series of numbers and count how times each digit appears. The closer all of the digit counts are to each other, the better your random distribution is. Or, you can pick a smaller range, say 1 to 10000, and generate 10000 of them, counting up how many times each number appeared. Plot the distribution and you will see a curve that represents your randomicity.

Edited May 26, 2010 by danwinslow

[matthew180]

Interesting points. Like I said, I have very vague knowledge of actually how and why a RNG would be developed. Do you have any info or links to specific examples, papers, etc. on using primes vs. non primes? Or, just assembly RNGs in general. I found it very hard to find any good info the last time I Googled the topic.

 

I suppose I should run the virtual coin toss a few hundred times to see how primes vs. non primes works out.

 

Matthew

[danwinslow]

I think you might be talking about the seed or the modulus factors being prime, rather than the number itself. Primes are often chosen for the modulus because they give better results...but again, whether the resulting random number is prime or not has nothing to do with it.

 

http://en.wikipedia.org/wiki/Random_number_generation

http://www.math.utah.edu/~pa/Random/Random.html

 

The best way to achieve close to random is to use a good psuedo-RNG algorithm and then mix in some entropy ( hardware based randomness ) into the results. Keypress times, which scan line the screen is on, etc.

 

Randomness is interesting in itself, as a concept...it truly defies definition, since as soon as you define what random means it ceases to be random.

Edited May 26, 2010 by danwinslow

[matthew180]

Excellent, thanks! Seems like Adamantyr method of shifting based on the VSYNC is a good means of entropy, especially when coupled with the fact that games are highly driven by user input, so there will be variation of when functions get called based on human input. I wonder if there is a floating pin somewhere in the 99/4A that we could sample?

 

Matthew

[EricBall]

Wikipedia is a good starting place.

 

Most of my experience is with LFSRs, which have the advantage of being trivial to implement. To improve the "randomness", ensure the seed is as random as possible (i.e. the value of a free running counter when the user presses "start") and then cycle the PRNG based on an external random factor (i.e. user input).

[+retroclouds]

Until now I haven't done any experimenting with random number in assembly language, so this does make an interesting read.

 

This is good stuff!

[Tursi]

A function I've been using since the Dreamcast days is this one. It has a couple of interesting values.

 

1) it's relatively fast, taking very few opcodes

2) it's relatively random-ish (definately could be better, especially in the low bits. For small values I tend to shift it first)

3) it's non-repeating over the entire range. For whatever range you select (8 bits, 16 bits, 32 bits), each value is guaranteed to be selected exactly once. This makes it nice for pixel dissolves, apparently.

 

It's definately not the best for being RANDOM, too many things are predictable, but it has worked quite well for me for a number of years.

 

Here's the original post from the DCDev list.

 

There are some really fast ways to calculate random numbers if you don't care about the number to

be truly random. The following algorithm comes from the book Graphic Gems.

 

The algorithm takes a seed and a mask. For 16bit integers the mask is 0xb400 and the seed

can be any 16bit value exept 0. The function nextrand should be called with the previous random number,

rand = nextrand(rand); The first time the random number should be set to the seed.

 

#define MASK 0xb400
int rand = 1; /* Seed = 1 */

int nextrand(int rand)
{
if(rand & 1){ /* If the bit shifted out is a 1, perform the xor */
	rand >>= 1;
	rand ^= MASK;
}
else { /* Else just shift */
	rand >>= 1;
}

return(rand);
}

 

In SH4 assembler the algorithm could look like this:

 

	mov #1, r0	! Seed -> r0, seed must not be 0

! Calculate next random number, use r0 as seed and put result in r0
shlr r0		! Shift r0 1 bit to the right, carry goes to T bit in status register
bf nocarry	! If carry was not set, jump to label nocarry
xor #0xb400, r0 ! calculate new random number with 0xb400 as mask
nocarry:

 

 

What makes this algorithm special is that if nextrand is called 2^16 times, then the rand variable

will traverse all 2^16 (65535) different values (except 0) exactly 1 time, but in a pseudo random order.

And this is all done with just one shift, one xor and one conditional jump. Personally I use this algorithm to

make dissolve effects.

 

For different widths just use a different mask. Below is a table of masks and widths.

 

Mask (hex)	Width (bits)
03			2 
06			3
0C			4
14			5
30			6
60			7
B8			8
110			9
240			10
500			11
CA0			12
1B00			13
3500			14
6000			15
B400			16
12000			17
20400			18
72000			19
90000			20
140000			21
300000			22
400000			23
D80000			24
1200000			25
3880000			26
7200000			27
9000000			28
14000000		29
32800000		30
48000000		31
A3000000		32

Try it!

 

/Albert

 

Of course, in 9900 it would be something like this (I'll use RAND16 from above)

 

MASK DATA >B400
MOV @RAND16,R0	    * Seed -> r0, seed must not be 0 (normally read the seed from memory somewhere)

* Calculate next random number, use r0 as seed and put result in r0
SRL R0,1    * Shift r0 1 bit to the right, carry goes to C bit in status register
JNC NOCARR  * If carry was not set, jump to label nocarry
XOR @MASK,R0 * calculate new random number with 0xb400 as mask
NOCARR	MOV R0,@RAND16

 

Again, just another simple routine depending on your needs. I know I'll be trying some of the others in here.

[+adamantyr]

Pseudo-random number generation is a great topic for assembly programming.

 

As game programmers, we usually just want random numbers, and don't want to delve into a lot of philosophical discussion on the subject. Which means short, simple, and imperfect routines are great to start. Then when you realize you actually need it a BIT more random, you start finding out more. That's the fun of programming, finding out what you need based on your own experiences. That's one reason I'm so hard on Matt about the ISR, it's better for people to discover on their own this blasted ROM routine is sucking up cycles they need elsewhere.

 

That's a very simple and easy routine, Tursi. The best part about it is it doesn't involve division, which is the real cycle-sucker in any random number generator. The ARM processors that drive most mobile devices, like Game Boys, don't have a native division opcode, and most games don't need something too complicated for randomness. If you used another external boolean to determine the XOR, like the even/odd bit of the VSYNC, it would be pretty random!

 

Now if you take a procedurally generated game, like Elite, they actually use 6-byte random numbers, because a 16-bit integer just isn't enough. You also need it to be stable; once you "seed" it with a value the rest of it's calculations are predictable. That means no user-inputs to cause major chaos. The random number generator in BASIC is that way; if you seed it you'll get the same values over and over again. At least we had a RANDOMIZE option; I remember playing Lemonade Stand on the old Apple IIc and being amused that weather and factors were always the same... it always rained the first cloudy day, I remember, but not the subsequent day.

 

Adamantyr

[Tursi]

While trying out Matthew's example, I realized that if we aren't running interrupts (as we discussed in the other thread), and we don't manually run a vertical blank routine, we won't have a continuously changing counter to use. But then I thought about the 9901. There's a 14-bit timer in there that ticks at roughly 46.785kHz, independent of the rest of the system. Not very much TI software uses it (indeed, I only learned how to from Karsten's Sudoku). Setting that up to count continuously, and reading the value as needed, may provide a nice injection of unpredictability, too. If you stopped for user input a lot, you could pretty much consider the number totally random, but otherwise, I thought it might be nice to use as the shift counter in Matthew's code. The timer loops every 349.2 milliseconds if set to maximum range, so for anything where accessing it is not fully deterministic timewise, you could almost use it raw. If you set it for a smaller value like 255 (or just mask), where it would wrap every 5ms and for code that interacts with the user between reads, would appear pretty darn random.

 

Not 100% sure on this, but using it would be something like this (based on Thierry's code):

 

INIT01 CLR  R12         CRU base of the TMS9901 
      SBO  0           Enter timer mode 
      LI   R1,>3FFF    Maximum value
      INCT R12         Address of bit 1 
      LDCR R1,14       Load value 
      DECT R12         There is a faster way (see below) (Tursi - I didn't follow the faster way, unless it's LDCR for all 15 bits)
      SBZ  0           Exit clock mode, start decrementer 
      B    *R11        Return to caller

 

If you BL @INIT01, then, the timer will start running through it's maximum range continuously. To get the value, you just need to do this:

 

READ01 CLR  R12         CRU base of the TMS9901 again
      SBO  0           Enter timer mode 
      STCR R0,15       Read current value (plus mode bit)
      SRL  R0,1        Get rid of mode bit
      SBZ  0           Exit clock mode, decrementer continues
      B    *R11        Return - 14-bit counter value is in R0

 

So the BL @READ01 should return the current value of the counter into R0. Theirry's page says it doesn't halt the counter to read it, and since we didn't reset it, it should keep counting.

 

Maybe an extra little bit of randomness, anyway!

 

(edit) I've tested this code now, and it appears to work in Classic99 at least.

Edited May 28, 2010 by Tursi

[matthew180]

That's pretty cool! Actually in the code where I'm using the RNG, I have a TICK based on polling the VDP status register (Adam does too, since I borrowed the trick from him.) But, this extra timer is another excellent source of entropy. I'll have to read Thierry's 9901 page again and give this a try too.

 

We need to come up with a virtual coin toss program to test these RNG's. I have an idea so I'll try to get it coded up.

 

Matthew

[sometimes99er]

Wow, this is good stuff. Only problem is, I see the need for both predictable and unpredictable random numbers. Maybe I should implement RNDP and RNDU (totally independent) in Strawberry.

 

:thumbsup:

[matthew180]

Well, I did some testing on these routines last weekend (jeez, has it been that long.) I wanted to post more details, but I ran everything on my unix box with a text output at 100 columns and I think that would blow the width of the forum post. Anyway, I'll summarize for now.

 

First, my using prime number messed everything up, so don't do that! I was basically testing the original code from Tombstone City (T.C.), my modification using prime numbers, and the shift/xor routine that Tursi posted. I wanted to include Adam's modification that uses the VDP frame counter, but unfortunately I have no way to test that off the real hardware, so that one will have to wait for testing on a real 99/4A. The others relied simply on the algorithm so I could test on any computer.

 

The first thing I learned is that the numbers from the original T.C. routine where such that no number would be repeated until all 65536 numbers of the 16-bit value had been used! That shocked me and this characteristic of the routine is the same as that of the routine posted by Tursi. When I changed those numbers to prime, thinking that somehow that would make it better, it actually makes the function worse. A lot worse!

 

Another interesting thing is that the numbers in Adams routine do the same thing, i.e. cause all 65536 values to be used before repeating. Of course Adam's routine then goes on to add some entropy, so that affects the characteristic of not reusing a number until all of the values have been used. I'm not sure how that affects the randomness, it is simply a change.

 

So, right from the start I'm throwing out my "prime number" modification. Don't do that, it has nothing to do with randomness.

 

The original problem I had with the T.C. routine was the characteristic that every other number it produced was even. So for picking small values, like 1 to 4, it was terrible. The routine Tursi posted is good in that is does not have this problem. Actually I could no pattern that an odd/even repetition would occur. edit: I have no idea what I was trying to say...

 

I also tested the "coin toss" test. That basically says that if you toss a coin 100 times or so, if the tosses are truly random, at the end you should have 50 heads and 50 tails, or somewhere close to that. Of course the original T.C. routine makes a perfect 50/50 every time because every other number is even, so this test does not really help us determine if the T.C. routine is a good random number routine. The routine Tursi posted does give some nice results though. The biggest difference I saw over the 65536 values was 60/40, with the average being more like 57/63.

 

Another characteristic of these routines (except Adam's) is that they all repeat once you go through the full range of values. The only difference is that the shift/xor routine can not ever be 0. So, the "seed" is simply a starting point in the list, but the same order of numbers will always be returned. Meaning, 65535 possible seed values does not give you 65536 unique lists of number. For example, say we have a generator that makes 10 numbers:

 

5 8 3 9 0 1 4 2 7 6

 

A seed value of 4 would produce this list of numbers:

 

9 0 1 4 2 7 6 5 8 3

 

A seed value of 9 would produce:

 

7 6 5 8 3 9 0 1 4 2

 

Clear?

 

Now depending on how your program uses the random numbers, this may or may not be a problem, however knowing the algorithm being used, and any number returned by the generator will let you know all the remaining random numbers. Then if you know something about the code, you can then cheat and know what will happen. This is a problem for things like poker or card games, and was actually used to exploit a real online gambling site! They were so confident in their random number routine that they actually published it, and someone noticed they were seeding based on the server's timestamp. So, even modern systems have the same problems.

 

Thus:

                        unique    unique    seed                         uses
                        before    list per  determines            good   mpy or
                range   repeat    seed      order      odd/even   50/50  div

Tombstone City:  65536     Y         N          Y          Y        Y     Y (both)

Shift/Xor:       65535     Y         N          Y          N        Y     N
                (no 0)

Adam's           65536     N         Y          N          N        ?     Y (both)

 

Note that in Adam's routine the seed really has nothing to do with the order and the list of numbers will always be different because of the entropy added by the VDP counter and the variance of when the subroutine is called, which is probably based on user input, code execution time, and a lot of other factors.

 

Anyway, I'm going to stick with the shift/xor code for now. It produces good results and does not use the VERY SLOW mpy and div instructions. It could also easily be added to Adam's entropy method for some added randomness as the expense of not having the same order of numbers based on the seed value (which can be very handy for testing and troubleshooting.)

 

Also note that the shift/xor subroutine can be easily expanded to 32 or even 64 bit numbers, which would help make a larger list of numbers, but other than that it still has the same characteristics.

 

Matthew

Edited November 22, 2011 by matthew180

[+adamantyr]

                        unique    unique    seed                         uses
                        before    list per  determines            good   mpy or
                range   repeat    seed      order      odd/even   50/50  div

Tombstone City:  65536     Y         N          Y          Y        Y     Y (both)

Shift/Xor:       65535     Y         N          Y          N        Y     N
                (no 0)

Adam's           65536     N         Y          N          N        ?     Y (both)

 

Note that in Adam's routine the seed really has nothing to do with the order and the list of numbers will always be different because of the entropy added by the VDP counter and the variance of when the subroutine is called, which is probably based on user input, code execution time, and a lot of other factors.

 

Anyway, I'm going to stick with the shift/xor code for now. It produces good results and does not use the VERY SLOW mpy and div instructions. It could also easily be added to Adam's entropy method for some added randomness as the expense of not having the same order of numbers based on the seed value (which can be very handy for testing and troubleshooting.)

 

I'll be interested to see how my routine does with the "coin toss"... it will likely require a very large sample size (tens of thousands of flips) to flatten the data curve out. If you roll dice in the real world, you see patterns like that.

 

I just KNEW you'd bring up the DIV and MPY slowness argument... As I said, different uses for random numbers. For filling a screen with pixels, the XOR/Shift technique with a logical progression is very good because it will eventually hit every value. That means you could use it to do a screen "wipe" effect in bitmap... For my purposes, the randomness needed to be very random like rolling a die, and fortunately I don't need it too fast.

 

For the record, in my CRPG I actually use the VDP counter even/odd state for a lot of quickly needed "true/false" decisions, or even for direction determination. No need to call an expensive subroutine when just a MOV/ANDI will do in a pitch.

 

Adamantyr

[matthew180]

I just KNEW you'd bring up the DIV and MPY slowness argument...

 

I'm very predictable. I'm a speed freak, what can I say, I always pay attention to that stuff. That does not mean I don't use div, sometimes you can't get what you need any other way, but I cringe every time I write it.

 

For the record, in my CRPG I actually use the VDP counter even/odd state for a lot of quickly needed "true/false" decisions, or even for direction determination. No need to call an expensive subroutine when just a MOV/ANDI will do in a pitch.

 

Yeah, for that stuff it is great. But for something like maze generation, it sucks. The maze *always* turns at each point where a direction needs to be chosen. I always wondered why my TI mazes were so "bent". Now I know and I can fix it. :-)

 

Matthew

[Airshack]

Reading this thread eight years after it first appeared and trying to draw some conclusions....

 

Here’s what I’ve picked out:

 

 

Method1 - This is the random number generation code from Tombstone City:

 

RAND16 EQU >83C0

.

.

.

LI R4,28645

MPY @RAND16,R4

AI R5,31417

MOV R5,@RAND16

 

Pro: It came from TI and served Matthew well for 25+ years.

 

Con: This tombstone code has the non random feature of producing an odd number, then even, then odd, then even, etc. Also, no number will be repeated until all 65536 numbers of the 16-bit value have been used. The even,odd,even repeating part makes this method unacceptable.

 

 

Matthew then talks a little about prime numbers but that turns out to be a dead end.

 

 

Method2 - Adamantyr posted a variation that he uses in his code that mixes up the bits depending on the current "tick" (a counter that is incremented every VSYNC), and this helps scramble things up and at the very least gets rid of the odd, even, odd nature of the original.

 

LI R4,23729

MPY @>83C0,R4

AI R5,31871

MOV @CLOCK,R0

ANDI R0,>000F

SRC R5,0

MOV R5,@>83C0

 

Pro: Seems like Adamantyr method of shifting based on the VSYNC is a good means of entropy, especially when coupled with the fact that games are highly driven by user input, so there will be variation of when functions get called based on human input. Removes the characteristic of not reusing a number until all of the values have been used.

 

Con: MPY makes this method slow which violates matthew’s prime directive. MPY is a real cycle sucker. There’s got to be a better way!

 

 

Method3 - Tursi’s Dreamcast Days Book of Graphic Gems leads to...

 

RAND16 EQU >83C0

MASK DATA >B400

.

.

MOV @RAND16,R0 * Seed -> r0, seed must not be 0

SRL R0,1 * Shift r0 1 bit to the right, carry goes to C bit in status register

JNC. NOCARR. * If carry was not set, jump to label no-carry

XOR @MASK,R0. * calculate new random number with 0xb400 as mask

NOCARR MOV R0,@RAND16

 

Pro: It's fast and relatively random. Iit's non-repeating over the entire range. For whatever range you select (8 bits, 16 bits, 32 bits), each value is guaranteed to be selected exactly once. This makes it nice for pixel dissolves. What makes this algorithm special is that if it is called 2^16 times, then the rand variable will traverse all 2^16 (65535) different values (except 0) exactly 1 time, but in a pseudo random order. And this is all done with just one shift, one xor and one conditional jump. Personally I use this algorithm to make dissolve effects.

 

Con: It's not the best for being RANDOM, too many things are predictable, but it has worked quite well for me for a number of years. No number will be repeated until all 65536 numbers of the 16-bit value had been used.

 

***** THIS APPEARS TO BE A GOOD NON-REPEATING ROUTINE.

 

 

Matt’s Conclusions: I'm going to stick with the shift/xor (Tursi method 3) code for now. It produces good results and does not use the VERY SLOW mpy and div instructions. It could also easily be added to Adam's entropy method for some added randomness as the expense of not having the same order of numbers based on the seed value (which can be very handy for testing and troubleshooting.)

 

Also note that the shift/xor subroutine can be easily expanded to 32 or even 64 bit numbers, which would help make a larger list of numbers, but other than that it still has the same characteristics.

 

 

Question: Have any of you out there given thought to quick and dirty routines for both repeating and non-repeating random number generators? Surely you have! Please post what you use and why.

 

 

Note: Tursi also added a routine helpful for adding entropy using The TMS9901’s 14-bit timer:

 

Tursi say -

 

 

While trying out Matthew's example, I realized that if we aren't running interrupts (as we discussed in the other thread), and we don't manually run a vertical blank routine, we won't have a continuously changing counter to use. But then I thought about the 9901. There's a 14-bit timer in there that ticks at roughly 46.785kHz, independent of the rest of the system. Not very much TI software uses it (indeed, I only learned how to from Karsten's Sudoku). Setting that up to count continuously, and reading the value as needed, may provide a nice injection of unpredictability, too. If you stopped for user input a lot, you could pretty much consider the number totally random, but otherwise, I thought it might be nice to use as the shift counter in Matthew's code. The timer loops every 349.2 milliseconds if set to maximum range, so for anything where accessing it is not fully deterministic timewise, you could almost use it raw. If you set it for a smaller value like 255 (or just mask), where it would wrap every 5ms and for code that interacts with the user between reads, would appear pretty darn random.

 

Not 100% sure on this, but using it would be something like this (based on Thierry's code):

 

INIT01 CLR R12 CRU base of the TMS9901

SBO 0 Enter timer mode

LI R1,>3FFF Maximum value

INCT R12 Address of bit 1

LDCR R1,14 Load value

DECT R12 There is a faster way (see below) (Tursi - I didn't follow the faster way, unless it's LDCR for all 15 bits)

SBZ 0 Exit clock mode, start decrementer

B *R11 Return to caller

 

If you BL @INIT01, then, the timer will start running through it's maximum range continuously. To get the value, you just need to do this:

 

READ01 CLR R12 CRU base of the TMS9901 again

SBO 0 Enter timer mode

STCR R0,15 Read current value (plus mode bit)

SRL R0,1 Get rid of mode bit

SBZ 0 Exit clock mode, decrementer continues

B *R11 Return - 14-bit counter value is in R0

 

So the BL @READ01 should return the current value of the counter into R0. Theirry's page says it doesn't halt the counter to read it, and since we didn't reset it, it should keep counting.

 

Maybe an extra little bit of randomness, anyway!

 

(edit) I've tested this code now, and it appears to work in Classic99 at least.

[+Lee Stewart]

The “random number generation” topic has come up several times here. A couple of other places are

• http://atariage.com/forums/topic/162941-assembly-on-the-994a/page-27?do=findComment&comment=3935928
• http://atariage.com/forums/topic/274403-rnd-and-rand-pseudorandom-number-generation-by-ti-basic/

The method you listed as “Method 1” was taken a step further by TI programmers in TI Forth (fbForth is the same) by doing a circular right shift of 5 bits before storing the new seed in >83C0.

 

...lee

[+adamantyr]

I still take issue with "Oh, MPY is so slow..." It's all about context.

 

If you have ten enemy units on the screen and you're just determining a random direction for each, that's only 10 calls. Whether you use MPY or not isn't going to make a huge difference. If you are trying to fill the screen with pixels randomly it's a whole heck of a lot more, and you are also interacting with video so you definitely want something faster. And in that case, deterministic is good too; you know after you've processed through all 65535 combinations that every pixel should be filled.

 

Use the technique that best fits what you need the random values for.

[Tursi]

Pre-generated tables work in a lot of cases too.

[+TheBF]

Not 100% sure on this, but using it would be something like this (based on Thierry's code):

 

INIT01 LIMI 0           * NEED THIS?
​       CLR  R12         CRU base of the TMS9901 
       SBO  0           Enter timer mode 
       LI   R1,>3FFF    Maximum value
       INCT R12         Address of bit 1 
       LDCR R1,14       Load value 
       DECT R12         There is a faster way (see below) (Tursi - I didn't follow the faster way, unless it's LDCR for all 15 bits)
       SBZ  0           Exit clock mode, start decrementer 
       LIMI 2           * AND THIS?
       B    *R11        Return to caller

So the BL @READ01 should return the current value of the counter into R0. Theirry's page says it doesn't halt the counter to read it, and since we didn't reset it, it should keep counting.

 

Maybe an extra little bit of randomness, anyway!

 

(edit) I've tested this code now, and it appears to work in Classic99 at least.

 

 

I use these timer routines in CAMEL99 Forth for milli-second delays and I need to have Interrupts disabled for INIT01 or it's unstable.

 

The timer read routine seems OK with interrupts on. EDIT: Wrong! Needs interrupts off as well.

 

Of course if you are running with interrupts off all the time for a game no matter.

Edited February 1, 2018 by TheBF

[RXB]

Pre-generated tables work in a lot of cases too.

I wonder if a GPL CALL IO to that CRU address counter would be better for RND in XB GPL?

 

I mean would be much less code used then the current one I am using in RXB.

Edited February 1, 2018 by RXB

[Airshack]

So Lee, this is what fbForth uses?

 

 

RAND16 EQU >83C0

.

.

.

LI R4,28645

MPY @RAND16,R4

AI R5,31417

SRC R5, 5

MOV R5,@RAND16

 

A minor edit of the Tombstone (Method1) routine? This must remove the odd,even,odd nature then.

[+Lee Stewart]

That is correct.

 

...lee

[marc.hull]

If you want real random numbers in your games then introduce some real world influences. The equation will always be the same but if you can influence the seed in a non repeatable fashion then it's as good as random for all intents.

 

IE doesn't matter what the algorythm is provided the seed is not predictable.