random number generation (in asm)

[meynaf]

Originally Posted by Ed Cruse

I want to see what you think of the data without any bias. After you do that then I'll explain how it works and upload the program that I'm going to write to actually generate the data. Then you can really tear it apart.

I will think nothing at all about the data. You could fool people with an extract of compressed data and say it actually comes from a PRNG.
Generated data isn't a good way for me to see the quality of a generator.

[meynaf]

Originally Posted by Thorham

To meynaf:

Bah, I wanted to delete this lengthy post, but to no avail. Guess I'll leave it then. The problem seems to be that we're arguing over 'timer less RNGs' vs 'timer RNGs'. Anyway, read on, and see why I think this is not a good idea

Ok.

Originally Posted by Thorham

The point is that if the PRNG is biased too much that the chance to hit won't be the same as the actual hits. That's bad.

But which PRNG is biased like that ?

Originally Posted by Thorham

No, it isn't, but multiplies aren't by definition the best method anyway.

Multiplies are certainly better than exclusive or.

Originally Posted by Thorham

Depends, but it doesn't matter. Why use a bad PRNG if you can use a good one?

Because what you say is good is the bad one, and vice-versa

Originally Posted by Thorham

Oh, but they are simple. Three adds and three rotates is certainly much simpler than your routine. Any way, it would be nice if you'd post the code to do this.

No need. A simple test will do (see below).

Originally Posted by Thorham

I've seen it in the basic visual test where you draw a square of pixels with random gray values. The square I've used is 256x256 pixels, and the gray values are 8 bit. Simply generate a 32 bit value and use the first byte as a gray value. Then wait for a key press, and draw a new square without re-seeding the PRNG. You'll see the pattern after a few key presses, especially if you skip each second 32 bit value (makes the period half as small so it's more obvious).

Are you sure you didn't misuse it ? I'll perform the test myself to be sure.

Originally Posted by Thorham

No, it's not, it's about your claim that your PRNG is better than the simple algorithms posted in this thread, which is not true.

It IS true (see test below).

Originally Posted by Thorham

No, many of them are not poor, and I don't know what you're basing this claim on. They're perfectly useful for general use.

They are not (see test below, again).

Originally Posted by Thorham

Multiplies are not that good for generating random numbers. This is the reason why most of the modern algorithms don't use them at all. Many games typically don't have very good algorithms for this. In fact, many of the worst algorithms use those silly multiplies.

And why would multiplies be not good ? Because Mr Thorham decided that they are Evil or for another reason ?

Originally Posted by Thorham

Of course I know that Captive levels are random

Because i told it to you.

Originally Posted by Thorham

It is if it doesn't offer any advantages.

But it just works better. Anyway, it's not really slower ; on a machine with fast multiply it will even be faster than many of them.

Originally Posted by Thorham

No, it's not. All PRNGs can have timers added, I've already said this. Timers don't count here, and I'm only talking about the base algorithm, not about the timer influences.

All PRNGs give the same result for the same seed, and all PRNGs loop, without exception.

But i told you why the multiply is better when you use timers, and you seemed to agree. Your memory is short

Originally Posted by Thorham

That's actually the one I was talking about. Again, any PRNG can benefit from hardware state (including timers). Hardware state doesn't count when discussing PRNG algorithms. The hardware state can be used to randomize a PRNG when it's called, but it's essentially a separate thing.

Basically what I'm saying is that the algorithms posted in this thread are either about as good as your timer less PRNG or they're a lot better.

And basically you're just plain wrong (see below, i repeat myself ).

Originally Posted by Thorham

Probably, but its very difficult. Certainly not worth my time when much easier, faster and better results can be obtained very quickly with other methods. Many of the best PRNGs don't even use multiplies at all. Says enough. Multiplies are an old way of doing this stuff, and they've been exceeded by much better methods.

Says who ? (apart yourself)

Originally Posted by Thorham

Yeah, that's probably not a bad idea. Just remember that those timers (or hardware state) are not to be included in those tests, or they'll be useless. Always test the base algorithm. The timer influence should be seen as separate (can be added to any algorithm to make it better, even the bad ones).

I've made my first test. It's just about setting the seed to a number which look like a coordinate - an integer from 1 to 64.
Then i get 64 random numbers, and extract their lower bit (bit #0) to make a 64-bit final bit-mask.
You can get the source here : meynaf.free.fr/tmp/tstrnd.lzx
If i misused some code, please fix it.

Guess what ? Nearly all methods here that i could check just miserably fail this test and show real obvious patterns, thus are unusable for my map generator program.
However, both my methods pass this test, apart that the first one fails if the timer reads are suppressed (this is why i insisted on this being an important part of it).

So long for your "better" methods.

[Ed Cruse]

Originally Posted by meynaf

I will think nothing at all about the data. You could fool people with an extract of compressed data and say it actually comes from a PRNG.
Generated data isn't a good way for me to see the quality of a generator.

I see your point. I'll upload the Amiga executable to the zone, everytime you run it you'll get a different sequence. It generates the starting seed by hashing the current date stamp? The source code would be difficult, it's a function inside of a C program. Once I tell you how it works you can probably do it for yourself.

I did upload a 10 meg sequence and I assure you it's real.

When you download the executable type at a dos prompt:

makefile filename "" rndsize=10000000

Filename is the path and file name where you want the data to go. Be sure to put the "", and you can change the size to something other then 10000000.

[Thorham]

To Ed Cruse:

I've tested the data you uploaded with the Diehard test suite, and it only seems to fail the Binary Rank test, and it seems to pass the other 14 tests, so that's not bad at all However, I'm no expert, so my interpretation of the test results might be off. Still, it seems to be a good algorithm. Source please

Originally Posted by meynaf

But which PRNG is biased like that ?

Low quality, biased PRNGs can do this (crypto algorithms don't count), but I can't give you an example

Originally Posted by meynaf

Multiplies are certainly better than exclusive or.

Perhaps, although XORS can be good if used properly (not always easy).

Originally Posted by meynaf

Because what you say is good is the bad one, and vice-versa

No, you're dead wrong, see below

Originally Posted by meynaf

Are you sure you didn't misuse it ? I'll perform the test myself to be sure.

Yes, I'm very sure.

Originally Posted by meynaf

And why would multiplies be not good ? Because Mr Thorham decided that they are Evil or for another reason ?

They're not the best choice, because they're hard to use properly, and can easily give low quality results.

Originally Posted by meynaf

Because i told it to you.

What? Why wouldn't I know Captive uses random dungeons? Probably everyone who's played Captive knows that

Originally Posted by meynaf

But it just works better. Anyway, it's not really slower ; on a machine with fast multiply it will even be faster than many of them.

No, it doesn't, see below.

Originally Posted by meynaf

But i told you why the multiply is better when you use timers, and you seemed to agree. Your memory is short

I think I'll take that back then.

Originally Posted by meynaf

Says who ? (apart yourself)

Like I said, many of the best algorithms don't use them, which makes it seem that multiplies aren't a good choice anymore. It's just based on what I've seen.

Originally Posted by meynaf

I've made my first test. It's just about setting the seed to a number which look like a coordinate - an integer from 1 to 64.
Then i get 64 random numbers, and extract their lower bit (bit #0) to make a 64-bit final bit-mask.
You can get the source here : meynaf.free.fr/tmp/tstrnd.lzx
If i misused some code, please fix it.

Guess what ? Nearly all methods here that i could check just miserably fail this test and show real obvious patterns, thus are unusable for my map generator program.
However, both my methods pass this test, apart that the first one fails if the timer reads are suppressed (this is why i insisted on this being an important part of it).

So long for your "better" methods.

Your test is so faulty that I don't know where to start...

The only reason why your timer less algorithm passes this test is because the counter you use to re-seed the PRNG (d1 in the euh block) gets multiplied by constants and has constants added to it. This is not random at all. PRNGs need the previous state to generate a new number, and this isn't happening. In the case of your algorithm it also means that the dungeon is going to be the same each time you call the routine, because your algorithm only has a 32 bit seed, and this is simply incremented by one for each call. Again, this isn't random at all.

Also, my algorithms don't have a 32 bit seed. The three liner has a 64 bit seed, and the 4 liner has a 96 bit seed. This extra information isn't saved, and it's necessary to do so.

Basically the mistake you're making is that none of the internal states of the PRNGs are saved, which means they all fail this test, including yours (multiplying and adding constants to a counter that is incremented by one for each call isn't random).

Further more, I've seen some LCGs in there. The problem with LCGs is that their lower bits are essentially useless (known fact), and you have to use the highest bits that are used, or they will fail when used normally.

Re-seeding PRNGs before each call is known to be a bad practice, and you're doing it with a simple counter! What I want to know is why you don't just call your PRNG twice per coordinate in the normal way (seed once and save the internal state) and simply use the two 32 bit numbers as the 64 bit mask?

The bottom line is that your test doesn't prove anything about the quality of PRNGs, because it doesn't use any of the PRNGs in the right way:

1) Re-seeding for every call.
2) Not storing the complete internal state information.

