Pseudo Random Number Generator. 4liner 68000.

[SoLo2]

Copyright(c)2004-2011 by Herman Samso J..
All Rights Reserved.
HSJ-RNG-20040204.txt

First test at a RNG with a Motorola
MC68000 processor.
First try was to code the Lewis, Goodman
and Miller algorithm from 1969, but then
realized that a long division opcode was
necessary, and MC68000 can only divide
by words.

So I gave up, and tried desperately with
a 32bit long dividend described in above
mentioned algorithm and a 16 bit number
as divisor, I chose 65533 that is nearly
the whole of 16bits.

The algorithm here described is probably
not too much random, and hasn't yet been
studied or benchmarked.

Anyways I found the results good enough
to be included in my last "retro scene
demo intro" for Atari ST. So, I have
decided to include it here, and maybe
get some advises or proofs.

The code I present here is in assembler
and can be easily compiled. It is only
4 instructions long!

It bases on the machine code of the
MC68000 which delivers remainder in the
high word, quotient in the low word of
a long word as result of an unsigned
division.
The only step inbetween is to rotate
this results around in the long word
by a fixed amount. I chose 8 bits,
but maybe 7 or 23 are also good values.


Greetings,
SOLO (BITS)

Code: Select all

# Copyright(c)2004-2011 by Herman Samso J..
# SoLo (BITS).
# http://thebitsclub.tripod.com
# All Rights Reserved.
# RND1.s
# An easy way ?

RND1
        move.l  Dend,d0
        divu    dsor,d0
        ror.l   #8,d0
        move.l  d0,Dend

Dend
        dc.l    2147483647 ;dividend
dsor
        dc.w    65533      ;divisor

[ggn]

If you're going for real-time performance you might want to eradicate that divu.

The random routine I use in my programs is this (5 instructions ) :

rand: move.l randseed,d1
ror.l #8,d1
sub.w $466.w,d1
add.b $ff8209.w,d1
move.l d1,randseed

By using the vsync counter and the low byte of the video counter you get some pretty good random numbers (I think!)

Of course, this routine is hardware dependent, but who cares?

George

[SoLo2]

Looks good involving those two
revolving registers for the random.
Will have to try your routine, as it
seems that mine can degenerate
for some seeds.

Also I use the whole 520KB low
memory of the Atari to create a
random seed by "eor"ing all that
memory.

SoLo2

[gwEm]

why not just take the number of seconds in the RTC as a seed, faster and totally random as you dont know when you'll be running the program. this seems the typical method after looking into other peoples routs.

[simonsunnyboy]

Not all STs have the RTC. I don't know if it bombs when you try to access the RTC on a machine without.

[gwEm]

is that right? i thought at least the IKBD clock was active on all systems.... infact i thought IKBD was functionally the same on all systems.

in anycase you could also take the 200hz or vbl counter a seed.

[simonsunnyboy]

IKBD != RTC

The IKBD clock is loaded from the RTC, if available. IKBD is ofcourse available on any ST but it is not the RTC.

[gwEm]

ah yeah, but thats not really the point i was trying to make which was theres easier ways to get a seed than eoring the whole of low memory.

[thothy]

Not all STs have the RTC. I don't know if it bombs when you try to access the RTC on a machine without.

FYI: No bombs when accessing the RTC memory space on a ST without RTC (at least not on my ST).

[NiceGuyUK]

Stupid ill-informed reply part 1 :-

Isn't there a trap to get a random number?

Code: Select all

move.w #17,-(sp)
trap #14
addq.l #2,sp

or am I being horribly naive?

[simonsunnyboy]

This trap is very slow - like all OS calls. It wastes a lot of cycles just for saving and restoring registers, in a fast demo or game you'll probably want to use that time for other things.

[Nyh]

Stupid ill-informed reply part 1 :-

Isn't there a trap to get a random number?

Code: Select all

move.w #17,-(sp)
trap #14
addq.l #2,sp

or am I being horribly naive?

The trap is slow and not always available. A real demo or game coder will not use the OS for getting a random value.

