random number generation (in asm)

[Thorham]

Originally Posted by pandy71

Amiga and input of sound card?

More generally speaking. On an Amiga you can easily use a parallel port sampler.

Originally Posted by pandy71

FM noise is not always random (some interferences can be quite regular)

Yes, care must be taken to get clean noise. Often possible, and very cheap.

Originally Posted by pandy71

Most modern FM receivers do auto-mute

Yes, but I mean cheap world receivers with completely manual tuning and no mute. These are great for this purpose.

[pandy71]

So if You adding some hardware and software maybe it is better to use something like this https://secure.wikimedia.org/wikiped...latform_Module

[Thorham]

Originally Posted by pandy71

So if You adding some hardware and software maybe it is better to use something like this https://secure.wikimedia.org/wikiped...latform_Module

The problem with a chip like that is that you have to make a board that plugs into the Amiga, and even if there is some serial or parallel device ready for use, you still need a driver. The software for processing clean radio static is simpler. Also, the sampler+radio solution is probably much cheaper.

[pandy71]

Originally Posted by Thorham

The problem with a chip like that is that you have to make a board that plugs into the Amiga, and even if there is some serial or parallel device ready for use, you still need a driver. The software for processing clean radio static is simpler. Also, the sampler+radio solution is probably much cheaper.

As always - software is the problem - and cheaper sampler + radio - don't think so...

[Thorham]

Originally Posted by pandy71

As always - software is the problem

Yes, but driver software is probably less easy than a radio static processing program.

Originally Posted by pandy71

- and cheaper sampler + radio - don't think so...

Okay, the radio is cheap, but isn't the sampler going to be quite cheap, too? You don't need the best sampler, probably any will do.

It's also about ease of use: Are those specialized solutions easy to connect to an Amiga and cheap?

[pandy71]

most of them use something like I2C or SPI bus so connection to any computer shall be not a problem (as a dongle or something similar)

btw - AVR uC (or some simple ARM like Cortex M3) can be used as a quite decent sampler for audio (usually 10 bit ADC with some limited DSP capabilities, buffering etc) - for 15$ ARM with embedded Ethernet can be nice solution for small Amigas - even TCP/IP stack can run on ARM which mean 32 bit 40 - 75MIPS CPU that offload all that network stuff from MC68K... i can made hardware but i'm not a programmer...

[meynaf]

Originally Posted by Thorham

Sure, but the best cryptographic algorithms are currently not hackable on a practical level (takes too long to be of any use).

Depends of your computing power. Governments probably have enough.

Originally Posted by Thorham

That sucks, but can't you at least use the math libs for float?

It's just c code using floats. Damned slow, perhaps can't even compile on my machine.

Originally Posted by Thorham

Not from what I've seen, it seems to work fine without the timers. About that dungeon generating PRNG, could you post it, if you want?

Well, i'm not so confident without timers, this is why i put an additionnal add/mul step in the dungeon PRNG.

So here it is anyway :

; d1=seed, d0=modulo -> d0=number
pseudornd
 movem.l d1-d3,-(a7)
 move.l #$59fa769f,d3
 mulu.l d3,d2:d1
 add.l d2,d1
 addi.l #$4a5be017,d1
 rol.l #7,d1
 move.l #2513894743,d3
 mulu.l d3,d2:d1
 eor.l d2,d1
 addi.l #$a5a5a5a5,d1
 ror.l #7,d1
 moveq #0,d2
 divu.l d0,d2:d1
 move.l d2,d0
 movem.l (a7)+,d1-d3
 rts

Not quite fast perhaps, but again it won't have to generate THAT many numbers. And it is fast if you have fast MUL.

Originally Posted by Thorham

Depends on the game

I don't think so. More precisely, i can't see any game in which the speed of the random generator is of any importance. It's a dwarf as compared to any AI code.

Originally Posted by Thorham