Try again, because your test has failed, not the PRNGs.

[Thorham]

Meynaf, here's my current multiply-less timer based PRNG (seems to pass the Diehard test suite), which can also be used to seed a normal PRNG (which is actually it's primary use):

seed
	movem.l	d0-d3/d6-d7/a0,-(sp)

	lea.l	state,a0
	movem.l	(a0),d0-d3

	move.l	$dff006,d6
	move.b	$bfe601,d7
	lsl.l	#8,d7
	move.b	$bfe701,d7
	lsl.l	#8,d7
	move.b	$bfe801,d7
	lsl.l	#8,d7
	move.b	$bfd800,d7

	add.l	d6,d0
	rol.l	#7,d0
	add.l	d1,d0

	add.l	d7,d1
	rol.l	#7,d1
	add.l	d2,d1

	add.l	d6,d2
	rol.l	#7,d2
	add.l	d3,d2

	add.l	d7,d3
	rol.l	#7,d3
	add.l	d0,d3

	move.l	d3,seed
	movem.l	d0-d3,(a0)

	movem.l	(sp)+,d0-d3/d6-d7/a0
	rts

	section	data,data_f
state
	dcb.l	4
seed
	dc.l	0

Notice that it's slower than yours (), because I'm reading more chip set registers (those CIA reads are over 200 cycles per read ). Basically, if you read multiple timer values, you can never have a fast generator Also, it's probably overkill (except for seeding)

[Ed Cruse]

[quote=Thorham;693055]To Ed Cruse:

I've tested the data you uploaded with the Diehard test suite, and it only seems to fail the Binary Rank test, and it seems to pass the other 14 tests, so that's not bad at all However, I'm no expert, so my interpretation of the test results might be off. Still, it seems to be a good algorithm. Source please


I'll send the C code for the actual functions involved, it's fairly complicated and probably will have to be modified to run in a normal C environment. I use my own environment and function libraries.

This is how the PRNG works. I simply use the CRC32 that's used for the internet as a 32 bit to 32 bit hash. At first I simply fed the hash with a consecutive stream of numbers and the output looked random but when I protted it, it had definite patterns. So then I fed the output to the input knowing that it would probably repeat before it did the entire 2^32 sequence. This is how it is now. As it turns out it doesn't repeat, I wrote a program that accounts for every single 32 bit number and it hits all the numbers but one. This is the number where the input equals the output with the hash, you wouldn't want to use that number as a seed. If I change anything in the hash like the poly constant then it repeats, so who ever come up with the CRC32 for the internet really new what they were doing. I've tried various other standard CRC hashes and they all repeat no matter what I do, so I'd say I was very lucky to find this one.

There's three functions involved, an open, close, and the hash itself. The open builds a table of 32 bit numbers and sets things up, close deallocates everything. The table makes doing CRC32 much faster. I'll upload the functions to the zone shortly. Also my C code tends to look like assembly because I used to write everything in assembly, so most C programmers don't like my C code. I use C as a high level assembly language.

If you have questions I'll do my best to answer them.

Do you happen to know what a binary rank test is? I'll have to find the test program I was using and see if it has that test.

Also, because I was lazy I used a program that I had already written. It takes the 32 bit output and does modulo 256 on it and outputs 0-255. This is more or less how the PRNG would normally be used, ranges other then 0-(2^32). I upload this program to the zone, it's a dos command. Type "makefile ?" and you'll see the template. Or "makefile filename "" rndsize=10000000" to geneate a sequence.

[meynaf]

Originally Posted by Ed Cruse

I see your point. I'll upload the Amiga executable to the zone, everytime you run it you'll get a different sequence. It generates the starting seed by hashing the current date stamp? The source code would be difficult, it's a function inside of a C program. Once I tell you how it works you can probably do it for yourself.

When you download the executable type at a dos prompt:

makefile filename "" rndsize=10000000

Filename is the path and file name where you want the data to go. Be sure to put the "", and you can change the size to something other then 10000000.

Good, thanks. I'll check it. With source, of course, it's perhaps easier

Originally Posted by Thorham