Reading the lowbyte is usable for getting a random seed buy it always is even and the numbers 0, 32, 64, 96, 128, 160, 192 and 224 are very likely to occour (with 0 the most likely).

Xorring a part of the low memory might be a fine idea if the OS is still up (but then, why not using the OS).

You can use a user action to generate a random seed:

Code: Select all

addq.w #1,d0
cmp.b #57,$FFFFFC02.w,D0
bne.s loop

A good 32 bit random number generator is:
seed=seed*1664525+1013904223
Doing the long multiply in assembly is left as an excercise to the reader...

Nyh

[ggn]

Holy crap, I realised I answered to that thread over a year ago I completely forgot about it!

Anyway, anyone has a different small rout for generating random numbers?

Regards, George

[Nyh]

Anyway, anyone has a different small rout for generating random numbers?

Well, you could use a 32 bit Maximal-Length LFSR:

Code: Select all

random:
     move.l  seed(PC),D0
     btst    #1,D0
     sne     D1
     btst    #5,D0
     sne     D2
     eor.b   D2,D1
     btst    #6,D0
     sne     D2
     eor.b   D2,D1
     btst    #31,D0
     sne     D2
     eor.b   D2,D1
     add.b   D1,D1
     addx.l  D0,D0
     move.l  D0,seed
     rts
seed:
     DC.L 1

It has a period of 2^32 -1. Works great but make sure the seed is not 0!

If you need some random bits fast you could use:

Code: Select all

random8:
     move.b  seed(PC),D0
     mulu    #221,D0
     add.b   #53,D0
     move.b  D0,seed
     rts
seed:
     DC.B 1

I found this one on the net. period 2^32:

Code: Select all

random32:
     move.l  seed(PC),D0
     add.l   D0,D0
     bcc.s   done
     eori.b  #$AF,D0
done:
     move.l  D0,seed
     rts
seed:
     DC.L $12345678
     END

Nyh

[tobe]

This one gives very good random numbers :

http://www.flipcode.com/archives/07-15-2002.shtml

Code: Select all

    lea     .rand(pc),a0
    lea     4(a0),a1

...

Code: Select all

    move.l  (a0),d0  ; AB
    move.l  (a1),d1  ; CD
    swap    d1       ; DC
    add.l   d1,(a0)  ; AB + DC
    add.l   d0,(a1)  ; CD + AB

...

Code: Select all

.rand:      dc.l    $3E50B28C
            dc.l    $D461A7F9

Of course the seed is just an example, but its entropy is quit good.
You can get ride of a1 by using post-increment and pre-decrement on a0.

PS: if you want to test your random generator... listen it

[tobe]

or, if you just want to fill a buffer with random numbers :

Code: Select all

    lea     buffer,a0
    move.l  #$3E50B28C,d1
    move.l  #$D461A7F9,d2
    move.w  #LENGTH-1,d0
.random:
    move.l  d2,d3
    swap    d3
    add.l   d1,d2
    add.l   d3,d1
    move.w  d3,(a0)+     ; move.b, move.w or move.l
    dbra.w  d0,.random

[Dal]

Surely a nice random seed would be to display a "Press any key to continue" message then base your seed on key pressed and number of clock cycles it took the user to react?

I guess you just need to make sure you ignore anything already in the buffer so as to avoid somebody hitting a key before the message and thus giving a predictable result.

[simonsunnyboy]

The actual key is probably not even needed. Just taking the time it took for the loop or even simply increment a counter while waiting for the keypress.

[tobe]

If you want to avoid bad seeds, you can use a hardcoded one (that gives good numbers) and just pop random numbers in a loop while waiting for a keypress.

[defjam]

rand_func:
move.l #$12345678,d0
addq.l #5,d0
rol.l d0,d0
move.l d0,rand_func+2
rts

[Nyh]

rand_func:
move.l #$12345678,d0
addq.l #5,d0
rol.l d0,d0
move.l d0,rand_func+2
rts

Cool!

Hans Wessels

[simonsunnyboy]

rand_func:
move.l #$12345678,d0
addq.l #5,d0
rol.l d0,d0
move.l d0,rand_func+2
rts

Hehe, selfmodifying code xD
How does a Falcon with 030 eat that?