@Ahle2
In Quartus set the mode to "Active Serial Programming"
Use "Add File" to get the DE2-115 file from its folder
Check the Program/Configure check box and the verify checkbox.
Set the Prog/Run switch to Prog.
Press "Start"
takes about 2 minutes.
PactRand was run up to 16GB. It reported one "unusual" for 1GB during the 63 bit test.
PactRand fails almost immediately on the 64 bit test !
Dieaharder reported a couple of "WEAK" for both 63 and 64 bit tests.
I have not retested the 64 bit (with carry) again. I think we all agree it is a miserable failure.
Conclusion: Only use 63 bits [63:1]
The gory details of the test results are attached here.
However, I have an even better PRNG..... JKISS32. Passes Pract Rand with no "unusuals" up to the 128GB test. Passes Dieharder with only two WEAK tests.
Only 32 bit mind.
// Return a 32 bit pseudo random integer between 0 and 0xffffffff
uint32_t JKISS32()
{
static uint32_t x = 123456789;
static uint32_t y = 234567891;
static uint32_t z = 345678912;
static uint32_t w = 456789123;
static uint32_t c = 0;
int t;
y ^= (y << 5);
y ^= (y >> 7);
y ^= (y << 22);
t = z + w + c;
z = w;
c = t < 0;
w = t & 2147483647;
x += 1411392427;
return x + y + w;
}
If JKISS32 really is that good... It's strange that it's never discussed anywhere and that it's hard to come by anyone that uses it.
Maybe it just comes down to the fact that it eats more cycles and isn't really THAT much better?
IMHO, 32 bits is not enough, it will start repeating after just 2^32 / 160000000 = 26.8 seconds.
However, I have an even better PRNG..... JKISS32. Passes Pract Rand with no "unusuals" up to the 128GB test. Passes Dieharder with only two WEAK tests.
However, using random seeds (from urandom device) xoroshiro mostly goes through Dieharder with just 1 week test and many time without any issues!
I will run JKISS32 and xoroshiro with random seeds side by side X number of times using Dieharder and PractRand. I will get back!
PRNGs are like fashions. JKISS32 is 7 years old now. George Marsaglia's KISS PRNG, on which it based, is even older. Kids to today would not be seen dead with such an old PRNG. Unless they are Hipsters looking for a retro PRNG
More seriously, JKISS32 is only a 32 bit generator and we live in a world of 64 bit machines. But arguably if you using a 32 bit machine JKISS might be smaller/faster than xoroshiro128+
Some have argued that JKISS32 is no good because the original source code, see linked paper, uses "int" and is therfor not cross-platform. The size of int depends on your compiler. I think that is silly because the intention is clear, it's easy to change to uint32_t and easy to verify your modified version works the same.
xoroshiro128+ has the great advantage of the jump() function, enabling one to create many thousands of independent PRNGs to run on massively parallel simulations and such (Up to 2^64 independent PRNGS!).
JonyMac uses JKISS32 on the Propeller in his Hollywood creations.
IMHO, 32 bits is not enough, it will start repeating after just 2^32 / 160000000 = 26.8 seconds.
No. JKISS32 has a period of about 2^121 or 10e36. Almost up there with the 2^128 of xoroshiro128+.
The period of a PRNG depends on how many state bits it has not the number of bits it outputs each round.
I will run JKISS32 and xoroshiro with random seeds side by side X number of times using Dieharder and PractRand. I will get back!
Great.
This random number problem is kind of obsessive, isn't it?
It first got my attention 25 odd years ago when we had to create a source of randomness for a secure military communications project. Turned out to be a lot harder than I would have ever guessed before.
This random number problem is kind of obsessive, isn't it?
By accident, creating a random number of 59*8 bits Heater found this code, that carries an intrinsic message to those understanding a little English. How long did it take, what was the logic, that created that code?
Randomness is all about history. If I do know only one number, this number is random. No matter how this number came into the world. If you just read the clock counter now and then this number will be random, controlled by the structure of the "now and then". Noone will present to an intruder all the codes created up to now to allow him to determine the mechanism to create numbers or even to run some statistical analyses.
Random numbers are used in a lottery. Clever guys bet on those number that are not used by average people, like birthdays, ... or special events, like Jan.20th2017, because in the case of being a winner, they will take it all and not share with the crowd. People that like to win take those numbers, that come from an imperfect machine rather often, then the share, but they win. ;-)
PRNGs are like fashions. JKISS32 is 7 years old now. George Marsaglia's KISS PRNG, on which it based, is even older. Kids to today would not be seen dead with such an old PRNG. Unless they are Hipsters looking for a retro PRNG
More seriously, JKISS32 is only a 32 bit generator and we live in a world of 64 bit machines. But arguably if you using a 32 bit machine JKISS might be smaller/faster than xoroshiro128+
Some have argued that JKISS32 is no good because the original source code, see linked paper, uses "int" and is therfor not cross-platform. The size of int depends on your compiler. I think that is silly because the intention is clear, it's easy to change to uint32_t and easy to verify your modified version works the same.
xoroshiro128+ has the great advantage of the jump() function, enabling one to create many thousands of independent PRNGs to run on massively parallel simulations and such (Up to 2^64 independent PRNGS!).
Of course, 64 bit output, jump ahead and less CPU cycles are great features, but I still would have thought that if JKISS32 really is better it would have been better known. I will try to figure out if it really is better by running many tests with both JKISS32 and Xoroshiro with random seeds using PractRand and Dieharder. It will of course take a considerable time, but I will automate it and run many processes at the same time to use the CPU better.
JonyMac uses JKISS32 on the Propeller in his Hollywood creations.
IMHO, 32 bits is not enough, it will start repeating after just 2^32 / 160000000 = 26.8 seconds.
No. JKISS32 has a period of about 2^121 or 10e36. Almost up there with the 2^128 of xoroshiro128+.
The period of a PRNG depends on how many state bits it has not the number of bits it outputs each round.
Yes, of course, but I thought JKISS32 used a 32 bit state because most other PRNG's uses postfixes like ...1024, ...512, ...19937 to indicate the size of the state rather than the output size.
Buuuut, I could have have looked at the code for 3 seconds instead of looking like a fool here!
I will run JKISS32 and xoroshiro with random seeds side by side X number of times using Dieharder and PractRand. I will get back!
Great.
This random number problem is kind of obsessive, isn't it?
It first got my attention 25 odd years ago when we had to create a source of randomness for a secure military communications project. Turned out to be a lot harder than I would have ever guessed before.
Yes, it seems to be a lot harder than most people realizes. Just rotating, shifting, adding and xoring at random (no fun intended) makes a poor PRNG. There's a reason why the designers choose "ROL x, 55" and not "ROL x, 36" in Xoroshiro; And the math behind it is on a level that most people can't understand.
I don't mean to be rude but I cannot tell the difference between your forum posts and a randomly selected word soup.
I know that if I reply to or question anything you say, I just get more randomly selected word soup back.
Anyway, randomness is not about "history". If it is history it is no longer random. It's recorded. We know what it is.
Randomness is about the unknown. The unguessable. The unpredictable.
The name of the game here is not to produce random numbers but to produce such sequences that any observer has a very hard time determining if they are really random or generated by some algorithm (Which by definition is not random).
You say: The name of the game here is not to produce random numbers but to produce such sequences that any observer has a very hard time determining if they are really random or generated by some algorithm (Which by definition is not random).
The question to me is: what is the reason to have a pseudo random number generator if you have a random number generator?
A true random generator would need a radioactive source or some such. A bit difficult to deploy, most places. Linux tries to get entropy from the environment, i.e. everything connected (keyboard and everything else), but the entropy is limited - /dev/random only gives you bits for some time, then it needs a breather. And you may have to use /dev/urandom instead.
The question to me is: what is the reason to have a pseudo random number generator if you have a random number generator?
A very good question.
Do you have a random number generator?
Traditionally computers did not have. They could only get randomness by means of whatever clock they had and the timing of incoming events, like keyboard hits.
Turns out this is not very good. And it's slow. What if you need a million random numbers but nobody has pressed a key in that time? You have to stall and wait.
Even if you add a hardware noise source to your machine in turns out it is slow. It's also expensive.
For example, on the Propeller you can use the RealRandom object to get randomness from the phase locked loop. But you have to consume a whole 32 bit COG to do just that.
What if you are running 10,000 processors in parallel in some super computer? It's impossible to feed them all from 10,000 hardware random number sources.
But here is a killer. What if you want to feed random numbers into your program but for testing purposes you need to run it again tomorrow with exactly the same input? You can store billions of numbers of course. Or you can just use the PRNG with the same seed again.
So, the question to me is: How do you suggest a random() function be implemented on the P2?
A true random generator would need a radioactive source ...
That depends upon which interpretation of quantum mechanics you adhere to. IOW, is the randomness inherent, or the result of hidden states in an otherwise deterministic process?
What is a random number? In the most simple case, your number is one bit long and can be 0 or 1. So how can you tell that the 1 you get with your first selection is random?
The same question can be asked, if your first try results in 0.
There is, and only ever has been, one random number. It is a secret. I am not going to tell you what it is. Unless you guess it correctly. Only one guess allowed I'm afraid.
Hint: It's an integer less than 100.
@Phil,
That depends upon which interpretation of quantum mechanics you adhere to. IOW, is the randomness inherent, or the result of hidden states in an otherwise deterministic process?
Quite so. Even Einstein, as revolutionary as he was, was clinging to the old Newtonian, mechanical, predictable ways and rejected quantum mechanics. As he said "God does not play dice with the universe".
But really, does this worry about determinism matter?
When you place your bets on a horse race the important point is that neither you or the guy taking your bet knows what is going to happen. If the outcome of the race was known already you would not be betting. If one of you knows and the other does not that is called cheating.
It does not matter if the outcome is deterministic, or quantum mechanically weird, or just impossible to compute in a chaos theory way.
The point is you and your bookie don't know ahead of time.
I strongly disagree with, if the randomness is repeatable thru the same seed.
So if the Random Generator needs a different seed or you will get the same numbers, again and again then the problem is not solved at all.
Because we will need a random seed. And are back to the beginning.
If I get the same numbers again, it is not random. It might be statistic random and equal distributed over the range of numbers, but if repeatable it is not random.
Heater: you are absolutely correct!
Some answers to difficult questions are so close, what we call: we do not see the forest for the trees, but if we see the forest, we don't see the trees.
If you have a infinitely small source of light, the light passing a finite slot, on a screen behind the wall you see a lets say gaussian intensity distribution. If now you have a finitely small source of light and an infinitely fine slot, the screen will show the same picture. But what if both, source and slot are of a medium size: in this case you see the same picture, because now a gaussion source is convoluted by an gaussion slot and that results in another, wider gaussian.
This very principle can be applied to every source/detector assembly. And it is in the end the principle of uncertainty. Imagine two entities of the same object observe each other. Observation means: exchange of energy in the form of action. So whenever you determine the energy of one object by another one, the energy must be different, so the next measurement must result in a different value and so, as you take a individual measurement not as valid, but you try to make a second probe, you automatically generate a different result, what you interpret as "uncertainty".
In reality any event only makes sense, when it is repeated, because then you can rely and predict. But if you predict, that a prediction is not possible it prevents you from relying, so for example, a frog decides not cross the road and so survives. Or: you may agree that doves are quite stupid. But there is not need to slow down your care whenever a dove is sitting on the street, because those doves, that do not fly away are dead for a long time.
To answer your question:
"This random number problem is kind of obsessive, isn't it?" without the apostrophe, including blanks, is 59 bytes long (if every character is represented by 8 bits). I thought you, by accident, created 59 random numbers of 8 bits, so generated a number with 59 bytes and funny things happen, this number formed a readable, senseful sentence which you then posted.
I strongly disagree with, if the randomness is repeatable thru the same seed.
You are quite right. Nothing random there.
what I am missing here?
I think what you are missing is that we are talking about "Pseudo Random Number Generators" (PRNG). Not actual random number generators.
PRNGs are algorithms that produce sequences of numbers that are statistically similar to actual random numbers.
Being algorithms, programs, PRNGs are not random at all. They are deterministic. They have to start from somewhere. That somewhere is the seed.
Run the same program again, from the same seed, and of course you get the same sequence of numbers out of it.
But consider this:
Let's say I feed you a stream of numbers, say zeros and ones. I say each one is randomly selected. Then can you tell if those zeros and ones come from some random event, like a coin toss, or if they come from my cunning algorithm?
If I have a stupid algorithm you can apply some statistical analysis which might convince you I'm faking it. If I have a clever algorithm you will find it very hard to tell.
I do understand that part, but since - as far as I know - the P2 opcodes have no opcode for seeding, all random reads will be deterministic and repeatable, and so useless for - say - gaming application or such.
Chip's plan, as far as I understand it, is to seed the PRNG from a source of real randomness at boot time.
So, every time you start a P2 you get a different random sequence.
I thought the downside of this is that you cannot repeat a random sequence if you want to. But then again, if you ever need that it's not hard to put your own PRNG into your code.
Chip's plan, as far as I understand it, is to seed the PRNG from a source of real randomness at boot time.
I think I'm finally beginning to understand the plan. Maybe someone can correct me if I'm wrong:
1. At boot, produce a real 64-bit random number, based upon some necessarily sketchy hardware process and the Von Neumann algo to eliminate bias.
2. From this 64-bit number, produce 16 32-bit seeds, one for each cog's PRNG by selecting bits (normal or inverted) from the 64-bit number using a fixed mapping. The mapping is designed such that each bit in the 64-bit number gets used eight times.
Heater, for testing, one could save a sample set from the P2's generator, and then play it back in place of it.
Or, as you said, just stick in your own PRNG with a fixed seed for testing.
Comments
In Quartus set the mode to "Active Serial Programming"
Use "Add File" to get the DE2-115 file from its folder
Check the Program/Configure check box and the verify checkbox.
Set the Prog/Run switch to Prog.
Press "Start"
takes about 2 minutes.
63 bits [63:1] PactRand OK Dieharder OK
64 bits [63:0] PactRand FAIL Dieharder OK
Notes:
PactRand was run up to 16GB. It reported one "unusual" for 1GB during the 63 bit test.
PactRand fails almost immediately on the 64 bit test !
Dieaharder reported a couple of "WEAK" for both 63 and 64 bit tests.
I have not retested the 64 bit (with carry) again. I think we all agree it is a miserable failure.
Conclusion: Only use 63 bits [63:1]
The gory details of the test results are attached here.
Thanks for the instructions on how to get going with the P2!
@Heater
Then we all have come to the same conclusion, and that agrees with what the Xoroshiro designers said themselves as well.
However, I have an even better PRNG..... JKISS32. Passes Pract Rand with no "unusuals" up to the 128GB test. Passes Dieharder with only two WEAK tests.
Only 32 bit mind.
// Return a 32 bit pseudo random integer between 0 and 0xffffffff uint32_t JKISS32() { static uint32_t x = 123456789; static uint32_t y = 234567891; static uint32_t z = 345678912; static uint32_t w = 456789123; static uint32_t c = 0; int t; y ^= (y << 5); y ^= (y >> 7); y ^= (y << 22); t = z + w + c; z = w; c = t < 0; w = t & 2147483647; x += 1411392427; return x + y + w; }http://www0.cs.ucl.ac.uk/staff/d.jones/GoodPracticeRNG.pdf
Maybe it just comes down to the fact that it eats more cycles and isn't really THAT much better?
IMHO, 32 bits is not enough, it will start repeating after just 2^32 / 160000000 = 26.8 seconds.
/Johannes
However, using random seeds (from urandom device) xoroshiro mostly goes through Dieharder with just 1 week test and many time without any issues!
I will run JKISS32 and xoroshiro with random seeds side by side X number of times using Dieharder and PractRand. I will get back!
PRNGs are like fashions. JKISS32 is 7 years old now. George Marsaglia's KISS PRNG, on which it based, is even older. Kids to today would not be seen dead with such an old PRNG. Unless they are Hipsters looking for a retro PRNG
More seriously, JKISS32 is only a 32 bit generator and we live in a world of 64 bit machines. But arguably if you using a 32 bit machine JKISS might be smaller/faster than xoroshiro128+
Some have argued that JKISS32 is no good because the original source code, see linked paper, uses "int" and is therfor not cross-platform. The size of int depends on your compiler. I think that is silly because the intention is clear, it's easy to change to uint32_t and easy to verify your modified version works the same.
xoroshiro128+ has the great advantage of the jump() function, enabling one to create many thousands of independent PRNGs to run on massively parallel simulations and such (Up to 2^64 independent PRNGS!).
JonyMac uses JKISS32 on the Propeller in his Hollywood creations.
No. JKISS32 has a period of about 2^121 or 10e36. Almost up there with the 2^128 of xoroshiro128+.
The period of a PRNG depends on how many state bits it has not the number of bits it outputs each round.
Great.
This random number problem is kind of obsessive, isn't it?
It first got my attention 25 odd years ago when we had to create a source of randomness for a secure military communications project. Turned out to be a lot harder than I would have ever guessed before.
Randomness is all about history. If I do know only one number, this number is random. No matter how this number came into the world. If you just read the clock counter now and then this number will be random, controlled by the structure of the "now and then". Noone will present to an intruder all the codes created up to now to allow him to determine the mechanism to create numbers or even to run some statistical analyses.
Random numbers are used in a lottery. Clever guys bet on those number that are not used by average people, like birthdays, ... or special events, like Jan.20th2017, because in the case of being a winner, they will take it all and not share with the crowd. People that like to win take those numbers, that come from an imperfect machine rather often, then the share, but they win. ;-)
Of course, 64 bit output, jump ahead and less CPU cycles are great features, but I still would have thought that if JKISS32 really is better it would have been better known. I will try to figure out if it really is better by running many tests with both JKISS32 and Xoroshiro with random seeds using PractRand and Dieharder. It will of course take a considerable time, but I will automate it and run many processes at the same time to use the CPU better.
Yes, of course, but I thought JKISS32 used a 32 bit state because most other PRNG's uses postfixes like ...1024, ...512, ...19937 to indicate the size of the state rather than the output size.
Buuuut, I could have have looked at the code for 3 seconds instead of looking like a fool here!
Yes, it seems to be a lot harder than most people realizes. Just rotating, shifting, adding and xoring at random (no fun intended) makes a poor PRNG. There's a reason why the designers choose "ROL x, 55" and not "ROL x, 36" in Xoroshiro; And the math behind it is on a level that most people can't understand.
I don't mean to be rude but I cannot tell the difference between your forum posts and a randomly selected word soup.
I know that if I reply to or question anything you say, I just get more randomly selected word soup back.
Anyway, randomness is not about "history". If it is history it is no longer random. It's recorded. We know what it is.
Randomness is about the unknown. The unguessable. The unpredictable.
The name of the game here is not to produce random numbers but to produce such sequences that any observer has a very hard time determining if they are really random or generated by some algorithm (Which by definition is not random).
You say:
The name of the game here is not to produce random numbers but to produce such sequences that any observer has a very hard time determining if they are really random or generated by some algorithm (Which by definition is not random).
The question to me is: what is the reason to have a pseudo random number generator if you have a random number generator?
Do you have a random number generator?
Traditionally computers did not have. They could only get randomness by means of whatever clock they had and the timing of incoming events, like keyboard hits.
Turns out this is not very good. And it's slow. What if you need a million random numbers but nobody has pressed a key in that time? You have to stall and wait.
Even if you add a hardware noise source to your machine in turns out it is slow. It's also expensive.
For example, on the Propeller you can use the RealRandom object to get randomness from the phase locked loop. But you have to consume a whole 32 bit COG to do just that.
What if you are running 10,000 processors in parallel in some super computer? It's impossible to feed them all from 10,000 hardware random number sources.
But here is a killer. What if you want to feed random numbers into your program but for testing purposes you need to run it again tomorrow with exactly the same input? You can store billions of numbers of course. Or you can just use the PRNG with the same seed again.
So, the question to me is: How do you suggest a random() function be implemented on the P2?
-Phil
The same question can be asked, if your first try results in 0.
Hint: It's an integer less than 100.
@Phil, Quite so. Even Einstein, as revolutionary as he was, was clinging to the old Newtonian, mechanical, predictable ways and rejected quantum mechanics. As he said "God does not play dice with the universe".
But really, does this worry about determinism matter?
When you place your bets on a horse race the important point is that neither you or the guy taking your bet knows what is going to happen. If the outcome of the race was known already you would not be betting. If one of you knows and the other does not that is called cheating.
It does not matter if the outcome is deterministic, or quantum mechanically weird, or just impossible to compute in a chaos theory way.
The point is you and your bookie don't know ahead of time.
I just told ErNa that there is and only ever has been, one random number. An integer less than 100.
That is to say the number is fixed already. And has been for all time perhaps.
That is to say it is not random at all.
We might speculate that ErNa makes a guess at this number. We might speculate that he has a 1 in 100 chance of getting it right.
That is to say, the randomness is not in the number. The randomness is in ErNa !
I think my brain is about to explode!
So if the Random Generator needs a different seed or you will get the same numbers, again and again then the problem is not solved at all.
Because we will need a random seed. And are back to the beginning.
If I get the same numbers again, it is not random. It might be statistic random and equal distributed over the range of numbers, but if repeatable it is not random.
what I am missing here?
Mike
Some answers to difficult questions are so close, what we call: we do not see the forest for the trees, but if we see the forest, we don't see the trees.
If you have a infinitely small source of light, the light passing a finite slot, on a screen behind the wall you see a lets say gaussian intensity distribution. If now you have a finitely small source of light and an infinitely fine slot, the screen will show the same picture. But what if both, source and slot are of a medium size: in this case you see the same picture, because now a gaussion source is convoluted by an gaussion slot and that results in another, wider gaussian.
This very principle can be applied to every source/detector assembly. And it is in the end the principle of uncertainty. Imagine two entities of the same object observe each other. Observation means: exchange of energy in the form of action. So whenever you determine the energy of one object by another one, the energy must be different, so the next measurement must result in a different value and so, as you take a individual measurement not as valid, but you try to make a second probe, you automatically generate a different result, what you interpret as "uncertainty".
In reality any event only makes sense, when it is repeated, because then you can rely and predict. But if you predict, that a prediction is not possible it prevents you from relying, so for example, a frog decides not cross the road and so survives. Or: you may agree that doves are quite stupid. But there is not need to slow down your care whenever a dove is sitting on the street, because those doves, that do not fly away are dead for a long time.
To answer your question:
"This random number problem is kind of obsessive, isn't it?" without the apostrophe, including blanks, is 59 bytes long (if every character is represented by 8 bits). I thought you, by accident, created 59 random numbers of 8 bits, so generated a number with 59 bytes and funny things happen, this number formed a readable, senseful sentence which you then posted.
PRNGs are algorithms that produce sequences of numbers that are statistically similar to actual random numbers.
Being algorithms, programs, PRNGs are not random at all. They are deterministic. They have to start from somewhere. That somewhere is the seed.
Run the same program again, from the same seed, and of course you get the same sequence of numbers out of it.
But consider this:
Let's say I feed you a stream of numbers, say zeros and ones. I say each one is randomly selected. Then can you tell if those zeros and ones come from some random event, like a coin toss, or if they come from my cunning algorithm?
If I have a stupid algorithm you can apply some statistical analysis which might convince you I'm faking it. If I have a clever algorithm you will find it very hard to tell.
The xoroshiro algorithm is one such example.
and that is quite sad.
Mike
Not so fast...
Chip's plan, as far as I understand it, is to seed the PRNG from a source of real randomness at boot time.
So, every time you start a P2 you get a different random sequence.
I thought the downside of this is that you cannot repeat a random sequence if you want to. But then again, if you ever need that it's not hard to put your own PRNG into your code.
I think I'm finally beginning to understand the plan. Maybe someone can correct me if I'm wrong:
1. At boot, produce a real 64-bit random number, based upon some necessarily sketchy hardware process and the Von Neumann algo to eliminate bias.
2. From this 64-bit number, produce 16 32-bit seeds, one for each cog's PRNG by selecting bits (normal or inverted) from the 64-bit number using a fixed mapping. The mapping is designed such that each bit in the 64-bit number gets used eight times.
Have I got that right?
-Phil
Or, as you said, just stick in your own PRNG with a fixed seed for testing.