Low quality, biased PRNGs can do this (crypto algorithms don't count), but I can't give you an example

Ok.

Originally Posted by Thorham

Perhaps, although XORS can be good if used properly (not always easy).

They don't move bits around in the number, so they're not quite useful.

Originally Posted by Thorham

No, you're dead wrong, see below

Ha !

Originally Posted by Thorham

Yes, I'm very sure.

I have made a 256-gray 256x256 image test and i cannot see a pattern or whatsoever, even after several consecutive images without reseeding. This doesn't mean there is none, of course. But anyway, even if a pattern is there, it doesn't change the fact that this method is NOT designed to be used like that (and i already told you this, but you never seem to understand, do you ?).

Originally Posted by Thorham

They're not the best choice, because they're hard to use properly, and can easily give low quality results.

But XOR is even worse. You only prefer them because they're faster, which is no longer the case on a machine with fast mul.

Originally Posted by Thorham

What? Why wouldn't I know Captive uses random dungeons? Probably everyone who's played Captive knows that

I remember i told it to you and that you didn't seem to know (or even believe it). Want me to dig a link to the relevant message ?

Originally Posted by Thorham

No, it doesn't, see below.

Ha again. See below.

Originally Posted by Thorham

Like I said, many of the best algorithms don't use them, which makes it seem that multiplies aren't a good choice anymore. It's just based on what I've seen.

And what are the "best" algorithms ? This is quite a claim from yours.

Originally Posted by Thorham

Your test is so faulty that I don't know where to start...

It's not faulty. But, of course, as you see the results and not like them, you say it is.

Originally Posted by Thorham

The only reason why your timer less algorithm passes this test is because the counter you use to re-seed the PRNG (d1 in the euh block) gets multiplied by constants and has constants added to it. This is not random at all. PRNGs need the previous state to generate a new number, and this isn't happening.

My test extracts the first number for consecutive seeds. No pattern must be visible here, or the method is a bad one. As simple as that.

Originally Posted by Thorham

In the case of your algorithm it also means that the dungeon is going to be the same each time you call the routine, because your algorithm only has a 32 bit seed, and this is simply incremented by one for each call. Again, this isn't random at all.

And this is exactly what i needed for the dungeon (actually the outside of it). It must be the same each time ; in fact i must be able to alter some part without affecting others. So i used coordinates as seed, and then get something that doesn't show patterns. No other method here does that.

Originally Posted by Thorham

Also, my algorithms don't have a 32 bit seed. The three liner has a 64 bit seed, and the 4 liner has a 96 bit seed. This extra information isn't saved, and it's necessary to do so.

It's not necessary for this particular test, because i extract only the first number - which MUST be random as the others.

Now imagine you're doing a small program that basically emulates a physical die. Only the very first number is useful here. Your saved state accounts for nothing.

Originally Posted by Thorham

Basically the mistake you're making is that none of the internal states of the PRNGs are saved, which means they all fail this test, including yours (multiplying and adding constants to a counter that is incremented by one for each call isn't random).

It's not a mistake. The PRNGs here all fail this test because they're poor, no more no less. They show patterns.

And this doesn't include mine. What you do in your code isn't random either (adds, moves and eors aren't random, yeah). Multiplying and adding constants just make the things more irregular, which is what we need.

Originally Posted by Thorham

Further more, I've seen some LCGs in there. The problem with LCGs is that their lower bits are essentially useless (known fact), and you have to use the highest bits that are used, or they will fail when used normally.

If their lower bits are useless, just add a rotation. And then you will see that they still fail the test quite lamentably.

Originally Posted by Thorham

Re-seeding PRNGs before each call is known to be a bad practice, and you're doing it with a simple counter! What I want to know is why you don't just call your PRNG twice per coordinate in the normal way (seed once and save the internal state) and simply use the two 32 bit numbers as the 64 bit mask?

And who said it was a bad practice ? It's just a test.

But when generating land outside, typically you'll be calling that code once per cell (often to choose from 2 cell types, hence the use of the lower bit). Same cell must have SAME result regardless of the whole number of cells. Neighbour cells (with consecutive coords) mustn't show a pattern. This test shows these patterns quite perfectly.

Here my method isn't only the "best" one. It's in fact the only one that's just merely usable.

Originally Posted by Thorham

The bottom line is that your test doesn't prove anything about the quality of PRNGs, because it doesn't use any of the PRNGs in the right way:

Now there's a "right" way to use a RNG !

Originally Posted by Thorham

1) Re-seeding for every call.

Yes, to see if the FIRST number is really random. It obviously isn't.

Originally Posted by Thorham

2) Not storing the complete internal state information.

Because if would be utterly useless to do so !

Originally Posted by Thorham

Try again, because your test has failed, not the PRNGs.

My test hasn't failed. But YOU failed. And you hate this, so you bash the test which showed it. How typical.

To say things in short : a good PRNG is basically a good hashing algorithm. And a good hash doesn't show similar bit patterns for consecutive values.

Originally Posted by Thorham

Meynaf, here's my current multiply-less timer based PRNG (seems to pass the Diehard test suite), which can also be used to seed a normal PRNG (which is actually it's primary use):

(...)

Notice that it's slower than yours (), because I'm reading more chip set registers (those CIA reads are over 200 cycles per read ). Basically, if you read multiple timer values, you can never have a fast generator Also, it's probably overkill (except for seeding)

Your distaste for multiplies never fails to amaze me, mate.

[Thorham]

Originally Posted by meynaf

They don't move bits around in the number, so they're not quite useful.

They scramble bits, and therefore they are useful, just not so easy to use properly.

Originally Posted by meynaf

I have made a 256-gray 256x256 image test and i cannot see a pattern or whatsoever, even after several consecutive images without reseeding. This doesn't mean there is none, of course. But anyway, even if a pattern is there, it doesn't change the fact that this method is NOT designed to be used like that (and i already told you this, but you never seem to understand, do you ?).

The pattern is quite chaotic, not immediately obvious: normal.zip. This image is the third image if you generate it like you've done. I've used seed=1 and a modulo of 2^32-1. I've used the first byte of each longword value (when stored in memory: byte 0,4,8, etc) for the gray tint. Also, this test is meant to show the period of the PRNG, an important part of any PRNG. The pattern is hard to spot, but it's there if you look very carefully.

Originally Posted by meynaf

But XOR is even worse. You only prefer them because they're faster, which is no longer the case on a machine with fast mul.

I don't use XOR, but ADD, because add is easier.

Originally Posted by meynaf

I remember i told it to you and that you didn't seem to know (or even believe it). Want me to dig a link to the relevant message ?

Okay, that's certainly possible. Guess I forgot.

Originally Posted by meynaf

And what are the "best" algorithms ? This is quite a claim from yours.

There are a few. Perhaps I'll look them up. But seeing how they probably won't pass your 'test', I won't be able to convince you any way.

Originally Posted by meynaf

It's not faulty. But, of course, as you see the results and not like them, you say it is.

That is complete none sense meynaf, I'm not that sort of person

Originally Posted by meynaf

My test extracts the first number for consecutive seeds. No pattern must be visible here, or the method is a bad one. As simple as that.

I've made an image based on the output of this test using your method, and it's patterned as you can see in here: reseeded.zip. Of course I simply let the seed count in the normal way.

Originally Posted by meynaf

And this is exactly what i needed for the dungeon (actually the outside of it). It must be the same each time ; in fact i must be able to alter some part without affecting others. So i used coordinates as seed, and then get something that doesn't show patterns. No other method here does that.

As you've seen it is patterned. Furthermore, this is a bad practice. Just generate a table, and use different parts of the table. Much easier, and a million times better.

Originally Posted by meynaf

It's not necessary for this particular test, because i extract only the first number - which MUST be random as the others.

It is necessary, you can't expect something to work properly if it's used in the wrong way. This is why your test is bogus.

Originally Posted by meynaf

Now imagine you're doing a small program that basically emulates a physical die. Only the very first number is useful here. Your saved state accounts for nothing.

Saved states are crucial in the proper functioning of PRNGs. Rock hard fact that's widely known.

Originally Posted by meynaf

It's not a mistake. The PRNGs here all fail this test because they're poor, no more no less. They show patterns.

The PRNGs are not poor. You base this on improper use of those algorithms, and therefore your test fails.

Originally Posted by meynaf

