English Amiga Board


Go Back   English Amiga Board > Coders > Coders. Asm / Hardware

 
 
Thread Tools
Old 16 November 2020, 17:40   #21
ross
Defendit numerus

ross's Avatar
 
Join Date: Mar 2017
Location: Crossing the Rubicon
Age: 50
Posts: 3,127
Quote:
Originally Posted by roondar View Post
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.
ross is offline  
Old 16 November 2020, 18:20   #22
sparhawk
Registered User

sparhawk's Avatar
 
Join Date: Sep 2019
Location: Essen/Germany
Age: 52
Posts: 376
I downloaded this list of 32 bit prime numbers and picked one at random.
http://www.umopit.ru/CompLab/primes32eng.htm
sparhawk is offline  
Old 16 November 2020, 18:42   #23
roondar
Registered User

 
Join Date: Jul 2015
Location: The Netherlands
Posts: 2,686
Thanks, both of those might be a good options
roondar is offline  
Old 16 November 2020, 18:42   #24
ross
Defendit numerus

ross's Avatar
 
Join Date: Mar 2017
Location: Crossing the Rubicon
Age: 50
Posts: 3,127
Quote:
Originally Posted by sparhawk View Post
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)
ross is offline  
Old 16 November 2020, 18:57   #25
meynaf
son of 68k
meynaf's Avatar
 
Join Date: Nov 2007
Location: Lyon / France
Age: 48
Posts: 4,145
Here is the one i'm using :
Code:
 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.
meynaf is offline  
Old 16 November 2020, 19:23   #26
ross
Defendit numerus

ross's Avatar
 
Join Date: Mar 2017
Location: Crossing the Rubicon
Age: 50
Posts: 3,127
Yep, good, but problematic if custom chip state is deterministic (UAE), clock unavailable and location absolute
ross is offline  
Old 16 November 2020, 19:42   #27
meynaf
son of 68k
meynaf's Avatar
 
Join Date: Nov 2007
Location: Lyon / France
Age: 48
Posts: 4,145
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).
meynaf is offline  
Old 16 November 2020, 20:20   #28
ross
Defendit numerus

ross's Avatar
 
Join Date: Mar 2017
Location: Crossing the Rubicon
Age: 50
Posts: 3,127
Quote:
Originally Posted by meynaf View Post
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.

Quote:
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.

Quote:
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
ross is offline  
Old 16 November 2020, 20:38   #29
meynaf
son of 68k
meynaf's Avatar
 
Join Date: Nov 2007
Location: Lyon / France
Age: 48
Posts: 4,145
Quote:
Originally Posted by ross View Post
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


Quote:
Originally Posted by ross View Post
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.


Quote:
Originally Posted by ross View Post
Yes, but for existing code?
Existing code will not use your random generator, will it ? Or what did i miss ?


Quote:
Originally Posted by ross View Post
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.
meynaf is offline  
Old 16 November 2020, 20:51   #30
ross
Defendit numerus

ross's Avatar
 
Join Date: Mar 2017
Location: Crossing the Rubicon
Age: 50
Posts: 3,127
Quote:
Originally Posted by meynaf View Post
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)

Quote:
That would not bring you very far. There are only 80 possible positions.
Not the longitudinal position but the position along the track.
ross is offline  
Old 17 November 2020, 09:30   #31
coder76
Registered User

 
Join Date: Dec 2016
Location: Finland
Posts: 123
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.
coder76 is offline  
Old 17 November 2020, 09:59   #32
Thomas Richter
Registered User
 
Join Date: Jan 2019
Location: Germany
Posts: 966
There are many, many tests in the references I gave. The spetral test is the most important one, but there are many more.
Thomas Richter is offline  
Old 17 November 2020, 10:41   #33
modrobert
old bearded fool

modrobert's Avatar
 
Join Date: Jan 2010
Location: Bangkok
Age: 53
Posts: 538
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/
modrobert is offline  
Old 17 November 2020, 11:21   #34
hooverphonique
ex. demoscener "Bigmama"

 
Join Date: Jun 2012
Location: Fyn / Denmark
Posts: 1,217
Quote:
Originally Posted by sparhawk View Post
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!?
hooverphonique is offline  
Old 17 November 2020, 11:48   #35
DanScott
Lemon. / Core Design

DanScott's Avatar
 
Join Date: Mar 2016
Location: Tier 5
Posts: 891
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.
DanScott is offline  
Old 23 November 2020, 19:13   #36
Antiriad_UK
OCS forever!

Antiriad_UK's Avatar
 
Join Date: Mar 2019
Location: Birmingham, UK
Posts: 355
Quote:
Originally Posted by a/b View Post
1. short
2. fast
3. accurate
Pick two :P.

This is a quick&dirty one that works for me:
Code:
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:
Code:
    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)

Code:
*****************************************************************************
* 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

Last edited by Antiriad_UK; 23 November 2020 at 19:48.
Antiriad_UK is offline  
Old 23 November 2020, 20:01   #37
ross
Defendit numerus

ross's Avatar
 
Join Date: Mar 2017
Location: Crossing the Rubicon
Age: 50
Posts: 3,127
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:
Code:
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

Last edited by ross; 23 November 2020 at 21:51.
ross is offline  
Old 23 November 2020, 22:22   #38
a/b
Registered User

 
Join Date: Jun 2016
Location: europe
Posts: 306
Quote:
Originally Posted by Antiriad_UK View Post
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.
a/b is offline  
Old 23 November 2020, 23:19   #39
DanScott
Lemon. / Core Design

DanScott's Avatar
 
Join Date: Mar 2016
Location: Tier 5
Posts: 891
Quote:
Originally Posted by Antiriad_UK View Post
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:
Code:
    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
DanScott is offline  
Old 24 November 2020, 01:16   #40
Antiriad_UK
OCS forever!

Antiriad_UK's Avatar
 
Join Date: Mar 2019
Location: Birmingham, UK
Posts: 355
Quote:
Originally Posted by a/b View Post
IIRC, I mentioned I was generating 16-bit numbers. If not, my bad for not being more specific.
Opps totally missed that
Antiriad_UK is offline  
 


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Serial Numbers vs QC numbers question 005AGIMA support.Other 1 05 January 2020 14:53
Fast floating-point random numbers Leffmann Coders. Tutorials 27 25 August 2016 02:59
Help needed!!Random octal numbers generator(asm) sheryn88 Coders. General 6 01 August 2010 08:19
A nice quick small random numbers routine? Photon Coders. General 2 20 December 2004 22:56
IP numbers Squonk project.WinUAE - Kaillera 0 24 September 2003 14:12

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 07:44.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, vBulletin Solutions Inc.
Page generated in 0.15390 seconds with 13 queries