Okay, but this example still is really slow, although it's a good example of how something may look random while it's not in any way random at all.

It IS random, despite what you think.

Originally Posted by Thorham

They're the handiest, until you need true random numbers

Good pseudo random is indistinguishable from true random.

[Thorham]

Originally Posted by meynaf

Depends of your computing power. Governments probably have enough.

Some are supposed to be practically unbreakable with todays computing power (that is, it would take too long to crack, and is therefore not practically usable).

Originally Posted by meynaf

It's just c code using floats. Damned slow, perhaps can't even compile on my machine.

It will compile with a compiler that uses the math libs for floating point math. Also, can't you convert to integer somehow, or is it not possible? Which tests did you look at?

Originally Posted by meynaf

Well, i'm not so confident without timers, this is why i put an additionnal add/mul step in the dungeon PRNG.

So here it is anyway :

...

Not quite fast perhaps, but again it won't have to generate THAT many numbers. And it is fast if you have fast MUL.

Nope, not fast at all Anyway, your other one is probably more than sound enough without timers, this seems like overkill.

Originally Posted by meynaf

I don't think so. More precisely, i can't see any game in which the speed of the random generator is of any importance. It's a dwarf as compared to any AI code.

Perhaps not, but making a reasonably good PRNG that's really fast is just cool.

Originally Posted by meynaf

It IS random, despite what you think.

No, it is most certainly not. Lossless compressed data is exactly the same as it's non compressed counter part, except for the form. Compressed data is not random. It may look random, but it's not. If you'd decompress truely random data, you'd end up with rubbish data.

Originally Posted by meynaf

Good pseudo random is indistinguishable from true random.

At the surface, yes. The difference is that psuedo random data always has a pattern that can be reproduced. True random data doesn't have this apparently.

[Maccara]

Originally Posted by Thorham

At the surface, yes. The difference is that psuedo random data always has a pattern that can be reproduced. True random data doesn't have this apparently.

Mersenne twister is a good example of this. Excellent PRNG with good statistical properties but utterly useless in cryptography or anything requiring "true" random data (you only need to observe ~600 cycles, depending on implementation, to "hack it").

[Leffmann]

Originally Posted by meynaf

; d1=seed, d0=modulo -> d0=number
pseudornd
 movem.l d1-d3,-(a7)
 move.l #$59fa769f,d3
 mulu.l d3,d2:d1
 add.l d2,d1
 addi.l #$4a5be017,d1
 rol.l #7,d1
 move.l #2513894743,d3
 mulu.l d3,d2:d1
 eor.l d2,d1
 addi.l #$a5a5a5a5,d1
 ror.l #7,d1
 moveq #0,d2
 divu.l d0,d2:d1
 move.l d2,d0
 movem.l (a7)+,d1-d3
 rts

It IS random, despite what you think.

But have you run some good tests on its output? It looks over-engineered and seems to be dependant on randomized input every time you call it, which is in a way self-contradictory for a PRNG. Making use of unpredictable input, such as CIA timer counters, is good, but it doesn't necessarily mean the algorithm has good statistical properties.

Any chance you could generate some sets of 10 Mb each from typical use cases and upload somewhere?

[meynaf]

Originally Posted by Thorham

Some are supposed to be practically unbreakable with todays computing power (that is, it would take too long to crack, and is therefore not practically usable).

They are supposed to be like that. But the maths behind often makes them more frail than they look (breaking them is just a matter of large number factorization).

Originally Posted by Thorham

It will compile with a compiler that uses the math libs for floating point math. Also, can't you convert to integer somehow, or is it not possible? Which tests did you look at?

You can see all this by yourself quite easily :
http://stat.fsu.edu/pub/diehard/
http://www.csis.hku.hk/cisc/download/idetect/
http://www.webalice.it/cristiano.pi/rabigete/
http://www.jstatsoft.org/v07/i03/

Originally Posted by Thorham