And this doesn't include mine. What you do in your code isn't random either (adds, moves and eors aren't random, yeah). Multiplying and adding constants just make the things more irregular, which is what we need.

You mean ADDs and ROLs. I don't use EOR. ROLs and ADDS make things very irregular, too.

Originally Posted by meynaf

And who said it was a bad practice ? It's just a test.

It's a known fact that reseeding a PRNG before every call is a bad practice, it's not my idea.

Originally Posted by meynaf

But when generating land outside, typically you'll be calling that code once per cell (often to choose from 2 cell types, hence the use of the lower bit). Same cell must have SAME result regardless of the whole number of cells. Neighbour cells (with consecutive coords) mustn't show a pattern. This test shows these patterns quite perfectly.

If you had performed the graphical test on your own data, then you'd know that it's patterned.

Originally Posted by meynaf

Now there's a "right" way to use a RNG !

Again, this is a hard fact, and not my idea.

Originally Posted by meynaf

Because if would be utterly useless to do so !

It's a complete necessity.

Originally Posted by meynaf

My test hasn't failed. But YOU failed. And you hate this, so you bash the test which showed it. How typical.

No, I don't hate it. If you think that I'm that kind of person, then you've got me all wrong.

Originally Posted by meynaf

To say things in short : a good PRNG is basically a good hashing algorithm. And a good hash doesn't show similar bit patterns for consecutive values.

Then yours is bad, too, as I've shown.

Originally Posted by meynaf

Your distaste for multiplies never fails to amaze me, mate.

I deem them unnecessary, although George Marsaglia (mathematician, random expert) has written a very good PRNG that uses multiplies. It's called 'multiply with carry'.

The bottom line is that PRNGs don't work properly (including yours as I've shown), if you reseed before every call. This is known to be a very bad practice. A PRNG isn't bad just because it doesn't work when it's misused in this way.

Even the very high quality Mersenne Twister (of which only a part has been posted in this thread previously) will fail your test miserably, because it needs a good initial seed, and it it needs all of it's state information saved. Here is the whole algorithm in pseudo code:

 // Create a length 624 array to store the state of the generator
 int[0..623] MT
 int index = 0
 
 // Initialize the generator from a seed
 function initializeGenerator(int seed) {
     MT[0] := seed
     for i from 1 to 623 { // loop over each other element
         MT[i] := last 32 bits of(1812433253 * (MT[i-1] xor (right shift by 30 bits(MT[i-1]))) + i) // 0x6c078965
     }
 }
 
 // Extract a tempered pseudorandom number based on the index-th value,
 // calling generateNumbers() every 624 numbers
 function extractNumber() {
     if index == 0 {
         generateNumbers()
     }
     
     int y := MT[index]
     y := y xor (right shift by 11 bits(y))
     y := y xor (left shift by 7 bits(y) and (2636928640)) // 0x9d2c5680
     y := y xor (left shift by 15 bits(y) and (4022730752)) // 0xefc60000
     y := y xor (right shift by 18 bits(y))
     
     index := (index + 1) mod 624
     return y
 }
 
 // Generate an array of 624 untempered numbers
 function generateNumbers() {
     for i from 0 to 623 {
         int y := 32nd bit of(MT[i]) + last 31 bits of(MT[(i+1) mod 624])
         MT[i] := MT[(i + 397) mod 624] xor (right shift by 1 bit(y))
         if (y mod 2) == 1 { // y is odd
             MT[i] := MT[i] xor (2567483615) // 0x9908b0df
         }
     }
 }

You may want to read a bit about it here: http://en.wikipedia.org/wiki/Mersenne_twister.

Basically, you're going against known facts. Your test shows nothing, and I have no problem with you telling me that my PRNGs are poor based on your test, because I know better than that. What I do care about is that a smart guy like you doesn't want to accept those facts as the truth

[Ed Cruse]

I have an idea about measuring the quaility of the output of a PRNG. Since white noise is supposed to be perfectly random, how about taking PRNG data and determining how good of white noise it is. I know when I listen to the output of my PRNG it sounds like really good quality white noise, of course that's might not mean much.

I'm thinking do a fourier transform and generate a frequency verses amplitude spectrum. Then do a k=4 standard deviate on the amplitude data, that would tell you the variation of the amplitude of 99% of the amplitude data. I believe perfect white noise has all frequencies with all the same amplitude and phase. To me the obvious problem would be the amount of data that can be analyzed. 10 megs even with a fast fourier transform could take a very long time. I'm not sure at this point.

So what do you think?

[Ed Cruse]

To Meynaf:

[quote=meynaf;693708]Good, thanks. I'll check it. With source, of course, it's perhaps easier


In case you haven't noticed I did upload the C and assem sources, in one of the previous messages to Thorham I explained how the PRNG works.

[Thorham]

Originally Posted by Ed Cruse

I have an idea about measuring the quaility of the output of a PRNG. Since white noise is supposed to be perfectly random, how about taking PRNG data and determining how good of white noise it is. I know when I listen to the output of my PRNG it sounds like really good quality white noise, of course that's might not mean much.

Probably all data that looks random (like TV noise) will sound like white noise, so that may or may not be the best idea. On the other hand, it's probably still a useful test, because the ear picks up different things than the eye.

Originally Posted by Ed Cruse

I'm thinking do a fourier transform and generate a frequency verses amplitude spectrum. Then do a k=4 standard deviate on the amplitude data, that would tell you the variation of the amplitude of 99% of the amplitude data. I believe perfect white noise has all frequencies with all the same amplitude and phase. To me the obvious problem would be the amount of data that can be analyzed. 10 megs even with a fast fourier transform could take a very long time. I'm not sure at this point.

Hmm, I don't actually know what a fourier transform is. I've heard of it, but I have no math background. However, I think I've read somewhere that they actually uses this, so if my memory is correct, it's probably a good idea.

About about your generator: What algorithm did you use for the CRC? You talk about the CRC from the internet, but which one is that? You don't have to post the source, but a pointer about the algorithm would be useful

[Ed Cruse]

Originally Posted by Thorham

Probably all data that looks random (like TV noise) will sound like white noise, so that may or may not be the best idea. On the other hand, it's probably still a useful test, because the ear picks up different things than the eye.
Hmm, I don't actually know what a fourier transform is. I've heard of it, but I have no math background. However, I think I've read somewhere that they actually uses this, so if my memory is correct, it's probably a good idea.

About about your generator: What algorithm did you use for the CRC? You talk about the CRC from the internet, but which one is that? You don't have to post the source, but a pointer about the algorithm would be useful

A Fourier transform is pretty cool. You can take any data like audio or PRNG and do a forward Fourier transform and get a frequency versus amplitude curve. Basically all signals are made up of sine waves of different amplitudes and phases, and when added together make up your original signal. This is how digital filters work. As an example you take an audio signal convert it to a frequency verses amplitude spectrum with a forward Fourier transform and then you can go in and change the amplitude of any frequency to any amplitude. Do a reverse Fourier transform and generate the new signal, as if it was an analog signal that just got processed by an analog filter.

The source codes are in the zone, C and assem. I found a print out of CRCs in general that came from Wikipedia. The title is "Cyclic redundancy check". It appears I'm using the same CRC32 that's used by Ethernet, FDDI, PKZip, WinZip, and PNG. It appears to be "CRC32 IEEE 802.3". I haven't found the information for doing CRCs in general. The method I'm using uses a lookup table which makes it much faster. In the source codes "CRC32open.c" creates the table and deallocates it. Rndgen.asm does the actual CRC32 calculations.

