Jump to content
IGNORED

Random number in assembly


Vorticon

Recommended Posts

Hi.

I need to generate random numbers between 1 and 6 for Ultimate Planet, and it struck me that I don't know how to do that with assembly! Could someone here be kind enough to point me in the right direction?

 

There was a lively thread on some different methods here:

http://www.atariage.com/forums/topic/163646-not-prime/page__p__2020334__hl__primes__fromsearch__1#entry2020334

 

Sparked by the idea that primes would be needed for a pseudo-random system.

 

Adamantyr

Link to comment
Share on other sites

Thanks :) While I really don't understand the math behind your RND routine (I have to research this a bit), I do understand its structure. One question though: what address is @CLOCK referencing? Is it the screen time-out counter >83D6? Also, the EA manual mentions address >8378 in the CPU RAM PAD area as being the random number generator. What is this used for? Here's your routine for reference:

 

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

Link to comment
Share on other sites

Thanks :) While I really don't understand the math behind your RND routine (I have to research this a bit), I do understand its structure. One question though: what address is @CLOCK referencing? Is it the screen time-out counter >83D6? Also, the EA manual mentions address >8378 in the CPU RAM PAD area as being the random number generator. What is this used for? Here's your routine for reference:

 

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

 

@CLOCK is just a 16-bit value incremented in the ISR, so it ticks every 1/60 of a second. You can use the VDP interrupt timer byte (>8379) for a similar function, which is to generate a random shift. Just replace that line with MOV @>8378,R0 and it will function the same.

 

>8378 a random value storage for BASIC and Extended BASIC, I believe. Can someone else confirm this?

 

Adamantyr

Link to comment
Share on other sites

 

 

@CLOCK is just a 16-bit value incremented in the ISR, so it ticks every 1/60 of a second. You can use the VDP interrupt timer byte (>8379) for a similar function, which is to generate a random shift. Just replace that line with MOV @>8378,R0 and it will function the same.

 

>8378 a random value storage for BASIC and Extended BASIC, I believe. Can someone else confirm this?

 

Adamantyr

What is the actual address @CLOCK is pointing to?

Link to comment
Share on other sites

 

 

@CLOCK is just a 16-bit value incremented in the ISR, so it ticks every 1/60 of a second. You can use the VDP interrupt timer byte (>8379) for a similar function, which is to generate a random shift. Just replace that line with MOV @>8378,R0 and it will function the same.

 

>8378 a random value storage for BASIC and Extended BASIC, I believe. Can someone else confirm this?

 

Adamantyr

What is the actual address @CLOCK is pointing to?

 

It's a memory variable, nothing more. I use it for a variety of purposes in my CRPG for timing.

 

Adamantyr

Link to comment
Share on other sites

 

 

@CLOCK is just a 16-bit value incremented in the ISR, so it ticks every 1/60 of a second. You can use the VDP interrupt timer byte (>8379) for a similar function, which is to generate a random shift. Just replace that line with MOV @>8378,R0 and it will function the same.

 

>8378 a random value storage for BASIC and Extended BASIC, I believe. Can someone else confirm this?

 

Adamantyr

What is the actual address @CLOCK is pointing to?

 

It's a memory variable, nothing more. I use it for a variety of purposes in my CRPG for timing.

 

Adamantyr

I see. I guess I'll use the VDP interrupt timer then. Thanks :) Oh and one more thing: is there a more efficient way to restrict the numbers generated to a certain range of values other than doing straight comparisons?

Edited by Vorticon
Link to comment
Share on other sites

I see. I guess I'll use the VDP interrupt timer then. Thanks :) Oh and one more thing: is there a more efficient way to restrict the numbers generated to a certain range of values other than doing straight comparisons?

 

Yes, you can use division to reduce the random value to something within a specific range, as follows:

 

* R3 = maximum range desired, R5 = random value from 0-65535
      INC  R3
      CLR  R4
      DIV  R3,R4
* R5 now contains a value from 0 to max - 1

 

Adamantyr

Link to comment
Share on other sites

