English Amiga Board Random numbers
 Register Amiga FAQ Rules & Help Members List  /  Moderators List Today's Posts Mark Forums Read

 15 November 2020, 16:24 #1 sparhawk Registered User   Join Date: Sep 2019 Location: Essen/Germany Age: 52 Posts: 353 Random numbers I was looking for some algorithm how to create random numbers. When I look at the glibc source, it looks extremly complicated and expensive. Another approach I became aware of was, to use a Murmur2 hash value. This works quite nice, but it also looks computationally expensive. From guts feeling I think it's not as expensive as the glibc code, but still. So I was wondering if there is some better approach which is also fast. At least the Murmur2 code looks much easier to translate to asm, so if there is no better alternative I will take that one. As a nice side effect, I have then a hashing algorithm as well.
 15 November 2020, 17:11 #2 daxb Registered User   Join Date: Oct 2009 Location: Germany Posts: 2,736 If you search the Coders forum for "random" you get some threads that should give several solutions for fast and cheap random generators. There is also a long discussion I remember with code examples.
 15 November 2020, 17:15 #3 thomas Registered User   Join Date: Jan 2002 Location: Germany Posts: 6,152 I once looked at the algorithm used by C64 Basic. It's really simple: it takes the 32bit seed, EORs it by a large random number (probably a prime number) and orders the bytes backward. The seed was then interpreted as a float and normalized to be between 0 and 1. But that's not necessary, you already get quite good results if you divide the seed by the desired range and use the remainder as result. Something like this for random numbers between 1 and 6: Code: ``` move.l seed,d0 eor.l #\$87654321,d0 swap.w d0 swap.l d0 swap.w d0 move.l d0,seed divu #6,d0 swap.l d0 ext.l d0 addq.l #1,d0``` (I don't remember exactly, it might as well be ADD instead of EOR.)
 15 November 2020, 17:22 #4 sparhawk Registered User   Join Date: Sep 2019 Location: Essen/Germany Age: 52 Posts: 353 Thanks. I tried to search, but I didn't find much. Maybe the wrong search phrase. That algorithm looks nice and simple.
 15 November 2020, 17:54 #5 jotd This cat is no more   Join Date: Dec 2004 Location: FRANCE Age: 49 Posts: 4,936 Code: ``` ;;; EAB simple random generator ; thanks meynaf mulu #\$a57b,d0 addi.l #\$bb40e62d,d0 rol.l #6,d0```
 15 November 2020, 20:09 #6 Wepl Moderator   Join Date: Nov 2001 Location: Germany Posts: 749 Code: ``` move.l seed,d0 eor.l #\$87654321,d0 swap.w d0 swap.l d0 swap.w d0 move.l d0,seed divu #6,d0 swap.l d0 ext.l d0 addq.l #1,d0``` swap.w swap.l ?? there is only swap
15 November 2020, 21:39   #7
Thomas Richter
Registered User

Join Date: Jan 2019
Location: Germany
Posts: 865
Quote:
 Originally Posted by sparhawk I was looking for some algorithm how to create random numbers.
Donald Knuth, "The Art of Programming", Vol. II: "Numerical and Semi-numerical algorithms". Contains everything you ever wanted to know about random generators and you never dared to ask.

The quick morale: Do not pick the algorithm to generate random numbers at random. In particular, do not accept "home made" algorithms. About the simplest random number generators are "linear congruence random generators", which use a multiply-add approach. Depending on the numbers you pick, the results are "ok".

Quote:
 Originally Posted by sparhawk When I look at the glibc source, it looks extremly complicated and expensive.
For a reason. Better quality requires more complexity. The linear congruence generators are not too good. A simple one is this one:

Code:
```        saveregs a2/a6
lea _Seed(a4),a2
move.l (a2),d0
move.l _UtilityBase(a4),a6
move.l #1664525,d1      ;Knuth's algorithm
jsr -\$90(a6)            ;UMul
move.l d0,(a2)
rts```
[/QUOTE]
This is Knuth's linear congruence algorithm with a modulo value of 2^32. It is well researched and well understood. Do not exchange the multiplication with anything else, neither its constant.

Note that if you use the output of this algorithm: Always use data from the MSBs on, do not generate random numbers by "masking", as the LSBs have a much smaller period.

15 November 2020, 23:10   #8
meynaf
son of 68k

Join Date: Nov 2007
Location: Lyon / France
Age: 47
Posts: 4,107
Quote:
 Originally Posted by Thomas Richter Note that if you use the output of this algorithm: Always use data from the MSBs on, do not generate random numbers by "masking", as the LSBs have a much smaller period.