I did all this years ago so I may have difficulty finding the info. Study the sources which is what I originally did with the sources I found on the internet.

[Maccara]

Meynaf, you have not only shown that you don't even know what a pseudorandom number generator means, but also that you don't understand statistics or probability.

Your claims and tests are utter crap, and you seriously need to do some basic reading on number theory & probability before venturing any further as currently you're only digging yourself deeper with every claim.

This is becoming "rather silly".

[Don_Adan]

Originally Posted by Maccara

Meynaf, you have not only shown that you don't even know what a pseudorandom number generator means, but also that you don't understand statistics or probability.

Your claims and tests are utter crap, and you seriously need to do some basic reading on number theory & probability before venturing any further as currently you're only digging yourself deeper with every claim.

This is becoming "rather silly".

Are you sure? For me this is difference between theory (like you) and practice (like meynaf).

[Maccara]

Originally Posted by Don_Adan

Are you sure? For me this is difference between theory (like you) and practice (like meynaf).

Well, I know little bit of theory and practice. Using the tools wrong on purpose and then blaming the tools is not the way to go, not in theory or practice.

[meynaf]

Originally Posted by Thorham

They scramble bits, and therefore they are useful, just not so easy to use properly.

They don't scramble much because they don't alter all bits. A multiply does change all bits and, due to the modulus that's implied, it also is a non-reversible operation. EORs are just good to mix several randoms together.

Originally Posted by Thorham

The pattern is quite chaotic, not immediately obvious: Attachment 26210. This image is the third image if you generate it like you've done. I've used seed=1 and a modulo of 2^32-1. I've used the first byte of each longword value (when stored in memory: byte 0,4,8, etc) for the gray tint. Also, this test is meant to show the period of the PRNG, an important part of any PRNG. The pattern is hard to spot, but it's there if you look very carefully.

Still totally irrelevant to me. Add some timer reads, and you'll no longer loop.

Originally Posted by Thorham

I don't use XOR, but ADD, because add is easier.

But ADD still doesn't move bits around very much, nor does it mix them enough.

Originally Posted by Thorham

There are a few. Perhaps I'll look them up. But seeing how they probably won't pass your 'test', I won't be able to convince you any way.

Look up whatever you want, but anything that doesn't pass my test can't replace my own generator in its place. Remember : it got used exactly like in the test, hence the test is perfectly valid to check whether another method would fit in its place.

Originally Posted by Thorham

That is complete none sense meynaf, I'm not that sort of person

You looked alike anyway.

Originally Posted by Thorham

I've made an image based on the output of this test using your method, and it's patterned as you can see in here: Attachment 26211. Of course I simply let the seed count in the normal way.

Ok, you've shown an image. Now show the code that produces it.

Originally Posted by Thorham

As you've seen it is patterned. Furthermore, this is a bad practice.

I've seen an image which isn't proof that this method was used. Show you code, then we'll talk.

Originally Posted by Thorham

Just generate a table, and use different parts of the table. Much easier, and a million times better.

A table is too limited for that. It's not a million times better, but it can easily end up a million times larger - not to mention giving more complex code.

Originally Posted by Thorham

It is necessary, you can't expect something to work properly if it's used in the wrong way. This is why your test is bogus.

I was not the one who said the other methods were better than mine. Yes, it proves they're not usable like that, which is obvious and you know it full well. So please stop telling they're better than mine, because it's simply not the same usage field !

And please do an asm test yourself, instead of adding more of your quibbles here. Would be much more useful.

Originally Posted by Thorham

Saved states are crucial in the proper functioning of PRNGs. Rock hard fact that's widely known.

You're saying that without any proof. Pointers please. And don't forget about save state compromise attacks in cryptography.

Originally Posted by Thorham

The PRNGs are not poor. You base this on improper use of those algorithms, and therefore your test fails.

They are poor, which is obvious for many of them by just looking at their code ; but it's not the purpose anyway. The problem is just that they can't replace my own generator in the program where it got used. Period.

Originally Posted by Thorham

You mean ADDs and ROLs. I don't use EOR. ROLs and ADDS make things very irregular, too.

MULs make things even more irregular. Now look : i just use MUL, ADD, ROL (or ROR). And your "simple" methods seem to be quite quickly done. Why, you didn't even provide an initialisation routine for their state.

Originally Posted by Thorham

It's a known fact that reseeding a PRNG before every call is a bad practice, it's not my idea.

If it's not yours, then whom is it ?

Originally Posted by Thorham

If you had performed the graphical test on your own data, then you'd know that it's patterned.

*sigh* I will perform it if you want. But the period used in these tests is much larger than what my land needed so it's not very relevant. Furthermore, it may be patterned, but it's less patterned than the others, right ?

Originally Posted by Thorham

Again, this is a hard fact, and not my idea.

If this is hard fact, show pointers.

Originally Posted by Thorham

It's a complete necessity.

Not in this case. You would save something you don't reuse.

Originally Posted by Thorham

No, I don't hate it. If you think that I'm that kind of person, then you've got me all wrong.

What i know about you is that you're quite often making claims about things you know zilch about.

Originally Posted by Thorham

Then yours is bad, too, as I've shown.

Perhaps it's bad, but at least it did its job quite nicely where the others wouldn't have done it good at all.

Originally Posted by Thorham

I deem them unnecessary, although George Marsaglia (mathematician, random expert) has written a very good PRNG that uses multiplies. It's called 'multiply with carry'.

Good old George ! So he knows that it's necessary to use operations that can't be reversed, f.e. some kind of modulus. A multiply does that. Eors, adds, and rotates don't.

Now please change your "unnecessary". Tell it : you see muls as "evil"

Originally Posted by Thorham

The bottom line is that PRNGs don't work properly (including yours as I've shown), if you reseed before every call. This is known to be a very bad practice. A PRNG isn't bad just because it doesn't work when it's misused in this way.

And this is known by whom, apart yourself ?

Originally Posted by Thorham

Even the very high quality Mersenne Twister (of which only a part has been posted in this thread previously) will fail your test miserably, because it needs a good initial seed, and it it needs all of it's state information saved. Here is the whole algorithm in pseudo code:
(...)
You may want to read a bit about it here: http://en.wikipedia.org/wiki/Mersenne_twister.

This is what i call using a tank to go shopping.

Originally Posted by Thorham

Basically, you're going against known facts. Your test shows nothing, and I have no problem with you telling me that my PRNGs are poor based on your test, because I know better than that. What I do care about is that a smart guy like you doesn't want to accept those facts as the truth

These aren't "known facts". Those are your facts. And "known" doesn't mean "true" either.

I think there is a little bit of misunderstanding in here, so it's time to clear it. Once and for all, my timerless method isn't designed to be a generic PRNG, it's made for my particular case of a dungeon generator.
You told that other methods were better, but for what it gets used they are not. My test shows why.

Now i'm not saying it would be a good generic method, there is another one for that. I'm also not saying my test is an absolute one, even though you (on purpose ?) nicely ignored that my timer-reading method also passes the test quite nicely.

Originally Posted by Maccara

Meynaf, you have not only shown that you don't even know what a pseudorandom number generator means, but also that you don't understand statistics or probability.