Nope, not fast at all Anyway, your other one is probably more than sound enough without timers, this seems like overkill.

It gave good results without much slow down, if any. If you want to see its work, fire up the little tile map proggy i gave you earlier and try to find a large area. It got used there.

Originally Posted by Thorham

Perhaps not, but making a reasonably good PRNG that's really fast is just cool.

I know of no example where speed is a real problem, f.e. Captive worked fast on 68000 despite it had to generate all its dungeons in this way.

Originally Posted by Thorham

No, it is most certainly not. Lossless compressed data is exactly the same as it's non compressed counter part, except for the form. Compressed data is not random. It may look random, but it's not. If you'd decompress truely random data, you'd end up with rubbish data.

Anyway if you look at some compressed data, you won't be able to tell it's not random.

Originally Posted by Thorham

At the surface, yes. The difference is that psuedo random data always has a pattern that can be reproduced. True random data doesn't have this apparently.

If that pattern is long enough, it may take a whole life to actually see it...

Originally Posted by Leffmann

But have you run some good tests on its output? It looks over-engineered and seems to be dependant on randomized input every time you call it, which is in a way self-contradictory for a PRNG. Making use of unpredictable input, such as CIA timer counters, is good, but it doesn't necessarily mean the algorithm has good statistical properties.

The code you quoted is for dungeon generation and things like that, that is, it must have same output for same initial seed.
I've posted my "normal" code earlier in this thread, and it uses timers.

Originally Posted by Leffmann

Any chance you could generate some sets of 10 Mb each from typical use cases and upload somewhere?

As i gave the code, you can do it whenever you want. You don't need me

[Leffmann]

Originally Posted by meynaf

The code you quoted is for dungeon generation and things like that, that is, it must have same output for same initial seed.
I've posted my "normal" code earlier in this thread, and it uses timers.

As i gave the code, you can do it whenever you want. You don't need me

If it needs a new random seed for each call then how do I get this random seed in the first place? It seems to be dependant on another PRNG, ad infinitum. And if it relies on data from the timers then at what rate and regularity should you call it?

Typically a PRNG is self-contained and you only seed it/set its internal state once for the lifetime of your application. I'm just not sure of what input to give your algorithms to make them behave as intended.

My 3-line algorithm in my first post passes half of the Diehard tests and fails miserably on the other half, and I think this is the case of most if not all homemade PRNGs. They work for most stuff but they're far from truly random, and chances are they will eventually stall or short circuit.

Added complexity doesn't always mean better either. Just for comparison here's one of the Xorshift algorithms Lionheart linked to. It has a period of 2^64-1, which is probably more random numbers than have been generated by all Amigas in total since their birth in 1985, and it passes all of the Diehard tests:

PRNG      movem.l   .state(pc), d0-d1

          move.l    d0, d2
          lsl.l     #2, d0
          eor.l     d2, d0           ; T = A^(A<<2)

          move.l    d1, d2
          lsr.l     #3, d2
          eor.l     d1, d2           ; B^(B>>3)

          eor.l     d0, d2           ; B^(B>>3)^T
          lsr.l     #7, d0
          eor.l     d0, d2           ; B^(B>>3)^T^(T>>7)

          movem.l   d1-d2, .state
          rts                        ; return random number in D2

.state    ds.l      2                ; initialize once to non zero

[Thorham]

Originally Posted by meynaf

They are supposed to be like that. But the maths behind often makes them more frail than they look (breaking them is just a matter of large number factorization).

Yes, but they often use large prime numbers, and factoring those is not always so easy. In the end, anything that is isn't truly random can be broken, but it can be very difficult and unpractical.

Originally Posted by meynaf

You can see all this by yourself quite easily :
http://stat.fsu.edu/pub/diehard/
http://www.csis.hku.hk/cisc/download/idetect/
http://www.webalice.it/cristiano.pi/rabigete/
http://www.jstatsoft.org/v07/i03/

Thanks, I'll have a look at those