If you need more performance than DIV gives, consider restricting your random number range to a power of two (ie: instead of 1-6, try to use 0-7). Then all you need is a bitmask, ANDI R5,>0003 will reduce R5 to a range of 0-7 without introducing the bias that a modulo operation does. (Modulo makes certain numbers more likely than others. It's usually not noticable in a game, but it's there. You wouldn't use it for gambling real money, for instance! ;) )

Link to comment
Share on other sites

If you need more performance than DIV gives, consider restricting your random number range to a power of two (ie: instead of 1-6, try to use 0-7). Then all you need is a bitmask, ANDI R5,>0003 will reduce R5 to a range of 0-7 without introducing the bias that a modulo operation does. (Modulo makes certain numbers more likely than others. It's usually not noticable in a game, but it's there. You wouldn't use it for gambling real money, for instance! ;) )

Easy enough to implement :) I can always ignore values of 0 or 7... Out of curiosity, why would modulo operations make certain numbers more likely than others?

On the other hand, adamtyr's method obviates the need to do compare instructions, especially when the range is not a power of 2, as long as the skewing effect is not too pronounced.

Edited by Vorticon
Link to comment
Share on other sites

If you need more performance than DIV gives, consider restricting your random number range to a power of two (ie: instead of 1-6, try to use 0-7). Then all you need is a bitmask, ANDI R5,>0003 will reduce R5 to a range of 0-7 without introducing the bias that a modulo operation does. (Modulo makes certain numbers more likely than others. It's usually not noticable in a game, but it's there. You wouldn't use it for gambling real money, for instance! ;) )

Easy enough to implement :) I can always ignore values of 0 or 7... Out of curiosity, why would modulo operations make certain numbers more likely than others?

On the other hand, adamtyr's method obviates the need to do compare instructions, especially when the range is not a power of 2, as long as the skewing effect is not too pronounced.

 

Yeah, if you add the compare instructions, you might as well use DIV, it'll be faster in most cases.

 

The bias I only learned about recently, when a friend of mine started an encryption job, and it was one of his interview questions. The reason makes total sense, but I'd never thought about it before.

 

For sake of simplicity (and human understanding rather than code), let's say the random number generator gives you a perfectly random number from 0-9. But as in your case, you want a number from 0-5.

 

If you use modulo, certain numbers are now more likely to come up than others. You would do val%6, and get this result table:

 

0 % 6 = 0

1 % 6 = 1

2 % 6 = 2

3 % 6 = 3

4 % 6 = 4

5 % 6 = 5

6 % 6 = 0

7 % 6 = 1

8 % 6 = 2

9 % 6 = 3

 

Note that this sequence makes the numbers 0-3 more likely to come up than the numbers 4-5, because there are two sets of them in the output range! The easiest solution is to use the random number as a percentage or fraction, instead of masking. So instead of saying x % 6, you would use x * 6 / 10. Unfortunately, for a small range like this, the end result is the same, two numbers still come up short! But the concept apparently balances out better with larger ranges. ;)

 

But if you can use the masking, it's generally better for speed if you can adapt your algorithm to use all the results than to compare and skip. If you can't, might as well just DIV! :)

Link to comment
Share on other sites

 

The bias I only learned about recently, when a friend of mine started an encryption job, and it was one of his interview questions. The reason makes total sense, but I'd never thought about it before.

 

For sake of simplicity (and human understanding rather than code), let's say the random number generator gives you a perfectly random number from 0-9. But as in your case, you want a number from 0-5.

 

If you use modulo, certain numbers are now more likely to come up than others. You would do val%6, and get this result table:

 

0 % 6 = 0

1 % 6 = 1

2 % 6 = 2

3 % 6 = 3

4 % 6 = 4

5 % 6 = 5

6 % 6 = 0

7 % 6 = 1

8 % 6 = 2

9 % 6 = 3

 

Note that this sequence makes the numbers 0-3 more likely to come up than the numbers 4-5, because there are two sets of them in the output range! The easiest solution is to use the random number as a percentage or fraction, instead of masking. So instead of saying x % 6, you would use x * 6 / 10. Unfortunately, for a small range like this, the end result is the same, two numbers still come up short! But the concept apparently balances out better with larger ranges. ;)

 

But if you can use the masking, it's generally better for speed if you can adapt your algorithm to use all the results than to compare and skip. If you can't, might as well just DIV! :)

Fascinating... As you said, it's simple, but one would have to look at it in detail to notice. Thanks for the explanation. I'm afraid I'm going to have to stick with DIV though because Ultimate Planet is based on a classic table top 1980 wargame, and all the combat resolution tables use a 6-sided dice. I worry that I may unbalance the game if I expand the tables arbitrarily... Here are a few screen shots of the original game for the curious:

http://laurent36.typepad.com/.a/6a013486df16fc970c0133f3bd044c970b-pi

http://laurent36.typepad.com/.a/6a013486df16fc970c0133f3bd0471970b-pi

