random number generation (in asm)

[meynaf]

I've had a discussion with Thorham on that subject. My way is time counter reading (date/time, cia registers, and beam counter), with some computation on this (including the previous emitted random value).

What, according to people here, is the best method for that ?

[Leffmann]

The perfect PRNG that doesn't stall nor generates identical series on successive runs is probably a lot more complicated (and IMO unnecessary for anything in an Amiga context) than you'd think.

I would just settle for a simple algorithm with a fixed initial state in order to get a predetermined series which I know is good, and use some input such as mouse position counters or TOD clock to determine a starting offset in the series.

Seed    move.l  #$9876fedc, d0
        move.l  #$abcd1234, d1
        move.w  JOY0DAT, d2
.loop   swap    d0
        add.l   d1, d0
        add.l   d0, d1
        dbf     d2, .loop
        movem.l d0-d1, PRNG.state
        rts

PRNG    movem.l .state(pc), d0-d1
        swap    d0
        add.l   d1, d0
        add.l   d0, d1
        movem.l d0-d1, .state
        rts

.state  ds.l    2

[SyX]

The Leffmann's solution is pretty, simple and fast and how he said set the seed in function of the player input or any random action.

Other option is using a Xorshift PRNG, they are very easy to convert to 68000 (a few EORs and ASL/R) and if you only need numbers of 8 or 16 bits, take a look here (i'm using it actually in my z80 code and changing the coeficients between games to get a few more pseudorandom ).

[gggcumming]

If its any use, this is the routine I used in all my asm programs.

Its computationally expensive, so I used to cheat and pre-generate my random numbers into a list and then use that!

Get_Random_Number

* D0 - Lower Bound, D1 - Upper Bound, number returned in d0

mult equ 34564
inc equ 7682
seed equ 12032
mod equ 65535

move.l d2,-(sp)
sub.w d0,d1
addq.w #1,d1
move.w old_seed,d2

mulu.w #mult,d2
add.l #inc,d2
divu.w #mod,d2
swap d2
move.w d2,old_seed

mulu.w d1,d2
divu.w #mod,d2
add.w d2,d0
move.l (sp)+,d2
rts
old_seed dc.w see

[victim]

Hi !

I think the best method is to use the cpu for programming a random function. Here i have found some information from the amycoders page.

so long victim

-------------------------

How are random numbers generated? True randomness is impossible to do on a computer since any number obtained will depend on the algorithm used to generate them and thus cannot possibly be random. Generally, it is sufficient to produce pseudorandom numbers, which are numbers that appear to be random. When we say they appear to be random, we mean that pseudorandom numbers should satisfy many of the properties that random numbers do. This is much easier said than done though.
Suppose we only need to simulate a coin flip. One way to do this is to examine the system clock. Presumably the clock maintains the number of seconds in the current time; if the number is even, we can return 0(for heads), and if it's odd, we can return 1 (for tails). The problem is that this strategy does not work well if we need a sequence of random numbers. One second is a long time, and the clock might not change at all while the program is running. We would expect to generate all 0s or all 1s, which is hardly a random-looking sequence. Even if the time was recorded in units of microseconds, and the program was running by itself, the sequence of numbers that would be generated would be far from random because the time between the calls to the generator would be essentially indentical on every program invocation.
What we really need is a sequence of pseudorandom numbers, a sequence with the same properties as a random sequence. Suppose we want random numbers between 0 and 999, uniformly distributed. In a uniform distribution, all numbers in the specified range are equally likely to occur. Other distributions are also widely used. We will see that most distributions can be derived from the uniform distribution, so that is the one we consider first. The following properties hold if the sequence 0...999 is a true uniform distribution:

• The first number to appear is equally likely to be 0,1,2...999.
• The ith number to appear is equally likely to be 0,1,2...999.
• The average of all the generated numbers is 499.5.

Theese properties are not particularly restrictive. For instance we could generate the first number by exmining the clock that was accurate to one millisecond and then using the number of milliseconds. We can generate subsequent numbers by adding one to the previous number. Clearly, after 1000 numbers are generated, all the properties above hold. However, stronger properties do not. Some stronger properties that would hold for uniformly distributed random numbers include:

• The sum of two consecutive numbers is equally likely to be even or odd.
• If 1000 numbers are randomly generated, some will be duplicated. Roughly 368 numbers will never appear.

Our numbers do not satisfy theese properties. Consecutive numbers always sum to an odd number, and our sequence is duplicate-free. We say that our simple pseudorandom number generator has failed two statistical tests. All pseudorandom number generators fail some statistical tests, but the better generators fail fewer tests than the bad ones.
Here we describe the simplest uniform generator that passes a reasonable number of statistical tests. By no means is it the best generator, but it is suitable for use as a reasonable generator in applications where a good approximation to a random sequence is acceptable. The method we use is the linear congruential generator, which was first described in 1951. Numbers X1,X2, ... are generated satisfying Xi + 1 = AXi(mod M)
This equation state that we can get the (i+1)th number by multiplying the ith number by some constant A and computing the remainder when the result is divided by M. In C/C++ we would do something like: X[ i+1 ] = A * X[ i ] % M;
The constants A and M are specified below. Notice that all generated numbers will be smaller than M. Some value X0 must be given to start the sequence. This value is known as the seed. If X0=0, then the sequence is not random because it generates all zeroes, but if A and M are carefully chosen, then any other seed satisfying 1 =< X0 < M is equally valid. If M is a prime, then Xi is never 0. For example, if M = 11,A=7, and the seed X0=1, then the numbers generated are 7,5,3,10,4,6,9,8,1,7,5,2, ...
When we generate a number a second time, we have a repeating sequence. In our case the sequence repeats after M-1 = 10 numbers; this is known as the period of the sequence. The period obtained with this choice of A is clearly as good as possible, since all nonzero numbers smaller than M are generated. (We must have a repeated number generated on the 11th iteration).
I believe this is a fairly detailed and extensive introduction to pseudorandom number generation which can be applicable in both assembler and C with ease. If you have made your own generator, and think it's better than this one, test it against all of the above properties, and if it holds, you can consider yourself lucky. ;-)

Example 1:

        moveq    #1,d7
        move.l    #9999,d0
loop: bsr         Random
        dbf        d0,loop
        rts

***********************************************************
* Input    *  d7 : seed
*
* Output
*  d7 : pseudo-random number
*
* Uses
*  d2-d7

Random:        
        move.l    d7,d6        ; copy Rand(i)
        move.l    #127773,d2    ; sythetic modulus
        bsr.b      Div        ; divide d6 by 127773
        move.l    d4,d5        ; copy to K1
        muls       #-2836,d5    ; d5 = -2836 * K1
        mulu       #42591,d4    ; multiply d4 by 127773
        move.l    d4,d6
        add.l      d4,d4
        add.l      d6,d4
        sub.l      d4,d7        ; d7 = Rand(i) - K1 * 127773

        moveq    #4,d4        ; loop counter
.loop:        
        move.l    d7,d6        ; multiply d7 by 16807
        lsl.l        #3,d7
        sub.l      d6,d7
        dbf        d4,.loop

        add.l      d5,d7        ; d7 = Rand(i + 1)
        bpl.b      .exit
        addi.l      #$7fffffff,d7    ; normalize negative result
.exit:        
        rts

***********************************************************

Div:   add.l      d6,d6        ; shift out unused bit
        moveq    #0,d4        ; quotient
        moveq    #14,d3      ; counter
        move.w  d6,d5        ; save low word of Rand(i)
        swap     d6
        andi.l     #$ffff,d6    ; d6 = Rand(i) DIV 2^15

.loop:        
        add.w    d4,d4        ; line up quotient and..
        add.w    d5,d5        ;   dividend
        addx.l    d6,d6        ; shift in bit of low word
        cmp.l     d2,d6        ; trial subtraction
        bmi.b     .exit
        sub.l      d2,d6        ; real subtraction
        addq.w  #1,d4        ; put 1 in quotient
.exit: dbf       d3,.loop     ; loop
        rts

Example 2:

              
;=============================================================================
; NAME
;    RandomSeed - seed random number generator, call once at beginning of
;          your program.  CurrentTime provides useful values for this
;
; SYSNOPSIS     RandomSeed( SeedValue )  D0
;
; FUNCTION     Seeds the random number generator
;
; INPUTS    SeedValue - a longword containing any value you like
;
; RESULT    Random number generator is initialised
;
;============================================================================

_RandomSeed
        MOVE.L    4(SP),D0    ;entry point for C functions
RandomSeed    
        ADD.L    D0,D1        ;user seed in d0 (d1 too)
        MOVEM.L    D0/D1,RND

; drops through to the main random function (not user callable)

LongRnd        
        MOVEM.L    D2-D3,-(SP)    
        MOVEM.L    RND,D0/D1    ;D0=LSB's, D1=MSB's of random number
        ANDI.B    #$0E,D0        ;ensure upper 59 bits are an...
        ORI.B    #$20,D0        ;...odd binary number
        MOVE.L    D0,D2
        MOVE.L    D1,D3
        ADD.L    D2,D2        ;accounts for 1 of 17 left shifts
        ADDX.L    D3,D3        ;[D2/D3] = RND*2
        ADD.L    D2,D0
        ADDX.L    D3,D1        ;[D0/D1] = RND*3
        SWAP    D3            ;shift [D2/D3] additional 16 times
        SWAP    D2
        MOVE.W    D2,D3
        CLR.W    D2
        ADD.L    D2,D0        ;add to [D0/D1]
        ADDX.L    D3,D1
        MOVEM.L    D0/D1,RND    ;save for next time through
        MOVE.L    D1,D0        ;most random part to D0
        MOVEM.L    (SP)+,D2-D3
        RTS

;=============================================================================
; NAME
;    Random - returns a random integer in the specified range
;
; SYSNOPSIS      RndNum = Random( UpperLimit )    D0          D0
;
; FUNCTION    returns a random integer in the range 0 to UpperLimit-1
;
; INPUTS     UpperLimit - a long(or short will do) in the range 1-65535
;
; RESULT     a random integer is returned to you, real quick!
;
; LIMITATIONS
;    range was limited to 1-65535 to avoid problems with the DIVU instruction
;    which can return real wierd values if the result is larger than 16 bits.
;
;============================================================================

_Random        
        MOVE.L    4(SP),D0    ;C entry point
Random    MOVE.W    D2,-(SP)
        MOVE.W    D0,D2        ;save upper limit
        BEQ.S    10$            ;range of 0 returns 0 always
        BSR.S    LongRnd        ;get a longword random number
        CLR.W    D0            ;use upper word (it's most random)
        SWAP    D0
        DIVU.W    D2,D0        ;divide by range...
        CLR.W    D0            ;...and use remainder for the value
        SWAP    D0            ;result in D0.W
10$        MOVE.W    (SP)+,D2
        RTS

        BSS
RND        DS.L    2            ;random number
        END

Originally Posted by meynaf

I've had a discussion with Thorham on that subject. My way is time counter reading (date/time, cia registers, and beam counter), with some computation on this (including the previous emitted random value).

What, according to people here, is the best method for that ?

[Photon]

I did some research on random number generation and made a short one modified from a paper by some Uni guys decennia ago, with improvements for minimum attractors.

It's really tricky to come up with some bit-massaging and math combo that doesn't result in patterning or biasing, especially if it is to deliver say, the full range of an axis. Best way to test it is to plot two axes scaled to fit in view for n x the axis length, then you can see patterns, range coverage and how quickly it covers the range.

Or hear it, if you use it as noise generator. The 'whiter' the noise is, the better the algorithm.

I think I used it in MonsterBobs, if so I'll grab that and share, um, brag :P
EDIT: Nah, it wasn't, I needed something even smaller. So here's that standard tiny one for now

RndW:	bsr.s RndB
	rol.w #8,d0
RndB:	move.b $dff007,d0		;Hpos
	move.b $bfd800,d5		;event counter
	eor.b d5,d0
	RTS

It's dangerous to use the realtime clock, as some Amigas don't have a clock and you end up with extremely little randomness

Also, if it's not allowed to repeat, it's not random. But for random playlists and stuff it's useful, even if you can use elimination of last n numbers to not mess up the random number generator routine itself.

[matthey]

There is some random number code on Aminet as well. This one in particular may be interesting for assembly coders...

http://aminet.net/dev/asm/Random250Lib.lha

[meynaf]

Well, so it appears that things are very similar to my actual method.

Here's my code. It's not very fast, but it needn't be in typical applications.

And it seems to give statistically significative results ; better than real dice anyway.

; random routine - takes rnd from 0 to D1-1 -> D0 (D1=0 means full 32-bit rnd)
rnd
 move.l d2,-(a7)
 move.l seed,d0
 move.w $dff006,d2
 swap d2
 move.b $bfe801,d2
 lsl.w #8,d2
 move.b $bfd800,d2
 add.l d2,d0
 mulu.l #$59fa769f,d2:d0
 add.l d2,d0
 addi.l #$4a5be021,d0
 ror.l #6,d0
 move.l d0,seed
 tst.l d1      ; 0 -> d0=full rnd32
 beq.s .nul
 moveq #0,d2
 divu.l d1,d2:d0
 move.l d2,d0   ; modulo
.nul
 movem.l (a7)+,d2
 rts

; init the seed
randomize
 lea $dff000,a2  ; custom chips
 lea $dc0000,a3  ; internal clock
 moveq #15,d7    ; (16 regs)
 move.w (a2),d0
 swap d0
 move.w d1,d0    ; d1 is bptr handle when we start ; depend on mem allocations
.loop            ; (so it's somewhat random too)
 rol.l #5,d0
 add.w (a3),d0
 addq.l #4,a3
 dbf d7,.loop
 add.l $a(a2),d0
 rol.l #7,d0
 add.l $12(a2),d0
 move.l d0,seed
 rts

Now i would like to answer my pal thorham, who doesn't seem to understand a few things... or perhaps i badly expressed myself ?

This discussion has started elsewhere, but i felt that a dedicated thread could be much better - and would allow other people to come in.

So here are the quotes.

1. Time taken by the user can be used as rnd seed.

Originally Posted by meynaf

Sorry pal, but the time in microseconds that you take to perform a click is random and unpredictable !

Originally Posted by Thorham

Humans can't click that fast. Even milliseconds are too fast. Probably a tenth of a second or so. Not good for random numbers at all. Furthermore, humans are not truly random to begin with. This is evident in programs that generate 'random' numbers based on mouse movements; you get patterns. Best sources are things like radio static (random and you can get lots of numbers quickly).

Can someone make him understand that it's precisely because humans can't click fast that they give good source of random numbers ? Hopefully you can't click that fast, and the number of microseconds you take will be large - and very variable - number !
Of course this isn't the generator by itself, but it certainly can be included in the seed.
Btw i don't see why radio static could be a good source.


2. About using a table...

Originally Posted by meynaf

On the other hand, a table isn't unpredictable once generated. What i'm saying is that the table is the OUTPUT of a random generator, not INPUT of it (for which it cannot be used), nor is it the generator itself, of course.

Originally Posted by Thorham

A table based on true random data (radio static) isn't predictable at all, that is, you can't recreate the table's contents with an algorithm, and you also can't recreate the table with the same random source (except by chance). What I want to know is why do you think that a table with numbers based on radio static can be predicted?

What i think is not that the table can be predicted, it's that it's useless for a random generator because it only contains a limited (and fixed) set of values.

Originally Posted by meynaf

So, at the end, it's not useful at all for someone who wants to write a generator !

Originally Posted by Thorham

It actually can be. The only problem is that the table can be copied. This is no good for security based applications, such as password generators, but it's fine for anything else.

No, no and no, a table isn't a random generator... it's just fixed data...


Hmm. I hope everything is clear enough. But i really HAD to move that into another thread.


Btw i still say that my actual random generator performs better than a real dice, because dice often (always) give some results more often than others, a problem which the generator haven't.

Even though it's supposed to be pseudo random, what really is random and pseudo is a philosophical question, isn't it ? Do true random really exist ?

Perhaps the answer comes from quantum physics. Then, as i've read that neurons appear to show quantic effects, they become unpredictable and the user is ultimately the best source of rnd for a computer.
Hence the time the user takes to do something is a good source !
And so time is best source of random numbers, whether Mr Thorham wants it or not

[victim]

Hi !

Good results you get through the usage of cia timers

so long...
victim

loop: cmp.b        #99,$dff006
        bne.s         loop

        move.w      #$f0f,$dff180
        
        move.w      #50-1,d7
rands: 
        moveq        #5,d0
        bsr            GetRnd020
        dbra          d7,rands
        
        move.w      #$bbc,$dff180

        btst        #6,$bfe001
        bne.s        loop
        rts


Randomizer:
        lea        maxrand(pc),a0
        move.l    d0,d2    
        st.b        seeded-maxrand(a0)
        move.b    $bfea01.l,d0        ;ciatodhi
        lsl.l         #8,d0
        move.b    $bfe901.l,d0        ;ciatodmid
        lsl.l         #8,d0
        move.b    $bfe801.l,d0        ;ciatodlow
        move.l     d0,random_seed-maxrand(a0)                
        tst.b       seeded-maxrand(a0)
        bne.b      valid_seed
        st.b        seeded-maxrand(a0)
        move.b    $bfea01.l,d0        ;ciatodhi
        lsl.l         #8,d0
        move.b    $bfe901.l,d0        ;ciatodmid
        lsl.l         #8,d0
        move.b    $bfe801.l,d0        ;ciatodlow
        move.l     d0,random_seed-maxrand(a0)
        move.l     d2,d0
valid_seed:    
        move.l     d0,(a0)                ;maxrand
        moveq     #0,d1
        move.b    $bfe801.l,d1        ;ciatodlow
        add.l       random_seed(pc),d1
        move.l     #$19660D,d0
        mulu.l      d1,d1:d0
        move.l     d0,random_seed-maxrand(a0)
        moveq     #0,d0
        swap      d0
        move.l    (a0),d3                ;maxrand
        mulu       d3,d0
        moveq    #0,d0
        swap     d0
        rts


maxrand:        dc.l    0
random_seed:    dc.l    0
seeded:            dc.w    0

[Thorham]

Originally Posted by meynaf

And it seems to give statistically significative results ; better than real dice anyway.

That's because dice throws aren't necessarily locally statistically correct. That's why you need many dice throws. As I said before, tens of thousands. That's the thing with true randomness: There's always a chance you'll end up with ten times heads in a row when flipping a coin. It's part of true random of this type.

Originally Posted by meynaf

Can someone make him understand that it's precisely because humans can't click fast that they give good source of random numbers ? Hopefully you can't click that fast, and the number of microseconds you take will be large - and very variable - number !
Of course this isn't the generator by itself, but it certainly can be included in the seed.

Sure, it's just that you end up with predictable data. Can be very difficult to break, but it's possible. This applies to all pseudo random number generators, not just to input and timer based ones.

Originally Posted by meynaf

Btw i don't see why radio static could be a good source.

It's a good source because the numbers you get are unpredictable and they're not related to each other. Unlike pseudo random number generators (which are useless for some applications).

Originally Posted by meynaf

What i think is not that the table can be predicted, it's that it's useless for a random generator because it only contains a limited (and fixed) set of values.

Okay, that's fair criticism.

Originally Posted by meynaf

No, no and no, a table isn't a random generator... it's just fixed data...

Of course a table doesn't generate anything, algorithms do that You can use a table in combination with a PRNG. With a table you can perhaps use a simpler PRNG algorithm and get more speed, which can be important sometimes. You can also use such a table to help make seed values. Tables aren't useless, but rather it all depends on what you need.

Originally Posted by meynaf

Btw i still say that my actual random generator performs better than a real dice, because dice often (always) give some results more often than others, a problem which the generator haven't.

That's because of the chance that you'll get pattern like results. That's dice, coin flips, etc for you! Basically if you need true random data then all PRNGs aren't useful anymore, and any true random source is better (because it can't be predicted).

Again, it all depends on what you need, and that's exactly why you 'can't' say that your PRGN is better than dice throws.

Originally Posted by meynaf

Even though it's supposed to be pseudo random, what really is random and pseudo is a philosophical question, isn't it ? Do true random really exist ?

This has absolutely nothing to do with philosophy, it's a physics question. It basically comes down to whether or not physics is ultimately deterministic or not. For all intents and purposes of today, something like radio static is certainly random, while a die may actually have relevant variables that can be reproduced for each throw (vacuum+robot+even surface). Perhaps you really are right about your dice throws

Originally Posted by meynaf

Perhaps the answer comes from quantum physics. Then, as i've read that neurons appear to show quantic effects, they become unpredictable and the user is ultimately the best source of rnd for a computer.

No, humans most certainly aren't the best source for random number generation, precisely because they aren't entirely unpredictable. Humans show many patters, while, for example, radio static doesn't.

Originally Posted by meynaf

Hence the time the user takes to do something is a good source !
And so time is best source of random numbers, whether Mr Thorham wants it or not

It's not about what I want, meynaf. If only you could make a true RNG like this, that would be great. But it's because you can't, that hardware RNGs exist. Time is not unpredictable, and even the speed of time can be measured! Time is not the best source for random numbers, although you can still use those methods to get effective results (although they're still not truly random, sadly).

[Thorham]

Originally Posted by Lionheart

Other option is using a Xorshift PRNG, they are very easy to convert to 68000 (a few EORs and ASL/R) and if you only need numbers of 8 or 16 bits, take a look here (i'm using it actually in my z80 code and changing the coeficients between games to get a few more pseudorandom ).

Here's my first try in 68K:

;------------------------------------------------------------------------------------
;XOR shift RND generator.
;------------------------------------------------------------------------------------
start
	bsr	xor128.init

	lea	dat,a0

	move.l	#1024,d7
.loop
	bsr	xor128.gen
	move.l	d2,(a0)+

	subq.l	#1,d7
	bne	.loop
	rts
;------------------------------------------------------------------------------------
xor128.init	;Call once before calling xor128.gen.
;------------------------------------------------------------------------------------
	move.l	a0,-(sp)

	lea	xor128_data,a0

	move.l	#123456789,(a0)+
	move.l	#362436069,(a0)+
	move.l	#521288629,(a0)+
	move.l	#88675123,(a0)+

	move.l	(sp)+,a0
	rts
;------------------------------------------------------------------------------------
xor128.gen	;Gets a random number.
;------------------------------------------------------------------------------------
;out:	d2=random number.
;------------------------------------------------------------------------------------
	movem.l	d0-d1/a0-a1,-(sp)

	lea	xor128_data,a0
	move.l	a0,a1

	move.l	(a0)+,d0
	move.l	(a0)+,(a1)+

	move.l	d0,d1
	lsl.l	#8,d1
	lsl.l	#3,d1

	move.l	(a0)+,(a1)+

	eor.l	d1,d0

	move.l	d0,d2
	lsr.l	#8,d2
	eor.l	d0,d2

	move.l	(a0)+,d1
	move.l	d1,(a1)+

	eor.l	d1,d2
	moveq	#19,d0
	lsr.l	d0,d1
	eor.l	d1,d2

	move.l	d2,(a1)

	movem.l	(sp)+,d0-d1/a0-a1
	rts
;------------------------------------------------------------------------------------
	section	data,data_f

xor128_data
	dcb.l	4
dat
	dcb.b	1024*1024
;------------------------------------------------------------------------------------

I sure hope there are no bugs

[pandy71]

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

[Photon]

Apart from first tries etc, which are usually shit (just look at my first try - it used the realtime clock...!), it's quite interesting to experiment with it. It's a good test of your algorithm design skills. The plot method gives more clues than the 'noise whiteness' method, of course, but they're both good.

I'd avoid constants as much as possible though, unless there's a researched (ie. not experimented) reason for them.

[Leffmann]

If you want to put your numbers up to real, rigid tests then look up The Diehard Battery of Tests of Randomness. The Xorshift family of algorithms that Lionheart linked to pass all of these tests, and the algorithms are simple, fast and scalable and IMO the best choice.

Though I dare say that for most purposes on the Amiga, being games I guess, sticking a few hundred values in a list, scrambling them around a bit and cycling through them, will be sufficient.

[Thorham]

Originally Posted by Leffmann

Though I dare say that for most purposes on the Amiga, being games I guess, sticking a few hundred values in a list, scrambling them around a bit and cycling through them, will be sufficient.

You could do something simple such as this to generate a table of numbers quickly:

start
	lea	$bfd800,a0	;Counter from time of day clock.
	lea	tab,a1
	moveq	#0,d0
	moveq	#0,d1
	moveq	#0,d2
	move.l	#255,d4
	move.l	#$11111111,d5

	move.l	#1023,d6
.loop_x
	move.l	#1023,d7
	rol.l	#1,d1
	move.b	(a0),d0
	add.l	d0,d1
.loop_y
	rol.l	#4,d1
	add.l	d2,d1
	add.l	d5,d2

	move.l	d1,d3
	and.l	d4,d3

	move.b	d3,(a1)+

	dbra	d7,.loop_y
	dbra	d6,.loop_x
	rts

	section	data,data_f
tab
	dcb.b	1024*1024

This generates a megabyte worth of PRND numbers in a about a second on a 50 mhz '030. Seems to work well, but don't ask me why

[SyX]

Originally Posted by Leffmann

Though I dare say that for most purposes on the Amiga, being games I guess, sticking a few hundred values in a list, scrambling them around a bit and cycling through them, will be sufficient.

Completely Agreed!!! Sometimes random is too random, usually a shuffling algorithm is what you need, perfect for tetris, bejewelled or another simple amiga game

[pandy71]

Write POTGO, read values from POTxDAT - they can be really random

[Thorham]

Thought this might be amusing:

[meynaf]

Originally Posted by Thorham

That's because dice throws aren't necessarily locally statistically correct. That's why you need many dice throws. As I said before, tens of thousands. That's the thing with true randomness: There's always a chance you'll end up with ten times heads in a row when flipping a coin. It's part of true random of this type.

Dice throws aren't globally statistically correct, and this makes a huge difference. No need to throw tens of thousands.
And this is because they can't be perfectly physically balanced, and they also get worse as they get used.

Originally Posted by Thorham

Sure, it's just that you end up with predictable data. Can be very difficult to break, but it's possible. This applies to all pseudo random number generators, not just to input and timer based ones.

Can you predict at which microsecond the user will do something ?
Come on, stay real.

Originally Posted by Thorham

It's a good source because the numbers you get are unpredictable and they're not related to each other.

What is the physics basis of this ? The fact this is actually unpredictable (and i need to know why) doesn't mean it will never be.

Originally Posted by Thorham

Unlike pseudo random number generators (which are useless for some applications).

And what applications are these ? A good pseudo random generator can be used everywhere, even in security applications.

Originally Posted by Thorham

Of course a table doesn't generate anything, algorithms do that You can use a table in combination with a PRNG. With a table you can perhaps use a simpler PRNG algorithm and get more speed, which can be important sometimes. You can also use such a table to help make seed values. Tables aren't useless, but rather it all depends on what you need.

I can't see anything i might need which has a use for a pre-generated random table. What about you ? Any examples in mind ?

Originally Posted by Thorham

That's because of the chance that you'll get pattern like results. That's dice, coin flips, etc for you! Basically if you need true random data then all PRNGs aren't useful anymore, and any true random source is better (because it can't be predicted).

Sorry, but my random generator doesn't get pattern like results. You can test it if you want, as i posted the code (which you already had because it is part of my framework includes since quite a long time).

Originally Posted by Thorham

Again, it all depends on what you need, and that's exactly why you 'can't' say that your PRGN is better than dice throws.

My blue 20-sided die does many more 3 than 20. My red one does many 8 and 12. No die i've ever tested is balanced.

On the other hand, my random generator doesn't have these problems. This is why i see it as better than the dice.

Originally Posted by Thorham

This has absolutely nothing to do with philosophy, it's a physics question. It basically comes down to whether or not physics is ultimately deterministic or not. For all intents and purposes of today, something like radio static is certainly random, while a die may actually have relevant variables that can be reproduced for each throw (vacuum+robot+even surface). Perhaps you really are right about your dice throws

Dice don't have perfect surface or shape, and this makes some results to come out many more often than others. Any RPG (not computer) player should know this

Originally Posted by Thorham

No, humans most certainly aren't the best source for random number generation, precisely because they aren't entirely unpredictable. Humans show many patters, while, for example, radio static doesn't.

You can't name a pattern that humans show that can make their timing predictable up to the microsecond !

Originally Posted by Thorham

It's not about what I want, meynaf. If only you could make a true RNG like this, that would be great. But it's because you can't, that hardware RNGs exist. Time is not unpredictable, and even the speed of time can be measured! Time is not the best source for random numbers, although you can still use those methods to get effective results (although they're still not truly random, sadly).

Sincerely i can generate megabytes of random numbers, and by looking at them you'll never detect they're pseudo-random. But if physics are deterministic, then everything is pseudo random, true random doesn't exist and that's all.
As we don't know this for sure, we can't tell that something is true random and something else isn't.

Time doesn't exist by itself if you ask me. What's used isn't just "time", but time it takes to perform something whose timing isn't predictable.

At the end, i'll say that my rnd generator never failed me, where dice did.
If you can find a specific application where it's not good enough, then tell me (and test it before speaking ).

Originally Posted by Thorham

Thought this might be amusing:

Yeah, you never know.

[Thorham]

Originally Posted by meynaf

Dice throws aren't globally statistically correct, and this makes a huge difference. No need to throw tens of thousands.
And this is because they can't be perfectly physically balanced, and they also get worse as they get used.

Sure, but the pattern in which the numbers appear is still unpredictable, and you'll only be able to say that the chance that one number will show up will be higher than for a different number.

Originally Posted by meynaf

Can you predict at which microsecond the user will do something ?
Come on, stay real.

Partially. If you measure at every micro second, then you'll only get 20 bits, furthermore, humans click at a somewhat uniform rate. You don't take a second to click once, and the next time you take only a tenth of a second. This means that you'll likely end up with only 10 to 15 useful bits. And finally, because humans don't click that often, you end up with extremely little data. Not enough for certain applications.

Originally Posted by meynaf

What is the physics basis of this ? The fact this is actually unpredictable (and i need to know why) doesn't mean it will never be.

Although I certainly can't explain this, why would radio static be predictable anyway?

Originally Posted by meynaf

And what applications are these ?

Applications for which you need true random data, such as for gambling games where money is involved, for example. Hence the existence of hardware RNGs.

Originally Posted by meynaf

A good pseudo random generator can be used everywhere, even in security applications.

No, only cryptographically strong PRNGs can be used for things such as encryption. There are quite a few very good PRGNs that are not cryptographically strong.

Originally Posted by meynaf

I can't see anything i might need which has a use for a pre-generated random table. What about you ? Any examples in mind ?

Yes! The simple algorithm I came up with can benefit from such data. Those tables can be used for seeding. You can actually do all sorts of things with such data.

Originally Posted by meynaf

Sorry, but my random generator doesn't get pattern like results. You can test it if you want, as i posted the code (which you already had because it is part of my framework includes since quite a long time).

To the human eye your algorithm doesn't produce any patterns, in fact my much simpler algorithm doesn't produce visible patterns, either. This of course doesn't mean that there are no patterns. The problem with your algorithm is that when you generate a table, say, for encryption, that the timers you're using will start to show regular behavior, because you're picking numbers at a regular interval. This means it's likely that your PRGN will be breakable. Only when you pick numbers at irregular intervals might the results be unpredictable.

Unpredictable PRGNs are used in cryptography, and they're more complex than yours, and even those can be broken, although it's extremely difficult. Actually, there are better PRNGs than yours that aren't secure.

Originally Posted by meynaf

My blue 20-sided die does many more 3 than 20. My red one does many 8 and 12. No die i've ever tested is balanced.

That's pretty crappy then!

Originally Posted by meynaf

On the other hand, my random generator doesn't have these problems. This is why i see it as better than the dice.

Except that your generator isn't random at all to begin with. No algorithm is. With unfair dice, there is only the chance that a number will show up more often than another, the pattern in which the numbers appear can't be predicted, however.

What I want to know is why you think your PRNG is so good?

Originally Posted by meynaf

Dice don't have perfect surface or shape, and this makes some results to come out many more often than others. Any RPG (not computer) player should know this

I'm not a pen and paper RPG player, and I don't use dice, so I didn't know this. It still doesn't matter, because the pattern your numbers will appear in can't be predicted. While it's easy to see patterns in a small number of throws, let's try ten thousand throws. Even a hundred throws doesn't mean anything.

Originally Posted by meynaf

You can't name a pattern that humans show that can make their timing predictable up to the microsecond !

The timigs aren't completely predictable, but there are some regularities, and humans are so slow that the little bit of unpredictability generated doesn't matter much at all.

Originally Posted by meynaf

Sincerely i can generate megabytes of random numbers, and by looking at them you'll never detect they're pseudo-random.

No, you can't see it with the naked eye. My simple, three line algorithm already does that. Your algorithm is too simple to be unpredictable, even with the timers (when generating a table). The moment you call your PRNG regularly (which is the case when making a table), the timers will start showing highly regular behavior, and this means you have patterns. This applies to all algorithms, and your's is not an exception.

Originally Posted by meynaf

But if physics are deterministic, then everything is pseudo random, true random doesn't exist and that's all.
As we don't know this for sure, we can't tell that something is true random and something else isn't.

And indeed we don't know this. However, something like radio static is for all intents and purposes truly random, and can't be predicted. There are simply physical events that can't be predicted. If the universe is deterministic than we still can't because we don't know how. Algorithms can always be predicted, although for a certain class of PRNGs this is incredibly difficult.

Originally Posted by meynaf

Time doesn't exist by itself if you ask me. What's used isn't just "time", but time it takes to perform something whose timing isn't predictable.

It is partially, and it's only of use if this data is collected freaquently enough.

Originally Posted by meynaf

At the end, i'll say that my rnd generator never failed me, where dice did.

For many purposes simple PRNGs like your own, will certainly be good enough.

Originally Posted by meynaf

If you can find a specific application where it's not good enough, then tell me (and test it before speaking ).

I can't test it, because I'm not a crypto analyst, but I find it extremely unlikely that your algorithm is cryptographically secure (it's too simple).

Here's some further reading on the subject: computers are lousy random number generators.