Originally Posted by meynaf

It gave good results without much slow down, if any. If you want to see its work, fire up the little tile map proggy i gave you earlier and try to find a large area. It got used there.

Okay, I can do that.

Originally Posted by meynaf

I know of no example where speed is a real problem, f.e. Captive worked fast on 68000 despite it had to generate all its dungeons in this way.

Sure, but that doesn't mean that finding a small, fast algorithm that's good isn't cool

Originally Posted by meynaf

Anyway if you look at some compressed data, you won't be able to tell it's not random.

If you only look at the data with the naked eye that's certainly true, but it still isn't random at all.

Originally Posted by meynaf

If that pattern is long enough, it may take a whole life to actually see it...

Again, with the naked eye this is certainly the case, however, when you use better methods than the naked eye this is no longer true.

Originally Posted by Leffmann

PRNG      movem.l   .state(pc), d0-d1

          move.l    d0, d2
          lsl.l     #2, d0
          eor.l     d2, d0           ; T = A^(A<<2)

          move.l    d1, d2
          lsr.l     #3, d2
          eor.l     d1, d2           ; B^(B>>3)

          eor.l     d0, d2           ; B^(B>>3)^T
          lsr.l     #7, d0
          eor.l     d0, d2           ; B^(B>>3)^T^(T>>7)

          movem.l   d1-d2, .state
          rts                        ; return random number in D2

.state    ds.l      2                ; initialize once to non zero

I've tried this algorithm in FreeBasic and it doesn't seem to work. Have you tested it? If so, I probably made a mistake somewhere.

[StingRay]

Originally Posted by Thorham

I've tried this algorithm in FreeBasic and it doesn't seem to work. Have you tested it? If so, I probably made a mistake somewhere.

You did initialize .state, didn't you?

[Thorham]

Originally Posted by StingRay

You did initialize .state, didn't you?

Yes, I did. This code probably just contains a bug.

Edit: Turns out I'm the one who made a mistake Basically I forgot to look at how the state is handled. Instead of saving d0 and d1 (which are the values that are read), the code saves d1 and d2 as a state Of course I assumed that d0 and d1 are saved

[meynaf]

Originally Posted by Leffmann

If it needs a new random seed for each call then how do I get this random seed in the first place? It seems to be dependant on another PRNG, ad infinitum. And if it relies on data from the timers then at what rate and regularity should you call it?

Please use the method with timers. The other one takes a simple hash made from coordinates and things like that to generate a random number. For using it otherwise you would have to save the number before the modulo is applied, and reuse it as next seed.

Originally Posted by Leffmann

Typically a PRNG is self-contained and you only seed it/set its internal state once for the lifetime of your application. I'm just not sure of what input to give your algorithms to make them behave as intended.

My regular method with timers has one routine to init the seed, and another one to generate the numbers. Nothing difficult in here.

But it is true that they're much easier to use in my system framework in which they normally lie.

Originally Posted by Leffmann

My 3-line algorithm in my first post passes half of the Diehard tests and fails miserably on the other half, and I think this is the case of most if not all homemade PRNGs. They work for most stuff but they're far from truly random, and chances are they will eventually stall or short circuit.

Added complexity doesn't always mean better either. Just for comparison here's one of the Xorshift algorithms Lionheart linked to. It has a period of 2^64-1, which is probably more random numbers than have been generated by all Amigas in total since their birth in 1985, and it passes all of the Diehard tests:

I wonder how you know something passes these tests or not. As far as i've seen in the sources, they never say "passed" or not.

Moreover, i don't trust these tests too much. Something that's perfectly statistically balanced can become more predictable because of that, and hence ceases to be random.

Originally Posted by Thorham

Yes, but they often use large prime numbers, and factoring those is not always so easy. In the end, anything that is isn't truly random can be broken, but it can be very difficult and unpractical.

Factorizing large primes is easy, it just takes time - and not as much as one might think.