http://laurent36.typepad.com/.a/6a013486df16fc970c0133f3bd0492970b-pi

Link to comment
Share on other sites

Yeah, if you add the compare instructions, you might as well use DIV, it'll be faster in most cases.

 

The bias I only learned about recently, when a friend of mine started an encryption job, and it was one of his interview questions. The reason makes total sense, but I'd never thought about it before.

 

For sake of simplicity (and human understanding rather than code), let's say the random number generator gives you a perfectly random number from 0-9. But as in your case, you want a number from 0-5.

 

If you use modulo, certain numbers are now more likely to come up than others. You would do val%6, and get this result table:

 

0 % 6 = 0

1 % 6 = 1

2 % 6 = 2

3 % 6 = 3

4 % 6 = 4

5 % 6 = 5

6 % 6 = 0

7 % 6 = 1

8 % 6 = 2

9 % 6 = 3

 

Note that this sequence makes the numbers 0-3 more likely to come up than the numbers 4-5, because there are two sets of them in the output range! The easiest solution is to use the random number as a percentage or fraction, instead of masking. So instead of saying x % 6, you would use x * 6 / 10. Unfortunately, for a small range like this, the end result is the same, two numbers still come up short! But the concept apparently balances out better with larger ranges. ;)

 

But if you can use the masking, it's generally better for speed if you can adapt your algorithm to use all the results than to compare and skip. If you can't, might as well just DIV! :)

 

True, but your example also uses a small random range. With a full 16-bit range, your increase of certain value results will be so small as to be statistically insignificant. That being said, it's ALWAYS better to use base 2 values in assembly language, because you can avoid the problem entirely by just using bit masks to get the number you want.

 

My particular random number generator is best used for real-time randomness, like rolling dice. Something you do in a program that replicates what a human user does. If I wanted to randomly fill the screen with pixels, I would NOT use this method, I'd do something like your XOR routine which would not use division and would actually cycle through all given values given enough permutations.

 

Adamantyr

Link to comment
Share on other sites

True, but your example also uses a small random range. With a full 16-bit range, your increase of certain value results will be so small as to be statistically insignificant. That being said, it's ALWAYS better to use base 2 values in assembly language, because you can avoid the problem entirely by just using bit masks to get the number you want.

 

My example uses a small range so that it's possible to explain the concept. Larger ranges have problems, too, and how signigicant it is depends on the range of the numbers you are generating and the purpose you are generating them for. You can't just generically say "it's insignificant", that doesn't cover all the cases.

 

At any rate, I was just demonstrating a concept, not saying it was significant in this case.

Link to comment
Share on other sites

Using a mask and re-randomizing if unwanted nubers are returned will provide well distributed numbers. I'd start with that and change it out only if performance becomes an issue.

 

That's a good idea I hadn't thought of! But the 9900 has hardware divide with modulo, and because of the poor memory architecture of the machine, instruction count is frequently more important to performance than per-instruction cycles. The tests to decide whether you need to re-generate the number again will be more expensive than the very slow DIV instruction, so if you can't use powers of two, it's often better to DIV. We have a huge heated thread here on why that is where I went through the various cycle counts. ;)

Link to comment
Share on other sites

Using a mask and re-randomizing if unwanted nubers are returned will provide well distributed numbers. I'd start with that and change it out only if performance becomes an issue.

Unfortunately I will then still have to do comparision instructions...

 

BTW, I had no idea you could display pictures on a VCS machine! Looks like a great program, especially on that limited platform. I recently programmed a full casino blackjack program for 5 players (4 computer controlled) for the TRS80 Model IV in Turbo Pascal, and it was a b*** to design, so I am impressed at what people can still pull off with the VCS...

Link to comment
Share on other sites

That's a good idea I hadn't thought of! But the 9900 has hardware divide with modulo, and because of the poor memory architecture of the machine, instruction count is frequently more important to performance than per-instruction cycles.

Thanks for taking the time to explain. My answer was certainly colored by my 6502 assembly work, where non-power of 2 division is painful and comparisons are relatively cheap. :)

 

 

BTW, I had no idea you could display pictures on a VCS machine! Looks like a great program, especially on that limited platform. I recently programmed a full casino blackjack program for 5 players (4 computer controlled) for the TRS80 Model IV in Turbo Pascal, and it was a b*** to design, so I am impressed at what people can still pull off with the VCS...

Thanks! For a game thats simple to play, blackjack is deceptively complicated to implement. While I'm glad I took it on, I'm equally glad there's no more work to do. :)

 