This is personal attack, typical of those who have nothing interesting to say. Shut up now, or next time i won't bother to answer but just report to the moderator.

Originally Posted by Maccara

Your claims and tests are utter crap, and you seriously need to do some basic reading on number theory & probability before venturing any further as currently you're only digging yourself deeper with every claim.

But of course.

What you're saying here is just bashing. Perhaps you feel like trolling, who knows. When this kind of personal attack comes, we see who's right and who's wrong.

Originally Posted by Maccara

This is becoming "rather silly".

And you've just added another layer on top of it. Congratulations.

Originally Posted by Don_Adan

Are you sure? For me this is difference between theory (like you) and practice (like meynaf).

Exactly. They talk, talk and talk again, about something they never actually experienced themselves with concrete applications.

Originally Posted by Maccara

Well, I know little bit of theory and practice. Using the tools wrong on purpose and then blaming the tools is not the way to go, not in theory or practice.

Someone said these tools were better than mine. So i had to prove they couldn't be used in its place. Easy or not ?

[Thorham]

Originally Posted by meynaf

They don't scramble much because they don't alter all bits. A multiply does change all bits and, due to the modulus that's implied, it also is a non-reversible operation. EORs are just good to mix several randoms together.

Your point?

Originally Posted by meynaf

Still totally irrelevant to me. Add some timer reads, and you'll no longer loop.

Great, now you have a PRNG that needs timers to not have a short period. My six and four line algorithms have a much larger period without hardware state.

Originally Posted by meynaf

But ADD still doesn't move bits around very much, nor does it mix them enough.

In combination with rotate it preforms just fine.

Originally Posted by meynaf

Look up whatever you want, but anything that doesn't pass my test can't replace my own generator in its place. Remember : it got used exactly like in the test, hence the test is perfectly valid to check whether another method would fit in its place.

What I want to know is what the purpose is of selecting random bits in the way you do? Seems to me that there are easier and better ways to do this...

Originally Posted by meynaf

You looked alike anyway.

Eh, no.

Originally Posted by meynaf

Ok, you've shown an image. Now show the code that produces it.

Here's the code is used with your test program:

method equ 0


start
	lea	out,a0

	move.l	#128*1024,d7
	moveq 	#1,d1			; on fait de 1 à 64
.loop
	bsr.s	euh
	move.l	d6,(a0)+
	bsr.s	euh
	move.l	d6,(a0)+
.next
	subq.l	#1,d7
	bne	.loop

	rts

The image is made by plotting 256x256 gray pixels (0->255) based on every consecutive byte in the produced data: byte 0=pixel(0,0), byte 1=pixel(1,0) and so forth.

However, I discovered that I put moveq #1,d1 inside the table gen loop for the image I've shown you So I've corrected it now. It's still highly patterned, and certainly not random. Image here: rndout_corrected.zip

Originally Posted by meynaf

I've seen an image which isn't proof that this method was used. Show you code, then we'll talk.

Oh man, why the hell would I bloody fake this

Originally Posted by meynaf

A table is too limited for that. It's not a million times better, but it can easily end up a million times larger - not to mention giving more complex code.

Well, I still don't have a clue about the reason you want to use a method like this.

Originally Posted by meynaf

I was not the one who said the other methods were better than mine. Yes, it proves they're not usable like that, which is obvious and you know it full well.

Eh, yes I know that, and I don't care, because why would I want to use them in such a way?

Originally Posted by meynaf

So please stop telling they're better than mine, because it's simply not the same usage field !

No, they're not, but yours isn't particularly good, either. With what you're doing in your PRNG, the results simply can't be good.

Originally Posted by meynaf

And please do an asm test yourself, instead of adding more of your quibbles here. Would be much more useful.

There are three tests I use:

. Plotting pixels in a 256x256 grid where each pixel gets a random gray value.
. Plotting white pixels in a 256x256 grid where the coordinates for each pixel are random.
. Marsaglia's Diehard test suite of 15 tests.

I don't need any more tests for testing general purpose routines.

Originally Posted by meynaf

You're saying that without any proof. Pointers please. And don't forget about save state compromise attacks in cryptography.

If they weren't crucial, none of the existing generators would bother with saving seed state. You'd know this if you had looked into it yourself, which is as easy as looking up some existing generators. Also, crypto PRNGs also use seed states.

Originally Posted by meynaf

They are poor, which is obvious for many of them by just looking at their code

My six and four line algorithms aren't poor, or they wouldn't get through the Die hard test suite very well. They pass these test quite reasonably, which means they're reasonably good.

Originally Posted by meynaf

; but it's not the purpose anyway. The problem is just that they can't replace my own generator in the program where it got used. Period.

That's not a great loss to me. It's not as if the method that your test employs is actually necessary for anything (and if it is, explain why).

Originally Posted by meynaf

MULs make things even more irregular. Now look : i just use MUL, ADD, ROL (or ROR). And your "simple" methods seem to be quite quickly done. Why, you didn't even provide an initialisation routine for their state.

I've only shown the core algorithm. The states aren't read, nor are they saved, seemed obvious to me. Here's the six liner (yes, it's still six lines, because it can be used inside loops in that form) with full seed state handling (principal is the same for the less good four line algorithm):

;------------------------------------------------------------------------------
rnd.gen		;Generates PRND numbers with a maximum period of 2^96.
;		;Has to bee seeded.
;
;		;out	d0=32 bit PRND number.
;------------------------------------------------------------------------------
	movem.l	d1-d2/a0,-(sp)

	lea	rnd.gen.seed,a0

	move.l	(a0)+,d0
	move.l	(a0)+,d1
	move.l	(a0),d2
	
	rol.l	#7,d0
	add.l	d0,d1
	rol.l	#7,d1
	add.l	d1,d2
	rol.l	#7,d2
	add.l	d2,d0
	
	move.l	d2,(a0)
	move.l	d1,-(a0)
	move.l	d0,-(a0)

	movem.l	(sp)+,d1-d2/a0
	rts
;------------------------------------------------------------------------------

As for the seeding, you can use any good seeding algorithm to seed the three 32 bit seeds used in here. I use this one, which is based on hardware state. Seems to be good based on the output I've seen it generate, and is also tested with Diehard (passes):

;------------------------------------------------------------------------------
rnd.seed	;Generates custom length seeds based on hardware state.
;		;Should not be used to re-seed the PRNGs, because it seeds from
;		;scratch (all states are overwritten and seeder state is
;		;cleared). Use rnd.reseed for that.
;		;Seed state is saved (for the re-seeder).
;
;		;in	d0=seed size in long words.
;		;	a0=pointer to seed.
;------------------------------------------------------------------------------
	movem.l	d0-d3/d5-d7/a0-a1,-(sp)

	move.l	d0,d7
	moveq	#0,d0
	moveq	#0,d1
	moveq	#0,d2
	moveq	#0,d3
.loop
	move.l	$dff006,d5
	move.b	$bfe601,d6
	lsl.l	#8,d6
	move.b	$bfe701,d6
	lsl.l	#8,d6
	move.b	$bfe801,d6
	lsl.l	#8,d6
	move.b	$bfd800,d6

	add.l	d5,d0
	rol.l	#7,d0
	add.l	d0,d1

	add.l	d6,d1
	rol.l	#7,d1
	add.l	d1,d2

	add.l	d5,d2
	rol.l	#7,d2
	add.l	d2,d3

	add.l	d6,d3
	rol.l	#7,d3
	add.l	d3,d0

	move.l	d0,(a0)+