There is another way to work around this shortcoming : just rotate the result.
This will not, however, fix the problem with the short period of the algorithm (for a 32-bit seed, it's in the thousands).

 16 November 2020, 10:06 #9 a/b Registered User   Join Date: Jun 2016 Location: europe Posts: 254 1. short 2. fast 3. accurate Pick two :P. This is a quick&dirty one that works for me: Code: ```Init: move.l #,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
16 November 2020, 10:49   #10
Thomas Richter
Registered User

Join Date: Jan 2019
Location: Germany
Posts: 865
Quote:
 Originally Posted by meynaf There is another way to work around this shortcoming : just rotate the result. This will not, however, fix the problem with the short period of the algorithm (for a 32-bit seed, it's in the thousands).
No. The period of a linear congruence random generator does not depend on the seed. It depends on the gcd of the modulo and the multiplier, here 2^32 and, well, the magic number in the code. This number here was not picked at random, so the period is really maximal. It is not in the thousands. Note, however, that this assumes that you pick bits from the MSB on. The period on the LSBs is small.

16 November 2020, 10:50   #11
Thomas Richter
Registered User

Join Date: Jan 2019
Location: Germany
Posts: 865
Quote:
 Originally Posted by a/b 1. short 2. fast 3. accurate Pick two :P. This is a quick&dirty one that works for me: Code: ```Init: move.l #,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
Looks like snake oil to me. Is there anything documented about the properties of this generator.

 16 November 2020, 11:05 #12 a/b Registered User   Join Date: Jun 2016 Location: europe Posts: 254 The one I posted? That one, as stated, works for me, to generate a few thousand random 16-bit numbers very quickly (6 bytes inline, 20 cycles on a 68000). Xorshift? Yeah, there are many variants that pass the bigcrush tests. Look up xorshift and xoshiro. But most importantly, read the first 4 lines (and pick two) :P. That's the point.
 16 November 2020, 11:45 #13 Thomas Richter Registered User   Join Date: Jan 2019 Location: Germany Posts: 865 The question is not "whether it works for you", but whether it is a good random generator and passes a couple of tests, for example the spectral test. See again Knuth II for a lot of tests and a lot of material on random generators, and in particular why home-made generators are not a good idea.
 16 November 2020, 12:22 #14 a/b Registered User   Join Date: Jun 2016 Location: europe Posts: 254 moveq #oh-how-i-love-arguing-with-internet-strangers-about-nothing,d0 ... not.l d0 Again, you are missing the point. Taking a step back, xorshift is not some mumbo jumbo, and as i said it passes the bigcrush test which is a few hours long test. Now, back to code I posted... You should stop looking at this from your point of view only, especially in a coders/asm forum. - Original poster said, in a general manner, that he needs a fast algorithm but doesn't specify how fast is fast enough for his definition of fast in this fast moving thread. - Apply 2-out-of-3 rule. - Different people present different options. 0-1 choice 0-\$ff better choice 0-\$ffff betterer choice 0-\$ffffffff bettererer choice So what's the problem? Need better accuracy (*again*, 2-out-of-3 rule)? 1. pick a better seed/modifier 2. use shift/ror instead of a swap 3. use 2x32 bits ... 9. use the "full-blown" xorshift algorithm, which is still plenty fast, if you still like this type of rng 10. use something else that you like more or that works better in your, and unknown to us, scenario
 16 November 2020, 12:51 #15 sparhawk Registered User   Join Date: Sep 2019 Location: Essen/Germany Age: 52 Posts: 353 The numbers should be sufficiently random for a game. they don't need to hold against a scientific test. So in a game, speed is important, but I think if I have the choice between a bad generator and a little bit slower one, then I might take the slower one. If it starts to get a performance issue, then a less "random" algorithm might be acceptable. I thought of adding a few of them and then compare how the perform vs. how they "feel" regarding randomness.
16 November 2020, 15:38   #16
meynaf
son of 68k

Join Date: Nov 2007
Location: Lyon / France
Age: 47
Posts: 4,107
Quote:
 Originally Posted by Thomas Richter No. The period of a linear congruence random generator does not depend on the seed. It depends on the gcd of the modulo and the multiplier, here 2^32 and, well, the magic number in the code. This number here was not picked at random, so the period is really maximal. It is not in the thousands. Note, however, that this assumes that you pick bits from the MSB on. The period on the LSBs is small.
Well ok, but this has a price : the period of the LSBs is very, very small (lower byte starts to repeat after 256 values !). May make it unsuitable, depending on the needs.

16 November 2020, 15:45   #17
meynaf
son of 68k

Join Date: Nov 2007
Location: Lyon / France
Age: 47
Posts: 4,107
Quote:
 Originally Posted by a/b Taking a step back, xorshift is not some mumbo jumbo, and as i said it passes the bigcrush test which is a few hours long test.
Indeed xorshift is fast and passes many tests (not all : it fails linear complexity tests). While unsuitable for cryptography, for most applications it's more than enough.

16 November 2020, 16:40   #18
Thomas Richter
Registered User

Join Date: Jan 2019
Location: Germany
Posts: 865
Quote:
 Originally Posted by sparhawk The numbers should be sufficiently random for a game. they don't need to hold against a scientific test.
I don't see how one contradicts the other. Depending on the type of game, and your needs for randomness, a good generator is absolutely necessary, and not a "scientific exercise" at all. Without knowing the game and your needs, one cannot give recommendations.

 16 November 2020, 16:54 #19 Rotareneg Registered User   Join Date: Sep 2017 Location: Kansas, USA Posts: 198 I suggest using RANDU just to irritate PRNG algorithm snobs.
 16 November 2020, 17:25 #20 roondar Registered User   Join Date: Jul 2015 Location: The Netherlands Posts: 2,471 Now I've been looking for a random number algorithm generator as well and it looks like something like xorshift would be good enough for my purpose. Assuming I'd use xorshift, what would be good initial seed (or state) values for 32 bit signed/unsiged random numbers? See, to me it seems to me that getting the seed right is the critical part for using this type of algorithm properly.

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

 Similar Threads Thread Thread Starter Forum Replies Last Post 005AGIMA support.Other 1 05 January 2020 14:53 Leffmann Coders. Tutorials 27 25 August 2016 02:59 sheryn88 Coders. General 6 01 August 2010 08:19 Photon Coders. General 2 20 December 2004 22:56 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 Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home News Main     Amiga scene     Retrogaming General Discussion     Nostalgia & memories Support     New to Emulation or Amiga scene         Member Introductions     support.WinUAE     support.WinFellow     support.OtherUAE     support.FS-UAE         project.AmigaLive     support.Hardware         Hardware mods         Hardware pics     support.Games     support.Demos     support.Apps     support.Amiga Forever     support.Amix     support.Other Requests     request.UAE Wishlist     request.Old Rare Games     request.Demos     request.Apps     request.Modules     request.Music     request.Other     Looking for a game name ?     Games images which need to be WHDified abime.net - Hall Of Light     HOL news     HOL suggestions and feedback     HOL data problems     HOL contributions abime.net - Amiga Magazine Rack     AMR news     AMR suggestions and feedback     AMR data problems     AMR contributions abime.net - Home Projects     project.Amiga Lore     project.EAB     project.IRC     project.Mods Jukebox     project.Wiki abime.net - Hosted Projects     project.aGTW     project.APoV     project.ClassicWB     project.Jambo!     project.Green Amiga Alien GUIDES     project.Maptapper     project.Sprites     project.WinUAE - Kaillera Other Projects     project.Amiga Demo DVD     project.Amiga Game Factory     project.CARE     project.Amiga File Server     project.CD32 Conversion     project.Game Cover Art         GCA.Feedback and Suggestions         GCA.Work in Progress         GCA.Cover Requests         GCA.Usefull Programs         GCA.Helpdesk     project.KGLoad     project.MAGE     project.Missing Full Shareware Games     project.SPS (was CAPS)     project.TOSEC (amiga only)     project.WHDLoad         project.Killergorilla's WHD packs Misc     Amiga websites reviews     MarketPlace         Swapshop     Kinky Amiga Stuff     Collections     EAB's competition Coders     Coders. General         Coders. Releases         Coders. Tutorials     Coders. Asm / Hardware     Coders. System         Coders. Scripting         Coders. Nextgen     Coders. Language         Coders. C/C++         Coders. AMOS         Coders. Blitz Basic     Coders. Contest         Coders. Entries Creation     Graphics         Graphics. Work In Progress         Graphics. Finished Work         Graphics. Tutorials     Music         Music. Work In Progress         Music. Finished Work         Music. Tutorials Off Topic     OT - General     OT - Entertainment     OT - Sports     OT - Technical     OT - Gaming

All times are GMT +2. The time now is 09:03.

 -- EAB3 skin ---- EAB2 skin ---- Mobile skin Archive - Top