The time it takes is in fact the square root of the maximum possible value, which in turn halves the number of bits. That is, you can do any 64-bit number in less than 4 billions of iterations. Unsafe maths if you ask me.

Said otherwise, you can break any 32-bit prime in less than 1 second even on unexpanded A1200.

Originally Posted by Thorham

Sure, but that doesn't mean that finding a small, fast algorithm that's good isn't cool

Well, use xorshift if you want that.

Originally Posted by Thorham

If you only look at the data with the naked eye that's certainly true, but it still isn't random at all.

Again, with the naked eye this is certainly the case, however, when you use better methods than the naked eye this is no longer true.

And what are "better" methods ? Most tests can be fooled with very simple algorithms.

[Leffmann]

Originally Posted by meynaf

I wonder how you know something passes these tests or not. As far as i've seen in the sources, they never say "passed" or not.

Moreover, i don't trust these tests too much. Something that's perfectly statistically balanced can become more predictable because of that, and hence ceases to be random.

You look at the output at the end of the tests. If you have many p-values at or close to 0.0 or 1.0 then this is an indication of a failed test.

I tested both your algorithms just now and the shorter one fails most of the tests. The timer-based algorithm failed about half of the tests in a first run, but in a second run where I called it at a slower rate it passed the tests really well.

It seems the guy who constructed the tests is a professor in statistics and has been studying in this field for over 25 years. I'm willing to take his opinion as law.

Anyway, I'm out. This thread has grown way too long already.

[Thorham]

Originally Posted by meynaf

Factorizing large primes is easy, it just takes time - and not as much as one might think.

Perhaps not anymore.

Originally Posted by meynaf

Well, use xorshift if you want that.

I think I'm going to use my latest PRNG. It seems to pass the Diehard tests and is very simple:

	add.l	d1,d0
	rol.l	#7,d0
	add.l	d2,d1
	ror.l	#7,d1
	add.l	d0,d2
	rol.l	#7,d2

D0 can be used as output.

Originally Posted by meynaf

And what are "better" methods ? Most tests can be fooled with very simple algorithms.

The visual test is simply not enough by itself, and more tests are needed, for example the Diehard test.

Edit: The problem with the visual test is that you can only see simpler patterns and very short periods. Also, data that isn't random at all, such as a compressed archive, will show as random while it isn't random at all. The visual test is just an indication of randomness in the end.

[Thorham]

I forgot to include the Diehard test results for my new simple algorithm, while I claimed it seems to pass this test, so here are the results: test10.txt

[meynaf]

Originally Posted by Leffmann

I tested both your algorithms just now and the shorter one fails most of the tests. The timer-based algorithm failed about half of the tests in a first run, but in a second run where I called it at a slower rate it passed the tests really well.

So if sometimes it passes the tests and sometimes not, it's random enough for my taste.

Originally Posted by Leffmann

It seems the guy who constructed the tests is a professor in statistics and has been studying in this field for over 25 years. I'm willing to take his opinion as law.

I won't take the opinion of anyone as law, but that's just me.

Originally Posted by Leffmann

Anyway, I'm out. This thread has grown way too long already.

Yes, it sure has...

Originally Posted by Thorham

Perhaps not anymore.

And why ? Method doesn't change for bigger numbers.

Originally Posted by Thorham

Edit: The problem with the visual test is that you can only see simpler patterns and very short periods. Also, data that isn't random at all, such as a compressed archive, will show as random while it isn't random at all. The visual test is just an indication of randomness in the end.

If non-random data passes a test, then this test isn't quite good, is it ?


EDIT:

Originally Posted by Leffmann

The timer-based algorithm failed about half of the tests in a first run, but in a second run where I called it at a slower rate it passed the tests really well.

This is "late" edit. But i want the truth to appear from page one (well, two in our case ). My generator didn't fail any test ; the guy was using uae which has unreliable timers. Ha !