(Link to AcmlmWiki) Offline: thank ||bass
Register | Login
Views: 13,040,846
Main | Memberlist | Active users | Calendar | Chat | Online users
Ranks | FAQ | ACS | Stats | Color Chart | Search | Photo album
05-22-24 12:11 AM
0 users currently in Programming.
Acmlm's Board - I3 Archive - Programming - Low-Power Random Numbers New poll | |
Add to favorites | Next newer thread | Next older thread
User Post
Guy Perfect









Since: 11-18-05

Last post: 6304 days
Last view: 6302 days
Posted on 02-13-06 02:41 AM Link | Quote
I'm looking for a random number generator. For the longest time, I've been researching what makes a good one. What is good from the programmer's perspective is something that eventually generates all values for a given data size and generates them evenly (diversity), and the rate at which it repeats itself is as low as posible (period). To top it all off, I'm looking for a method that uses as little CPU time as possible.

What I've found is a very fast method, but of course uses more memory than most pseudorandom algorithms. The idea is v[a] = v[a-1] XOR v[a-n], where n is some arbitrary value. This requires a history buffer n+1 records long, which means RAM usage. Just set up a sliding variable for c that cycles through the entire history buffer from start to finish, then loops to start, and you get the algorithm v[c] = v[c-1] XOR v[c+1], assuming c-1 and c+1 will wrap around the bounds of the buffer (1 simle If statement each).

I've tested this algorithm with a history of 5000 8-bit values initialized with a fixed-seed pseudorandom built into the OS (so it'd be the same each execution) (the first value is initialized to 255 to ensure all bits are active), and I can verify that its diversity is good; all values generated are roughly equal in occurence. And because of how it's set up, you can extend the period to max out at some 3.232e+616 for 8-bit values alone just by changing the length of the history buffer.



My question, though: Does anyone else know of any faster, simpler, or better algorithms that provide good randomness with little processing?
kingshriek
Newcomer


 





Since: 02-13-06

Last post: 6639 days
Last view: 6639 days
Posted on 02-13-06 08:14 AM Link | Quote
If you're interested in random number generation, I recommend reading Chapter 7 of Numerical Recipes in C. In 7.4, they say that linear feedback shift register generators (LFSR) are poor random number generators when used as a series of bits interpreted as an integer or floating point number.

If you don't care too much about the quality of the random numbers, then LFSR makes for very fast generation. Many NES games use this technique, e.g. Adventures of Lolo 3 uses 8 bits of a 16-bit LFSR for password generation. Also, letting n (as given in your post) be an arbitrary value is a bad idea. For the most random results (maximal period for the shift register length), the feedback polynomial needs to be a primitive polynomial mod 2.
Guy Perfect









Since: 11-18-05

Last post: 6304 days
Last view: 6302 days
Posted on 02-13-06 01:04 PM Link | Quote
I know there has been unlimited research conducted on this stuff, but I honestly can't tell why this method may be considered inapproperiate. I ran a test overnight that counted up all combinations of 8 bits that occurred (even the distribution was sufficiently random) and used the generated numbers to draw colored pixels to locations on the screen. Even watching the initial speckle of incoming pixels was adequately random from a human perspective.

Are there perhaps any inherant flaws or problems with generating numbers this way for random use? From what I can observe, it's sufficiently adequate and the simplicity of implementation and speed of processing serve only as additional perks.
sloat



 





Since: 11-18-05
From: Delaware, US

Last post: 6405 days
Last view: 6405 days
Posted on 02-13-06 05:35 PM Link | Quote
For typical use, it shouldn't be a problem. But remember, it's a pseudorandom number generator. It's not safe for cryptography (IOW, the algorithm can be derived from the output) and it will repeat sequences eventually.
Guy Perfect









Since: 11-18-05

Last post: 6304 days
Last view: 6302 days
Posted on 02-13-06 10:04 PM Link | Quote
Well, the laws of physics prevent true randomness and the properties of any random number generator will eventually repeat a sequence in its entirety indefinitely given an infinite number of iterations. I was just asking if there's any kwirks that this particular method has.

Anyhow, I've FreeBASIC'd together a generator to use this method. It can be translated into other languages fairly easily:

'Variables used by the functions
Dim Shared N(0) As Byte, BigN As Long
Dim Shared CurN As Long 'Sliding Variable


'Generate the next number in the sequence
Public Function rndGenRand() As Byte
Dim NexN As Long, PreN As Long, Ret As Byte

'Obtain the previous and next buffered values
PreN = CurN - 1: If PreN = 0 Then PreN = BigN
NexN = CurN + 1: If NexN > BigN Then NexN = 1

'Calculate the new value
N(CurN) = N(PreN) XOr N(NexN)

'Increment sliding variable
Ret = N(CurN): CurN = CurN + 1
If CurN > BigN Then CurN = 1

'Return the value
rndGenRand = Ret
End Function


'Initialize the number generator
Public Sub rndInit(HistCount As Long)
Dim Q As Integer

'Redimension array with new value
BigN = HistCount
ReDim N(1 To BigN) As Byte

'Initialize the array
N(1) = &HFF
For I = 2 To BigN - 1
N(I) = Q: Q = Q + 37
If Q > 255 Then Q = Q - 255
Next

'Set up sliding variable
CurN = BigN

'Run a few startup mixing cycles
For I = 1 To 50: rndGenRand: Next
End Sub
And, of course, run rndInit before calling any rndGenRand's. I've found that calling rndInit passing a parameter of 100 works just fine.
FreeDOS +

Giant Red Koopa
Legion: freedos = fritos








Since: 11-17-05
From: Seattle

Last post: 6302 days
Last view: 6302 days
Posted on 02-13-06 11:09 PM Link | Quote
It's like the difference between /dev/random and /dev/urandom. The latter is quick and dirty, the former is slow but more random (better for real-use cryptography)
||bass
Administrator








Since: 11-17-05
From: Salem, Connecticut

Last post: 6303 days
Last view: 6302 days
Posted on 02-13-06 11:14 PM Link | Quote
Anyone who uses /dev/urandom for crypto deserves the royal assraping they're going to end up getting.
Guy Perfect









Since: 11-18-05

Last post: 6304 days
Last view: 6302 days
Posted on 02-13-06 11:37 PM Link | Quote
Fortunately, my primary application for randomization is games. This little, fast method works wonders for level generation and AI.
||bass
Administrator








Since: 11-17-05
From: Salem, Connecticut

Last post: 6303 days
Last view: 6302 days
Posted on 02-14-06 12:08 AM Link | Quote
You realize that when the system entropy poll runs out, urandom starts seeding from the system clock right?
Guy Perfect









Since: 11-18-05

Last post: 6304 days
Last view: 6302 days
Posted on 02-14-06 12:34 AM Link | Quote
Erm... Was that directed to me? I'm referring to the code I posted, not some OS generator.
||bass
Administrator








Since: 11-17-05
From: Salem, Connecticut

Last post: 6303 days
Last view: 6302 days
Posted on 02-14-06 01:52 AM Link | Quote
Originally posted by BGNG
Erm... Was that directed to me? I'm referring to the code I posted, not some OS generator.
Oh. Nvm then.
Add to favorites | Next newer thread | Next older thread
Acmlm's Board - I3 Archive - Programming - Low-Power Random Numbers |


ABII

Acmlmboard 1.92.999, 9/17/2006
©2000-2006 Acmlm, Emuz, Blades, Xkeeper

Page rendered in 0.015 seconds; used 399.84 kB (max 493.05 kB)