Random numbers

[ross]

Originally Posted by roondar

See, to me it seems to me that getting the seed right is the critical part for using this type of algorithm properly.

Yes, good seed is a problem, mainly in WinUAE (it's fully predictive).

On real Amiga is relatively easy to get it: something related to MFMpos on floppy, or timers/beampos in the other cases.

[sparhawk]

I downloaded this list of 32 bit prime numbers and picked one at random.
http://www.umopit.ru/CompLab/primes32eng.htm

[roondar]

Thanks, both of those might be a good options

[ross]

Originally Posted by sparhawk

I downloaded this list of 32 bit prime numbers and picked one at random.

Problem here is not to pick a random pre-made seed, but to generate a different sequence on different launch.

So a way to get a random seed every time
(or at least to generate the sequence from 'enough' seeds, which then explodes into thousands of pseudo-random numbers)

With WinUAE I failed (On A500 CE emulation)

[meynaf]

Here is the one i'm using :

 lea $dff000,a2    ; custom chips
 lea $dc0000,a3    ; clock (if there is one)
 moveq #15,d7
 move.w (a2),d0
 swap d0
 move.w d1,d0      ; d1 is dos bptr upon program entry
.loop
 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

It depends on custom chips state, internal clock (should there be one), and program location.
Not good enough as a random generator by itself, but nevertheless a satisfying seed.

[ross]

Yep, good, but problematic if custom chip state is deterministic (UAE), clock unavailable and location absolute

[meynaf]

That's too iffy for its intended use case, which is under OS.
There, not only the user will take indefinite amount of time to run the program ; there is also host disk i/o that will add some random time and thus custom chip state ceases to be deterministic.

Anyway, you *have* to find a source of entropy somewhere.
If there is none, the task is simply impossible !

In all cases however, the user can give you some. Wait for some mouse/keyboard/joystick input, and measure the time it took. You could do that not only at startup but permanently, updating your seed.

Also it might be eventually possible to execute native code from winuae (i just don't know how).

[ross]

Originally Posted by meynaf

there is also host disk i/o that will add some random time and thus custom chip state ceases to be deterministic.

Not on floppy i/o in UAE CE cases.

Anyway, you *have* to find a source of entropy somewhere.
If there is none, the task is simply impossible !

There is sure a source, even on emulation: the host machine, so the value must somehow come from there.

Also it might be eventually possible to execute native code from winuae (i just don't know how).

Yes, but for existing code?


Adding up all these questions/answers there is therefore a possibility: make sure that UAE set the floppy head on a random position when a load for the very first track from floppy is requested

On real machines this is "automatic": when you boot the machine and start DMA for the firsts floppy load you sure are in a random position with the head (which cascades propagates to the execution of the code that generates the seed based on a state at that point definitely random).
Same for HDD load.

I had talked about it with Toni and he had explained to me why it is not so, I don't remember anymore, but it were certainly good reasons

[meynaf]

Originally Posted by ross

Not on floppy i/o in UAE CE cases.

You're looking for trouble
Stop using floppies, use the OS, and it will work fine

Originally Posted by ross

There is sure a source, even on emulation: the host machine, so the value must somehow come from there.

This requires some direct access to the host machine, as otherwise its entropy is hidden by cycle exact emulation.

Originally Posted by ross

Yes, but for existing code?

Existing code will not use your random generator, will it ? Or what did i miss ?

Originally Posted by ross

Adding up all these questions/answers there is therefore a possibility: make sure that UAE set the floppy head on a random position when a load for the very first track from floppy is requested

On real machines this is "automatic": when you boot the machine and start DMA for the firsts floppy load you sure are in a random position with the head (which cascades propagates to the execution of the code that generates the seed based on a state at that point definitely random).
Same for HDD load.

I had talked about it with Toni and he had explained to me why it is not so, I don't remember anymore, but it were certainly good reasons

That would not bring you very far. There are only 80 possible positions.
Ya better ask for some winuae backdoor to grab random data.

[ross]

Originally Posted by meynaf

Existing code will not use your random generator, will it ? Or what did i miss ?

Some game (or game protection) behave the same when you run them multiple times in WinUAE, it's not the same for the real machine.
And in any case I would like to use a simple way in my code (for example the x position of the video beam) to generate a simple seed and I can't do that on all existing emulated machine (I'm talking about my particular case histories as a patcher of old games)

That would not bring you very far. There are only 80 possible positions.

Not the longitudinal position but the position along the track.

[coder76]

One simple and good way of testing the randomness of the pseudornd generator is to randomize some small number, e.g. 1-10, and add these numbers together and make a histogram of the results. For 1 number you should get a uniform distribution, for 2 added numbers a triangular, and 3 added numbers a parabolic distribution. The distribution should approach a gaussian distribution for many added numbers.

I remember some bad simple rnd generators couldn't ever produce a lot of same outcomes in succession so the tails were missing in the distribution of added numbers. Of course you need to collect a lot of statistics to see the tails.

[Thomas Richter]

There are many, many tests in the references I gave. The spetral test is the most important one, but there are many more.

[modrobert]

Hardware random generators are better, make it a fun project, Amiga parallel port uses 5V which should be fine for the bus interface, some examples:

https://makezine.com/projects/really...ber-generator/

[hooverphonique]

Originally Posted by sparhawk

I downloaded this list of 32 bit prime numbers and picked one at random.
http://www.umopit.ru/CompLab/primes32eng.htm

But don't you need an RND-generator in order to do that!?

[DanScott]

Best to avoid a multiply of divide where possible.

I use a RNG that uses just a swap and a couple of adds, and it works great. I use it to generate noise maps etc, with no issues.

More important is seeding it well.

[Antiriad_UK]

Originally Posted by a/b

1. short
2. fast
3. accurate
Pick two :P.

This is a quick&dirty one that works for me:

Init:	move.l	#<seed>,d7	; large prime numbers
	move.l	#$6be7d35b,d6	; are good...

Rng:	swap	d7
	add.l	d6,d7
	eor.l	d6,d7

It's based on this: https://en.wikipedia.org/wiki/Xorshift

I was trying to make a function that just generates a screen of noise and tried to use this one but I tried a few prime seeds and when you had a screenful of noise it had really obvious repeating patterns. I don't know if you viewed it like that or if my implementation was bad

Dan mentioned a quick one involving a swap and a couple of adds. I wonder if it's this one that uses this idea: https://www.flipcode.com/archives/07-15-2002.shtml . I found a snippet on the atari forum that used it like:

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

    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

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

It sure looks good when viewed as screen noise - no obvious repeats - and nice and simple too. I don't know if anyone knows how good exactly it is (or not) . I added it to my library for a generic "create noise of xxx words" function. I added a bit of complexity to write longs instead of words, I'm sure someone will have a better idea for handling odd numbers of words rather than mine (edit: just thought of doing the odd word first and not using d4 at all, updated)

*****************************************************************************
* Generates a number of words of noise into a buffer.
*
*http://www.flipcode.com/archives/07-15-2002.shtml
*
* IN:		d0.w, number of words
*		d1.l/d2.l seeds
*		a0, buffer
* OUT:		d1.l/d2.l new seeds		
* TRASHED:	d0-d2/a0
*****************************************************************************

	xdef	LIB_GenNoise_W
LIB_GenNoise_W:
	move.l	d3,-(sp)

	lsr.w	#1,d0			;number of words to longs
	bcc.s	.firstlong
.firstword:
	move.l	d2,d3
	swap	d3
	add.l	d1,d2
	add.l	d3,d1
	move.w	d3,(a0)+		;write out just word
.firstlong	
	subq.w	#1,d0			;-1 for dbf
	bmi.s	.done
.loop:
	move.l	d2,d3
	swap	d3
	add.l	d1,d2
	add.l	d3,d1
	move.l	d3,(a0)+		;write out entire long
	dbf	d0,.loop
.done:
	move.l	(sp)+,d3
	rts

[ross]

I remember writing some code to generate a noise screen and it seemed to work very well (in fact it was not a screen but a face of a glenz polygonal object with a random changing stencil inside).

I picked up the code and it was just this:

random_generator:
		move.w	#$880/4-1,d1
		lea	random,a0
		move.l	#$bada55a0,d0
.lr		addq.l #5,d0
		rol.l d0,d0
		move.l d0,(a0)+
		dbf	d1,.lr

I should try to recover it and see how it behaves

[a/b]

Originally Posted by Antiriad_UK

I was trying to make a function that just generates a screen of noise and tried to use this one but I tried a few prime seeds and when you had a screenful of noise it had really obvious repeating patterns. I don't know if you viewed it like that or if my implementation was bad

Well, my intention was not to give you some code and tell "use this, it works" . My code is using the idea of xorshift&co and twisting it to the extreme, sacrificing accuracy for speed. It works in some cases, and it doesn't in others. In one of my latter posts I gave a few alternatives to increase accuracy (and yeah, seed is super important). Anyway, it was about pushing you in the right direction so you can possibly write something that's mucho fast and works for you. OK, enough bull :P.

I tried it with this seed (literally 2x faceroll): 25434<<16+16514. Plugged that in and repeated 320*256/16 times. It's important to use words when writing to bitplane (e.g. move.w d7,(ax)+)!! Looked pretty ok-ish. Then I increased the accuracy and replaced swap d7 with rol.l #1,d7 (+6 cycles) and it looked noticably better.
I guess the problem was using longwords, that won't work good. IIRC, I mentioned I was generating 16-bit numbers. If not, my bad for not being more specific.

[DanScott]

Originally Posted by Antiriad_UK

Dan mentioned a quick one involving a swap and a couple of adds. I wonder if it's this one that uses this idea: https://www.flipcode.com/archives/07-15-2002.shtml . I found a snippet on the atari forum that used it like:

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

    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

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

Yeah, that's the one, forgot where I stole it from

Of course, the random screen noise we (or at least a lot of us) used back in the day (ie in the credits of Madness 2), was generated by drawing a couple of blitter lines from y = 0 to y = 255, with random x coordinates, then blitter filling the buffer.. and repeat that each frame without clearing the buffer... that generated a really good and convincing noise effect.

It got me thinking recently if that method could be used to generate (for example) a 256 byte random number table each frame

[Antiriad_UK]

Originally Posted by a/b

IIRC, I mentioned I was generating 16-bit numbers. If not, my bad for not being more specific.

Opps totally missed that