While we're off-topic... The TI isn't a system of my youth, but I've greatly enjoyed following the exploits of yourself, Tursi, and all of the TI-99'ers. Somehow you guys have been blessed with a lack of ego and an abundance of creativity! :thumbsup:

Link to comment
Share on other sites

 

 

@CLOCK is just a 16-bit value incremented in the ISR, so it ticks every 1/60 of a second. You can use the VDP interrupt timer byte (>8379) for a similar function, which is to generate a random shift. Just replace that line with MOV @>8378,R0 and it will function the same.

 

>8378 a random value storage for BASIC and Extended BASIC, I believe. Can someone else confirm this?

 

Adamantyr

What is the actual address @CLOCK is pointing to?

 

It's a memory variable, nothing more. I use it for a variety of purposes in my CRPG for timing.

 

Adamantyr

I see. I guess I'll use the VDP interrupt timer then. Thanks :) Oh and one more thing: is there a more efficient way to restrict the numbers generated to a certain range of values other than doing straight comparisons?

 

 

 

 

Hey Walid....

 

 

Some thoughts.

 

 

Using the VDP screen count out timer(if that is your plan) can skew your result by itself as it is always an even number or always an odd number. The decrementer in the ISR removes two at a time so you will always have either odd numbers or even numbers in your seed. You have to massage the data before you take the remainder. A suggestion would be to have your own incrementer based on game cycles that can be added to the screen timer to solve the odd/even dilemma. That would at least insure a chance of a full distribution without complicating the matter too much.

 

As far as introducing some randomness with little headache, I have found that having an incrementer that is polled when the user presses a key is about as random an event as one could get on the TI. While waiting for a key press, one could increment a location (letting it wrap) and add it to your seed when a legal keypress is made. Since it is unlikely that a user will press a key at the same given time each turn then there is an element of uncertainty introduced as well as a 33/66 percent chance of an odd/even number. Added to the screen counter that solves two odd/even problem and introduces a bit more randomness to the seed.

 

Using the 9901 timer removes the whole odd/even problem. There is an example of using the timer on Theirry's site.

Edited by marc.hull
Link to comment
Share on other sites

Seed

 

ref.: Wikipedia

A random seed (or seed state, or just seed) is a number (or vector) used to initialize a pseudorandom number generator.

 

Tursi once told me a good seed in a game would come from the time between a (game) title screen and the user (gamer) pressing a key. This seems to be a very good idea.

 

To avoid the situation where the user is already holding the key, when the title screen appears, start checking for that key in the up position (not pressed), when this is true, continue to checking for the key in the down position (key pressed).

 

One thing I have not been able to test (have no hardware - emulation only), is whether you can actually check the keyboard (perform CRU operations on the keyboard) this fast and have correct values returned (doing nothing but incrementing a value and checking the key in a loop). What makes me sceptical is the delay in the TI-99/4A ROM keyboard scanning routine(s).

 

Time delay
0498 020C LI 12,>04E2 Loop counter
049A 04E2
049C 060C DEC 12
049E 16FE JNE >049C
04A0 045B B *11

I'm not sure whether the above was included because of keyboard bouncing or voltage having to settle (in keyboard wires), but it must be there for a reason.

 

ref.: Wikipedia

When pressing a keyboard key, the key contacts "bounce" against each other several times for several milliseconds before they settle into firm contact (although this was not true with early "solid-state" keyswitch keyboards that used Hall-effect, inductive, or capacitive keyswitch technologies). When released, they bounce some more until they revert to the uncontacted state. If the computer were watching for each pulse, it would see many keystrokes for what the user thought was just one. To resolve this problem, the processor in a keyboard (or computer) "debounces" the keystrokes, by aggregating them across time to produce one "confirmed" keystroke that (usually) corresponds to what is typically a solid contact.

 

One way to check it may be to change the background color to let the user know we're going into a keyboard loop, count and read the key state continuously and only store the changes, once the count reaches a certain value the loop is aborted and the changes can be examined. The user should only press and release the key once. The table with changes should, hopefully, only contain 2 changes (the press and the release).

 

Range

 

I like the simple and cool DIV solution presented in post #9, and being aware of the bias, which Tursi explains nicely in post #12.

 

I tried to have DIV return the desired range as a result instead of the remainder, but still some bias in the top of range. I guess there's no advantage there. The quickie below might even be influenced by XB and floating point, but for now I trust the distribution (from the algorithm/method).

 

random1.png

 

Note, divisor (10923) is integer to be comparable with assembler.

 

:)

Edited by sometimes99er
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...