.next
	subq.l	#1,d7
	bne	.loop

	lea	rnd.seed.state,a1
	movem.l	d0-d3,(a1)

	movem.l	(sp)+,d0-d3/d5-d7/a0-a1
	rts
;------------------------------------------------------------------------------

Could have some small bugs in them, probably not

The seeder saves it's own seed state, because there's also a re-seeding algorithm (rnd.reseed). It uses the same method as this one, except that it uses the state generated by rnd.seed and it also uses the PRNGs existing state instead of overwriting it. It's used by periodically calling it to randomize the PRNG state further based on part of the hardware state (instead of just overwriting everything). The reseeder can be called before every PRND call, but it's better to do it far less frequently. This works because none of the sates are overwritten by it.

Originally Posted by meynaf

If it's not yours, then whom is it ?

I've read this quite a few times online, but it also seems that not using the PRNGs seed state to it's fullest means that you're not using the generator properly. Your test clearly shows this for your own generator.

Originally Posted by meynaf

*sigh* I will perform it if you want. But the period used in these tests is much larger than what my land needed so it's not very relevant. Furthermore, it may be patterned, but it's less patterned than the others, right ?

It's shouldn't be patterned at all, because it proves you're using your own generator in the wrong way, or that it's not well designed for the task at hand. It too can't handle this kind of reseeding very well. That's why I want to know exactly why it's necessary to use such a bad practice. Basically the problem is that you can't (perhaps ), or it's difficult (much more likely ), to generate randomness when you use a simple counter as your seed.

Originally Posted by meynaf

If this is hard fact, show pointers.

How can you expect that something will work properly when it's used in the wrong way? I've already said that PRNGs rely on saving their seed state, or they'll fail. Simple as that, and your test clearly shows it.

Originally Posted by meynaf

Not in this case. You would save something you don't reuse.

Yes, in this case, too, because the generators can't work properly without them.

Originally Posted by meynaf

What i know about you is that you're quite often making claims about things you know zilch about.

And at least I'm willing to admit that I'm wrong when I'm wrong. In this case I've actually done my homework, so here I do know what I'm talking about. You don't even know that PRNGs shouldn't be reseeded before every call, and you also don't know that PRNGs depend on their seed state to work properly. Says enough, really.

Originally Posted by meynaf

Perhaps it's bad, but at least it did its job quite nicely where the others wouldn't have done it good at all.

It doesn't do it's job well, because you're using your own PRNG in the wrong way. Why you would even do it like this is beyond me.

Originally Posted by meynaf

Good old George ! So he knows that it's necessary to use operations that can't be reversed, f.e. some kind of modulus. A multiply does that. Eors, adds, and rotates don't.

Eh, what's wrong with reversibility? I've read up on it a little, and it only seems that when it's reversible, it has a longer period. Also, who says that multiplies aren't reversible?

Originally Posted by meynaf

Now please change your "unnecessary". Tell it : you see muls as "evil"

I don't like them, and I don't need them for this.

Originally Posted by meynaf

And this is known by whom, apart yourself ?

Everyone who knows what they're talking about.

Originally Posted by meynaf

This is what i call using a tank to go shopping.

At least it's very good and quite fast.

Originally Posted by meynaf

These aren't "known facts". Those are your facts. And "known" doesn't mean "true" either.

They are know facts, which you would have known if you knew what you're talking about.

Originally Posted by meynaf

I think there is a little bit of misunderstanding in here, so it's time to clear it. Once and for all, my timerless method isn't designed to be a generic PRNG, it's made for my particular case of a dungeon generator.

Okay, but that still doesn't mean it's not good at what it's supposed to do.

Originally Posted by meynaf

You told that other methods were better, but for what it gets used they are not. My test shows why.

The whole method is lousy if you ask me.

Originally Posted by meynaf

Now i'm not saying it would be a good generic method, there is another one for that. I'm also not saying my test is an absolute one, even though you (on purpose ?) nicely ignored that my timer-reading method also passes the test quite nicely.

Just about any timer based PRNG will do that. But you can't use them if you want the same result for the same seed every time.

Originally Posted by meynaf

Exactly. They talk, talk and talk again, about something they never actually experienced themselves with concrete applications.

Except that you don't even know the basic facts about seed states and reseeding before every call.

[Maccara]

Meynaf, sorry if my post felt like a personal attack, but it was only meant to address your "test methodology" and the qualities of your claims. For that it was an accurate assessment. (Edit: I re-read my post and I indeed wrote it as a personal attack. Sorry.)

You slant other prng based simply on your flawed testing, which your generator happens to pass. That's clear bias from you.

The other generators obviously failed because they were not designed for your kind of test at all and you used them incorrectly. Simple as that. Doesn't tell anything about the actual qualities of the other generators or yours.

Originally Posted by meynaf

Exactly. They talk, talk and talk again, about something they never actually experienced themselves with concrete applications.

I've had to implement a few random generation algorithms (for Monte Carlo simulation) and while doing that, I needed to do resonable research on the subject to not to fall into the common pitfalls while implementing them. From that I know the implementation is rarely as straightforward as it first seems (due to available bits how easy it is actually run into pigeon-hole issues with mod and so on, when you need scaled output etc etc).

