Random ? 
Author Message
 Random ?

Would someone know how to simulate a RANDOM function in asm ?


Mon, 09 Jul 2001 03:00:00 GMT  
 Random ?


Quote:
>Would someone know how to simulate a RANDOM function in asm ?

 Try Rand(n+1) = (((Rand(n) * 1447) + 1523) mod 1601)
 [those are 3 prime numbers -- if you want bigger values,
 look up or calculate bigger primes].  

 Try something like what follows, I haven't assembled or run it:

.data
RVal   dd  0
.code
Rand:  mov eax,[RVal]
       mov ebx,1447
       mov ecx,1523
       mov esi,1601
       mul eax,ebx
       add eax,ecx
       mon edx,0
       div eax,esi
       mov [RVal],eax
       retn

--




Mon, 09 Jul 2001 03:00:00 GMT  
 Random ?
I'm sorry, I'm still new to assembler.  I thought your answer was pretty
enlightening, but what does "mon" do?

Leron

Quote:
>       mon edx,0
>       div eax,esi
>       mov [RVal],eax
>       retn



Tue, 10 Jul 2001 03:00:00 GMT  
 Random ?
The choice of multipliers in linear congruential pseudo-random generators
is far more advanced than just "use a prime".  Knuth's volume 2,
Seminumerical
Algorithms, devotes a lot of pages to this.  Table 1 lists several
generators,
mostly good, but with one or two "bad" examples.  Borrow a copy,
use one of the good ones.

Also,    mod 1601,   even with an excellent multiplier will give a poor
pseudo-random stream because the modulus is WAY too low.

Note that many of the generators in Knuth's Table 1 have
moduli of (2^n)-1 or (2^n)+1.  For either of these cases
assembly implementation is trivial if n=word width.  For
a n-bit by n-bit multiplication, the high n bits of the 2n-bit
result are either added to or subtracted from the low n bits.
This kind of operation, while difficult to implement efficiently
in most HLLs, is trivial in assembly.

I would recommend choosing one of the table entries with
2^32  +/- 1.    Smaller moduli are asking for trouble.

Previous rand (or seed) in EAX
multiplier in EDX
offset (if any) in ECX
----------------
                imul            eax,edx
                add             eax,ecx
                sub             eax,edx           ; mod (2^32)+1
----------------
                imul            eax,edx
                add             eax,ecx
                add             eax,edx           ; mod (2^32)-1

result will smash EDX and leave new rand in EAX.   Note NO idiv's.
--
Kevin G. Rhoads, Ph.D. (Linearity is a convenient fiction.)




Tue, 10 Jul 2001 03:00:00 GMT  
 Random ?

Quote:



> >Would someone know how to simulate a RANDOM function in asm ?

>  Try Rand(n+1) = (((Rand(n) * 1447) + 1523) mod 1601)
>  [those are 3 prime numbers -- if you want bigger values,
>  look up or calculate bigger primes].

Not all combinations of primes work for these 'linear congruential
generators'.
This will repeat every 1601 calls, you may want to hunt a generator
with a longer cycle. (do a web-search for linear congruential random
number generator' perhaps?)

If you find the source code to the rand() C runtime library function
(and there are several on the net) then you can translate that to
assembly. Most are linear congruential. I know Borland (used to)
supply the source to their CRTL.

Also search for 'Linear Feedback Shift Register', which is a very
quick way of giving a single random bit.

Books:
- "Numerical Recipies" (in any language, the algorithms remain the
same, be it fortran, Pascal, c or c++)
- Surely sedgewick's "Algorithms" has got PRNG code in?

FatPhil

--
Phil Carmody
Not speaking for or on behalf of Nokia Telecommunications.

"At the showing of blue movies at Scotland Yard I take the precaution
of
removing my glasses, which reduces the whole messy business to an
impressionist blur." John Mortimer, QC, 1978



Tue, 10 Jul 2001 03:00:00 GMT  
 Random ?
Thanks a lot everybody.


Tue, 10 Jul 2001 03:00:00 GMT  
 Random ?

Quote:




> > >Would someone know how to simulate a RANDOM function in asm ?

> >  Try Rand(n+1) = (((Rand(n) * 1447) + 1523) mod 1601)
> >  [those are 3 prime numbers -- if you want bigger values,
> >  look up or calculate bigger primes].

> Not all combinations of primes work for these 'linear congruential
> generators'.
> This will repeat every 1601 calls, you may want to hunt a generator
> with a longer cycle. (do a web-search for linear congruential random
> number generator' perhaps?)

<cogent remarks snipped for brevity>

Quote:
> Books:
> - "Numerical Recipies" (in any language, the algorithms remain the
> same, be it fortran, pascal, c or c++)
> - Surely sedgewick's "Algorithms" has got PRNG code in?

> FatPhil

> --
> Phil Carmody

And, of course, the classic: Knuth, D. E. _The Art of Computer
Programming_
Vol. 2:  _Semi-numerical Algorithms_.

Includes Assembly language source code (for a non-existant but easy to
understand machine).

Al Moore



Tue, 10 Jul 2001 03:00:00 GMT  
 
 [ 10 post ] 

 Relevant Pages 

1. random rant on random files

2. A truly random $random??

3. ? generating random uniform and binomial random deviates for BIG integers

4. Unit tests and random.Random()

5. Random number not random?

6. random behavior in random module?

7. Random Number Generator to produce SAME random number from 12:00am-11:59pm

8. Opening random line from file with random.shuffle()

9. Random Value

10. J random-number generator: what is used?

11. Quasi Random numbers

12. Instructions for testing the COM Random Stream Sample

 

 
Powered by phpBB® Forum Software