I just wish Americans would put the "l" back into "solder"
It annoyed me too, until I looked into the history of the word. It turns out that the Americans are pronouncing it inline with the origins of the word. The ‘l’ being there from Middle English creates the confusion.
Summary: a newly-submitted but year-old paper examines superseded PRNGs that are older still and finds that reversing the bits of half the output fails one or two statistical tests.
We have a more complete analysis of the ++ backend, and indeed w/2 is not a very good rotation (maybe you already discovered it by testing).
We suggest an odd number, possibly a prime, close to w/2, e.g., 7 for 16-bit generators and 17 for 32-bit generators. In principle, lower than w/2 gives higher linear complexity, but higher than w/2 seem to reduce better Hamming dependencies. So you might prefer a smaller rotation for xoroshiro[16]32 and a larger rotation for xoroshiro[32]64. Heuristically, it would also be better to avoid w-a, w-b, w-c, where (a,b,c) are the parameters of the generators (e.g., for xoroshiro[16]32 14-2-7 don't use 2, 14 or 9).
In small dimension, testing is essential tho. In particular, the odd/prime rule and the "no w-parameters" rules are just heuristics.
I suggested rotations other than w/2 to Seba when he first told me about xoroshiro++ and at that time he said there were analytical reasons why w/2 was the best but clearly that has changed.
The "++ backend" is now known as the "++ scrambler" and xoroshiro[16]32 as simply xoroshiro32. The informal w-a, w-b, w-c "rule" is a pretty good one that I'd forgotten about.
I just wish Americans would put the "l" back into "solder"
It annoyed me too, until I looked into the history of the word. It turns out that the Americans are pronouncing it inline with the origins of the word. The ‘l’ being there from Middle English creates the confusion.
I found this statement of Fowler (from the definition of the word) a bit on the arrogant side "The only pronunciation I have ever heard, except from the half-educated to whom spelling is a final court of appeal.
Personally I find the rules of pronunciation for the English language to be a bit on the silly side with all these silent letters and exceptions. Word pronunciation and spelling should be consistent.
Latin solidare "to make solid," from solidus "solid" (see solid (adj.)).
and it was the French that dropped "l" from words.
The loss of Latin -l- in that position on the way to Old French is regular, as poudre from pulverem, cou from collum, chaud from calidus.
I conclude that English speaking people should keep the "l" and that this Fowler guy was some idiot Francophile.
Besides keeping the "l" avoids any confusion with "sod" and "sodomy" which we would like to avoid.
I agree, spelling and pronunciation in English is a mess. It all has a reason though, lost in the depths of time, what with being a language hacked together from the influences of many others. Bit like C++ I guess
Latin solidare "to make solid," from solidus "solid" (see solid (adj.)).
and it was the French that dropped "l" from words.
The loss of Latin -l- in that position on the way to Old French is regular, as poudre from pulverem, cou from collum, chaud from calidus.
I conclude that English speaking people should keep the "l" and that this Fowler guy was some idiot Francophile.
Besides keeping the "l" avoids any confusion with "sod" and "sodomy" which we would like to avoid.
I can’t stage a good argument to oppose you, and I still cringe somewhat when I hear the word pronounced ‘properly’, but I at least can accept it when I hear it.
Now perhaps we’ve strayed somewhat from our original brief....
I put my xoroshiro[32,64]++ efforts up on github https://github.com/ZiCog/xoroshiro-plusplus. Available in C++, SpinalHDL, Verilog and VHDL. Includes a little Quartus demo for the DE0 Nano board to step through xoroshiro64++ output as you press button 1.
It's the first time I managed to get a SpinalHDL project all the way from Spinal source to Verilog to Quartus project to actual working FPGA. Including a test bench written in Scala.
I don't find any other C++ implementations of these algorithms or example output anywhere on the net except as discussed on this forum. So it would be great if someone could verify my output, see link, is correct and is what the Propeller 2 hardware is actually doing now a days.
PS: I presume the d=17 constant for Xoroshiro64++ was an educated guess.
Probably should add some comments in the sources on how the constants were selected. ie: [13 5 10 9] was done via heavy testing with the tools, including Tony's ultimate means of picking from many good ones. Achievable because of the 32-bit state space.
[26 9 13 17], on the other hand, is based on the original Xoroshiro64+ constants of [26 9 13] with d=17 thrown in.
In the C++ source, you've placed the scrambler after the engine. Not the usual order, because it forces serialised flow.
I have no idea what you mean by "usual order". I have even less idea what you mean by "serialised flow"
At the end of the day we have a simple loop of logical/arithmetic operations mashing around bits.
The only question then is: Does my implementation produce the same sequence of bits?
PS: I presume the d=17 constant for Xoroshiro64++ was an educated guess.
Not at all. Nothing educated about it. All those magic numbers, a, b, c, d, come from this very forum thread. I have no idea if they are good magic numbers or not.
All I want is the same as whatever happens in the P2.
P.S. Why is it so hard for these PRNG developer guys to show some reference code in C or whatever and some example output we can check against?
Come-on Heater,
The original code is there on Seba's website. And I provided my reference to you only a few days back.
The basic difference I'm bringing up is output scrambling gets done ahead of the engine iteration. This in effect makes it a parallel operation.
See here where "result" is calculated before s[0] and s[1] are updated:
static rngword_t nextxoro( void )
{
rngword_t s0 = s[0];
rngword_t s1 = s[1];
rngword_t result = s0 + s1; // output hash (scrambler) for Xoroshiro+
//New addition from authors: Rotation and second summing
result = rotl( result, CONSTANT_D ) + s0;
s1 ^= s0;
s[0] = rotl( s0, CONSTANT_A ) ^ s1 ^ (s1 << CONSTANT_B);
s[1] = rotl( s1, CONSTANT_C );
return( result );
}
I presumed you understood the origins of the constants but I guess not. For Xoroshiro64, there is no way to do a brute force search for even okay candidates, let alone discovering good ones. The state full period is just too big. So the constants used in Xoroshiro64++ are only what Seba supplied for Xoroshiro64+, namely a=26, b=9, c=13. As far as I know he never supplied anything for the ++ scrambler.
Come-on Heater, The original code is there on Seba's website.
Please tell me where. I see no reference to xoroshiro[32,64]++ source code anywhere here: http://xoshiro.di.unimi.it/ I see no test data.
See here where "result" is calculated before s[0] and s[1] are updated:
I don't get it.
Case 1: Produce the result before updating the state variables. The result depends only on the old state variables.
Case 2: Update the result after updating the state variables. The result now depends on the new state variables.
It's the same sequence at the end of the day. Give or take a step.
I presumed you understood the origins of the constants but I guess not.
You guessed right. I have no idea.
To my naive mind we have a randomly selected arrangement of logical and arithmetic operations with some randomly selected "magic" numbers and we are told "this is a good PRNG".
Well, OK, I have no way to judge what is good or not.
For this reason I ask for example code from the PRNG designers and example output to test other implementations against.
PS: I presume the d=17 constant for Xoroshiro64++ was an educated guess.
Probably should add some comments in the sources on how the constants were selected. ie: [13 5 10 9] was done via heavy testing with the tools, including Tony's ultimate means of picking from many good ones. Achievable because of the 32-bit state space.
[26 9 13 17], on the other hand, is based on the original Xoroshiro64+ constants of [26 9 13] with d=17 thrown in.
Evan, you must have missed this reply of mine to Heater. :
The paper mentions the xoroshiro64 [26,9,13] engine and the +, * and ** scramblers. + is not good enough and ++ would be a much better alternative if there are no multipliers available. In an email to me Seba suggested 15 or 17 for the ++ rotation, i.e. half the output width +/- 1.
I chose d = 17 as Seba told me that, in theory, an odd prime has a little more mojo than plain odd (although not in those exact words). Also our chosen xoroshiro32++ has d = w/2 +1.
Nobody really knows whether d = 17 is the best choice or not, as xoroshiro64++ is far too big to test fully.
P.S. Why is it so hard for these PRNG developer guys to show some reference code in C or whatever and some example output we can check against?
Heater., if this is directed at me I posted test outputs for you for both xoroshiro32++[13,5,10,9] and xoroshiro64++[26,9,13,17].
Exactly when the PRN is calculated, before or after the state iteration, makes no difference to the sequence of pseudo-random data. Having said that, in hardware or software with parallel processing before is preferable because it is faster. In software without parallel processing after is best as it can save a register and is not any slower.
Your C version of xoroshiro64++ does it before but it seems that your SpinalHDL does if after. This was one of the points I was trying to make when I suggested this
Before publication Seba told me xoroshiro++ would not be in the paper but it ended up being included (para 10.7, p.38). A link to the paper and mention of xoroshiro32++ is at http://xoshiro.di.unimi.it/. The paper does not make it clear in my view how much better the ++ scramber is than +, although it does call the former strong and the latter weak.
Heater., if this is directed at me I posted test outputs for you for both xoroshiro32++[13,5,10,9] and xoroshiro64++[26,9,13,17].
Yes you did. Thank you.
Nothing is directed at you. It's directed at the guys busy inventing the PRNG algorithms but don't provide a reference so that others can implement the same.
As it is I put my implementations up on github, https://github.com/ZiCog/xoroshiro-plusplus, together with test output and ask: Is it correct or not? WRT what the Propeller 2 does.
Before publication Seba told me xoroshiro++ would not be in the paper but it ended up being included (para 10.7, p.38). A link to the paper and mention of xoroshiro32++ is at http://xoshiro.di.unimi.it/. The paper does not make it clear in my view how much better the ++ scramber is than +, although it does call the former strong and the latter weak.
/me goes looks ... Hmm, all of two paragraphs leading off with this little gem: "We conclude our discussion mentioning a strong scrambler that we ended up not using, ..."
As it is I put my implementations up on github, https://github.com/ZiCog/xoroshiro-plusplus, together with test output and ask: Is it correct or not? WRT what the Propeller 2 does.
Yes or no?
If "yes" we are good to go.
If "no" we can discuss how to fix it.
No. Prop2 uses the more parallel scrambler first arrangement.
/me goes looks ... Hmm, all of two paragraphs leading off with this little gem: "We conclude our discussion mentioning a strong scrambler that we ended up not using, ..."
Do you have a link to exactly where that quote comes from?
I worry about this.
If I build a 64 bit binary counter I know it will pass through all states from 0x00000000 to 0xFFFFFFFF.
With a brilliant statistical distribution. Every state gets visited once. Every 16 bit output happens 2^16 times, etc.
A PRNG is such a counter. But working in some weird order.
Now I have no idea if my counter even visits all the possible states. Or how often.
As John von Neumann said: "Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin."
Heater,
The engine defines the state space, not the scrambler. The Xoroshiro engine hasn't change. Dave and Seba has tools for producing every possible full period set of constants for a given engine size. EDIT: So [26 9 13] is known to go full period. The unknown is quality.
The paper mentions the xoroshiro64 [26,9,13] engine and the +, * and ** scramblers. + is not good enough and ++ would be a much better alternative if there are no multipliers available. In an email to me Seba suggested 15 or 17 for the ++ rotation, i.e. half the output width +/- 1.
I chose d = 17 as Seba told me that, in theory, an odd prime has a little more mojo than plain odd (although not in those exact words). Also our chosen xoroshiro32++ has d = w/2 +1.
Nobody really knows whether d = 17 is the best choice or not, as xoroshiro64++ is far too big to test fully.
I saw it, I figured Heater was up to speed on it too, so I was making another polish suggestion.
Prop2 uses the more parallel scrambler first arrangement.
Yes, but that makes no difference to the output sequence except to delay by one iteration or not.
The scrambler is a simple function of the state.
It can be a function of the old state.
It can be a function of he new state.
As I demonstrated in my HDL examples earlier in this thread.
Yes, I have read the paper. I do not understand most of it. Except there is no code in there for an xorshoro32++ or xorshoro64++ algorithm. So I have no way to know if what I have implemented is correct or not.
Comments
It annoyed me too, until I looked into the history of the word. It turns out that the Americans are pronouncing it inline with the origins of the word. The ‘l’ being there from Middle English creates the confusion.
https://www.google.com.au/search?q=solder+etymology
Summary: a newly-submitted but year-old paper examines superseded PRNGs that are older still and finds that reversing the bits of half the output fails one or two statistical tests.
The "++ backend" is now known as the "++ scrambler" and xoroshiro[16]32 as simply xoroshiro32. The informal w-a, w-b, w-c "rule" is a pretty good one that I'd forgotten about.
I found this statement of Fowler (from the definition of the word) a bit on the arrogant side "The only pronunciation I have ever heard, except from the half-educated to whom spelling is a final court of appeal.
Personally I find the rules of pronunciation for the English language to be a bit on the silly side with all these silent letters and exceptions. Word pronunciation and spelling should be consistent.
Latin solidare "to make solid," from solidus "solid" (see solid (adj.)).
and it was the French that dropped "l" from words.
The loss of Latin -l- in that position on the way to Old French is regular, as poudre from pulverem, cou from collum, chaud from calidus.
I conclude that English speaking people should keep the "l" and that this Fowler guy was some idiot Francophile.
Besides keeping the "l" avoids any confusion with "sod" and "sodomy" which we would like to avoid.
I agree, spelling and pronunciation in English is a mess. It all has a reason though, lost in the depths of time, what with being a language hacked together from the influences of many others. Bit like C++ I guess
I can’t stage a good argument to oppose you, and I still cringe somewhat when I hear the word pronounced ‘properly’, but I at least can accept it when I hear it.
Now perhaps we’ve strayed somewhat from our original brief....
It's the first time I managed to get a SpinalHDL project all the way from Spinal source to Verilog to Quartus project to actual working FPGA. Including a test bench written in Scala.
I don't find any other C++ implementations of these algorithms or example output anywhere on the net except as discussed on this forum. So it would be great if someone could verify my output, see link, is correct and is what the Propeller 2 hardware is actually doing now a days.
In the C++ source, you've placed the scrambler after the engine. Not the usual order, because it forces serialised flow.
Other than that, the output for both 32 and 64 checks fine against mine.
Probably should add some comments in the sources on how the constants were selected. ie: [13 5 10 9] was done via heavy testing with the tools, including Tony's ultimate means of picking from many good ones. Achievable because of the 32-bit state space.
[26 9 13 17], on the other hand, is based on the original Xoroshiro64+ constants of [26 9 13] with d=17 thrown in.
At the end of the day we have a simple loop of logical/arithmetic operations mashing around bits.
The only question then is: Does my implementation produce the same sequence of bits? Not at all. Nothing educated about it. All those magic numbers, a, b, c, d, come from this very forum thread. I have no idea if they are good magic numbers or not.
All I want is the same as whatever happens in the P2.
P.S. Why is it so hard for these PRNG developer guys to show some reference code in C or whatever and some example output we can check against?
The original code is there on Seba's website. And I provided my reference to you only a few days back.
The basic difference I'm bringing up is output scrambling gets done ahead of the engine iteration. This in effect makes it a parallel operation.
See here where "result" is calculated before s[0] and s[1] are updated:
static rngword_t nextxoro( void ) { rngword_t s0 = s[0]; rngword_t s1 = s[1]; rngword_t result = s0 + s1; // output hash (scrambler) for Xoroshiro+ //New addition from authors: Rotation and second summing result = rotl( result, CONSTANT_D ) + s0; s1 ^= s0; s[0] = rotl( s0, CONSTANT_A ) ^ s1 ^ (s1 << CONSTANT_B); s[1] = rotl( s1, CONSTANT_C ); return( result ); }I presumed you understood the origins of the constants but I guess not. For Xoroshiro64, there is no way to do a brute force search for even okay candidates, let alone discovering good ones. The state full period is just too big. So the constants used in Xoroshiro64++ are only what Seba supplied for Xoroshiro64+, namely a=26, b=9, c=13. As far as I know he never supplied anything for the ++ scrambler.
EDIT: Improve readabilty
Case 1: Produce the result before updating the state variables. The result depends only on the old state variables.
Case 2: Update the result after updating the state variables. The result now depends on the new state variables.
It's the same sequence at the end of the day. Give or take a step. You guessed right. I have no idea.
To my naive mind we have a randomly selected arrangement of logical and arithmetic operations with some randomly selected "magic" numbers and we are told "this is a good PRNG".
Well, OK, I have no way to judge what is good or not.
For this reason I ask for example code from the PRNG designers and example output to test other implementations against.
Is that too much to ask?
Evan, you must have missed this reply of mine to Heater. :
I chose d = 17 as Seba told me that, in theory, an odd prime has a little more mojo than plain odd (although not in those exact words). Also our chosen xoroshiro32++ has d = w/2 +1.
Nobody really knows whether d = 17 is the best choice or not, as xoroshiro64++ is far too big to test fully.
Heater., if this is directed at me I posted test outputs for you for both xoroshiro32++[13,5,10,9] and xoroshiro64++[26,9,13,17].
Exactly when the PRN is calculated, before or after the state iteration, makes no difference to the sequence of pseudo-random data. Having said that, in hardware or software with parallel processing before is preferable because it is faster. In software without parallel processing after is best as it can save a register and is not any slower.
Your C version of xoroshiro64++ does it before but it seems that your SpinalHDL does if after. This was one of the points I was trying to make when I suggested this
Correct. But my suggested improvement has sound reasoning. It was only meant as a nudge.
Yes. Tony and I were the ones who decided to use the ++ scrambler. Seba and David have dropped it. EDIT: It was never published.
Here's a reply I prepared earlier:
Nothing is directed at you. It's directed at the guys busy inventing the PRNG algorithms but don't provide a reference so that others can implement the same.
As it is I put my implementations up on github, https://github.com/ZiCog/xoroshiro-plusplus, together with test output and ask: Is it correct or not? WRT what the Propeller 2 does.
Yes or no?
If "yes" we are good to go.
If "no" we can discuss how to fix it.
/me goes looks ... Hmm, all of two paragraphs leading off with this little gem: "We conclude our discussion mentioning a strong scrambler that we ended up not using, ..."
I worry about this.
If I build a 64 bit binary counter I know it will pass through all states from 0x00000000 to 0xFFFFFFFF.
With a brilliant statistical distribution. Every state gets visited once. Every 16 bit output happens 2^16 times, etc.
A PRNG is such a counter. But working in some weird order.
Now I have no idea if my counter even visits all the possible states. Or how often.
As John von Neumann said: "Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin."
The engine defines the state space, not the scrambler. The Xoroshiro engine hasn't change. Dave and Seba has tools for producing every possible full period set of constants for a given engine size. EDIT: So [26 9 13] is known to go full period. The unknown is quality.
Here's the paper with that quote - http://vigna.di.unimi.it/ftp/papers/ScrambledLinear.pdf
I saw it, I figured Heater was up to speed on it too, so I was making another polish suggestion.
The scrambler is a simple function of the state.
It can be a function of the old state.
It can be a function of he new state.
As I demonstrated in my HDL examples earlier in this thread.
Yes, I have read the paper. I do not understand most of it. Except there is no code in there for an xorshoro32++ or xorshoro64++ algorithm. So I have no way to know if what I have implemented is correct or not.
Still waiting for a simple "yes" or "no" on that.
No really I did. Perhaps you could elaborate on you answer.
Thing is, the output of what I have on github matches the outputs presented recently in this thread.
Which one of us is wrong? And how?
You do have a way to be non-specific and nebulous.
If my PRNG sequence is the same but ahead or behind what you expect by one step then that is good.
I cannot fathom why it is so hard to say "this is the algorithm", "this is the input(seed)" and "this is the output"
Chip discovered this as well. Meaning, Chip did it same way as you initially.
If you posted your results here then I could see them, instead of Secure Connection Failed, blah, blah, blah.
EDIT:
https or http - makes no difference.
EDIT: You could try just removing the S off of HTTP, ie: http://github.com/ZiCog/xoroshiro-plusplus