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
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
sub             eax,edx           ; mod (2^32)+1
----------------
imul            eax,edx

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

 Page 1 of 1 [ 10 post ]

Relevant Pages