The least you could do is read the documentation for the other algorithms how to use them properly before claiming anything on them. (for example, they usually specifically say you're not to reseed them for each call)

Someone said these tools were better than mine. So i had to prove they couldn't be used in its place. Easy or not ?

Not exactly. You only showed they couldn't be used as a direct replacement in your specific use case due to how you have designed your own algorithm (which is not exactly a pseudo random number generator, as it isn't exactly deterministic - which also makes it quite useless for many research purposes where verifiability/repeatability of results/methods is a criteria - but you addressed this so that's not an issue).

Implemented properly they could be used instead of your algorithm.

That said, I haven't analyzed your algorithm so I can't comment if it has any obvious flaws or not. Obviously, it works better for your specific needs as is, but you still can't claim it is generally better than anything else, especially based on that one premise. With certain strict qualifiers, your algo "beats" the other generators, but is not necessarily any better.

Your generator breaks if it is called in a tight loop. You addressed this and said it is not designed to be used like that. Fine. Show the same courtesy towards other generators before you claim yours is better or others are flawed.

Note that prngs' have the property (not a flaw) that if you give them the same seed, you will always get the same sequence of numbers. If you want to use them as "true random" simulators, you need be careful how you implement them.

Prng purpose is only to give a sequence that is sufficiently indistinguishable from true random sequence. If you call them repeatably with the same seed (while losing the state) you obviously lose this and turn them into constant number generators - i.e. useless.

If you claim that is a flawed concept, that's your problem (if you actually find reputable sources saying otherwise, please provide them). You do realize pseudo random numbers predate computers? (first "official" tables were published in the twenties or early thirties, iirc) So your opinion on how they should/shouldn't work is pretty much irrelevant.

[Maccara]

@Thorham

I think you need to take one distinction in account with prng vs "true" random generators. Periodicity. You have tried to address this, but I think you might need to find a little bit more info on this (if you're willing to do some more digging).

For prng, it is extremely important to know the period it will repeat (as you have noted), but for "true" rng (which meynaf's implementation is supposed to be) this concept doesn't apply exactly the same way - it shouldn't repeat at all. Sorry, I don't have good sources on hand for this distinction, as I have dealt mostly with prngs' only (execution speed in a loop has been critical, and "true" generators are not usually suitable for that).

My personal understanding is that even for "true" generators, the underlying algorithm long period is preferrable, but don't quote me on that - try to find a source to back up that claim and asses what the significance is.

It is still worthwhile to examine the algorithm without the "true" random source (cia timers in this case) to determine if the underlying algorithm has an extremely short period (what is extremely short? needs sources) or if it has significant bias which might exhibit as a problem with the random distribution even with the "true" source included. However, it is not enough to just note this but needs to be analyzed in context with the random source too. (for example after determining there is a significant bias, run without timers and collect data and then run with timers and see if there's a significant correlation - does not prove anything definitely but will be a clear indication if there's something warranting a more detailed inspection)

Even if you can prove those flaws it does not automatically mean it will result in bad sequences when the "true" source is included. This is where the "entropy extraction" comes in and analysis of it.

Also, when you test a rng algo, try to make sure you don't accidentally cause bias. Simple truncation can be "dangerous".

My personal view is that it is overkill to use "true" random numbers unless you really need them (because they're usually hard to get right and slow and do not give significant benefits apart from special needs like cryptography). I guess that's the POV you're driving at also?

[Thorham]

Originally Posted by Ed Cruse

A Fourier transform is pretty cool. You can take any data like audio or PRNG and do a forward Fourier transform and get a frequency versus amplitude curve. Basically all signals are made up of sine waves of different amplitudes and phases, and when added together make up your original signal. This is how digital filters work. As an example you take an audio signal convert it to a frequency verses amplitude spectrum with a forward Fourier transform and then you can go in and change the amplitude of any frequency to any amplitude. Do a reverse Fourier transform and generate the new signal, as if it was an analog signal that just got processed by an analog filter.

That is very interesting, thanks for explaining Might be very interesting to see what this does with PRNG data and 'semi TRND' data, as well.

Originally Posted by Ed Cruse

The source codes are in the zone, C and assem. I found a print out of CRCs in general that came from Wikipedia. The title is "Cyclic redundancy check". It appears I'm using the same CRC32 that's used by Ethernet, FDDI, PKZip, WinZip, and PNG. It appears to be "CRC32 IEEE 802.3". I haven't found the information for doing CRCs in general. The method I'm using uses a lookup table which makes it much faster. In the source codes "CRC32open.c" creates the table and deallocates it. Rndgen.asm does the actual CRC32 calculations.

Thanks, I'll have a go at it

Originally Posted by Ed Cruse

I did all this years ago so I may have difficulty finding the info. Study the sources which is what I originally did with the sources I found on the internet.

Sure, no problem

Originally Posted by Maccara

You slant other prng based simply on your flawed testing, which your generator happens to pass. That's clear bias from you.

His own generator which he made specifically for this, doesn't even pass it very well, although it seems to have an easy fix.

Originally Posted by Maccara

The other generators obviously failed because they were not designed for your kind of test at all and you used them incorrectly. Simple as that. Doesn't tell anything about the actual qualities of the other generators or yours.

He also said that he could see the generators are poor based on how the source code looks (yes, no testing needed!)...

Originally Posted by Maccara

I think you need to take one distinction in account with prng vs "true" random generators. Periodicity. You have tried to address this, but I think you might need to find a little bit more info on this (if you're willing to do some more digging).

It sure couldn't hurt to read more on this subject, because it's not actually as straightforward as it may seem at first.

Originally Posted by Maccara

For prng, it is extremely important to know the period it will repeat

That's not going to be easy for me with those ROL+ADD PRNGs, my six line and four line algorithms have a 96 bit seed state, and I've made one with a whopping 8192 bit seed state! I have no clue about how test the period for this kind of stuff

Originally Posted by Maccara

but for "true" rng (which meynaf's implementation is supposed to be) this concept doesn't apply exactly the same way - it shouldn't repeat at all.

Actually, it's about his dungeon generator PRNG, which accepts a value, and randomizes it, and then outputs the same value for the same input value. It's basically a stateless PRNG of sorts.

Originally Posted by Maccara

My personal understanding is that even for "true" generators, the underlying algorithm long period is preferrable, but don't quote me on that - try to find a source to back up that claim and asses what the significance is.

I can see how. If you don't handle the TRNGs out out properly, and use something with a very short period, like the lower bits of an LCG, then you're definitally going to get into trouble.

Originally Posted by Maccara

It is still worthwhile to examine the algorithm without the "true" random source (cia timers in this case) to determine if the underlying algorithm has an extremely short period (what is extremely short? needs sources)

I've done it, but's it's quite a few posts ago. I say that extremely short would be a couple of hundred thousand bytes or less, although a few million isn't very large, either. In fact, a 32 bit seed is usually seen as too short.

Originally Posted by Maccara

or if it has significant bias which might exhibit as a problem with the random distribution even with the "true" source included.

Hard to test, because the short period prevents testing with the Diehard test suite (G. Marsaglia), because it wants a 10 MB file. The PRNGs period is way too short for that.

Originally Posted by Maccara

However, it is not enough to just note this but needs to be analyzed in context with the random source too. (for example after determining there is a significant bias, run without timers and collect data and then run with timers and see if there's a significant correlation - does not prove anything definitely but will be a clear indication if there's something warranting a more detailed inspection)

What I do is simple: Come up with some algorithm and see what the data looks like (first plot the data as gray scale pixels in a grid, and after that use the data as x,y,z cords and plot white pixels). If it looks random, just test with the Diehard suite. If it isn't good enough, tweak and try again. Did it with my four liner and six liner and it seems to work well (they don't have to be the best, just good is good enough).

Originally Posted by Maccara

Even if you can prove those flaws it does not automatically mean it will result in bad sequences when the "true" source is included. This is where the "entropy extraction" comes in and analysis of it.

He he, I'm doing something really simple for this, see source code in my last post. Seems to work just fine (tested).

Originally Posted by Maccara

Also, when you test a rng algo, try to make sure you don't accidentally cause bias. Simple truncation can be "dangerous".

Very true. Not all generators produce output of which all bits can be used. LCGs are a prime example of this (lower bits are useless, stick to the high ones). Another pitfall is the use of MOD, which creates bias.

Originally Posted by Maccara

My personal view is that it is overkill to use "true" random numbers unless you really need them (because they're usually hard to get right and slow and do not give significant benefits apart from special needs like cryptography). I guess that's the POV you're driving at also?

Not entirely. 'semi TRNGs' can be used to seed a PRNG, and they can also be used to add further unpredictability to a PRNG. The seeding algorithm in my previous post also has a variant which can be used to reseed a PRNG. It works by having the seeder keep it's state. It then uses this state together with the PRNGs existing to state to randomize it. This is different from the original seeder, because that starts with a cleared state, and overwrites the PRNGs state.

The reseeder might not be that useful, but a seeder really needs to try and be a TRNG (or better, a 'semi TRNG).

I hope I made some sense here