[14,2,7] has better top byte than bottom, [15,3,6] is the reverse and therefore [14,2,7] is the better choice. Both have better bits[7:0] than [8:1] which suggests bit 8 is not so random but it's how the bits perform as a group that matters.
Could you simply return x[ i ] (spaces to prevent italics) and get rid of prn? I only added prn to make things clear.
The nice thing about using even the simplest optimizing compiler is that it allows you to write code so that it makes things clear. The compiler will remove prn for you, so it can safely stay.
The only reason for making the parity bit the msb is if it gets a 2G score on its own, i.e. better than sum[15]. It would be nice to have a sum[0] test, but I hope there's a CMWC test churning away currently!
It's mostly similar. Only thing of note is the msbit scores are almost entirely 1G, rather than a somewhat more mixed bag previously. And "Byte0" is now the weakest again.
It's mostly similar. Only thing of note is the msbit scores are almost entirely 1G, rather than a somewhat more mixed bag previously. And "Byte0" is now the weakest again.
Parity on its own get a 1G so bits 31 or 16 or 15 or 0 of XORO32 output could all be used for a high-quality random bit. Low byte not so good now, therefore best to keep things as they are with parity in bit 0.
Yep. Though, it's probably not very fair comparing to an 8-bit generator. That said, there is substantially more state to CMWC8 compared to Xoroshiro32.
I'd imagine Melissa's geometric tests will be more favourable to CMWC.
You can see the parity calculation in x86 code in post #9 (for some reason my browser cannot go directly to these posts). I think the carry is not included.
I'll try to get in touch with David Roberts and the inventors of the Xoroshiro+ algorithm over the weekend to tell them what we have done to improve it.
You can see the parity calculation in x86 code in post #9 (for some reason my browser cannot go directly to these posts). I think the carry is not included.
You might have to give me some pointers on where to look in that code. I don't see any mention of parity or carry in that source. The xoroshiro128+ assembly ends at the summing.
PowerBASIC and x86 asm are entirely foreign to me.
I'll try to get in touch with David Roberts and the inventors of the Xoroshiro+ algorithm over the weekend to tell them what we have done to improve it.
Sebastiano Vigna is aware of our work and is mildly amused at a poky 32-bit state. That said, he might be interested in the parity mod though.
EDIT: Actually, he probably deliberately didn't include a parity step because it's so processing costly for a CPU to execute without a custom instruction.
I don't understand what you say there. I would like to think that any PRNG algorithm is independent of whatever machine runs it. P2, Z80, 6809, whatever.
Actually I have not understood this whole thread.
Seems to be a lot of random tweaking of PRNG generators and expecting the output is more "random" and has long periods.
Why not just use the algorithms as published that have been analysed already?
I don't understand what you say there. I would like to think that any PRNG algorithm is independent of whatever machine runs it. P2, Z80, 6809, whatever.
I think potatohead is amused at the different ways of testing the new and improved XORO32 algorithm: PASM2, Z80, QuickBASIC and C.
Even though we're suited, I'm slightly surprised nobody has done it in Forth.
Seems to be a lot of random tweaking of PRNG generators and expecting the output is more "random" and has long periods.
Why not just use the algorithms as published that have been analysed already?
The P2 needed a PRNG and because of this thread it has the best one there is as of October 2017, in terms of ease of implementation, ease of use, small state and high quality.
Until yesterday, we had to sum the XORO32 output to get only 15 high-quality bits as bit 0 was rubbish. Since yesterday, bit 0 is the most random of the lot and XORO32 gives us 32-bit PRNG bits directly.
There is still work to do, though. I want to get the jump function working, which will help us select non-overlapping sequences. As you can speak geek, perhaps you could help with the C code below. What does i < sizeof JUMP / sizeof *JUMP mean?
/* This is the jump function for the generator. It is equivalent
to 2^64 calls to next(); it can be used to generate 2^64
non-overlapping subsequences for parallel computations. */
void jump(void) {
static const uint64_t JUMP[] = { 0xbeac0467eba5facb, 0xd86b048b86aa9922 };
uint64_t s0 = 0;
uint64_t s1 = 0;
for(int i = 0; i < sizeof JUMP / sizeof *JUMP; i++)
for(int b = 0; b < 64; b++) {
if (JUMP[i] & 1ULL << b) {
s0 ^= s[0];
s1 ^= s[1];
}
next();
}
s[0] = s0;
s[1] = s1;
}
perhaps you could help with the C code below. What does i < sizeof JUMP / sizeof *JUMP mean?
(sizeof ARRAY_VARIABLE / sizeof ARRAY_VARIABLE[0]), or
(sizeof ARRAY_VARIABLE / sizeof *ARRAY_VARIABLE),
gives the the number of elements in the array variable.
It's idiomatic C.
perhaps you could help with the C code below. What does i < sizeof JUMP / sizeof *JUMP mean?
(sizeof ARRAY_VARIABLE / sizeof ARRAY_VARIABLE[0]), or
(sizeof ARRAY_VARIABLE / sizeof *ARRAY_VARIABLE),
gives the the number of elements in the array variable.
It's idiomatic C.
Thanks for the reply.
So sizeof JUMP and sizeof *JUMP are in effect the same thing? In this case 64?
In this case it resolves to a constant of 2. The outer for() loop only does two iterations.
And normally you'd have {} brackets following a for() but since there isn't the subsequent indentation is a hint that that for() loop only contains the singular inner for() loop. Ie; s[0] = s0; s[1] = s1; are executed only after all loops are completed.
Until yesterday, we had to sum the XORO32 output to get only 15 high-quality bits as bit 0 was rubbish. Since yesterday, bit 0 is the most random of the lot and XORO32 gives us 32-bit PRNG bits directly.
Heater is doing a whine about the whole effort around XORO32, not just our recent work. He thinks what we have now is rubbish and will laughed at when someone that understands the deep theory has a look at it.
Comments
Bits 0-15 normal:
[14,2,7] has better top byte than bottom, [15,3,6] is the reverse and therefore [14,2,7] is the better choice. Both have better bits[7:0] than [8:1] which suggests bit 8 is not so random but it's how the bits perform as a group that matters.
Bits 1 and 9 reversed:
I don't think we can swap arbitrary bits willy-nilly. I'd expect [15,3,6] to perform worse if other bits were swapped.
The bits that really matter to the user are the whole word, top byte, bottom byte and top bit:
Thanks to the full parity, the bottom byte is now at least as good as the whole word and sometimes better.
Also, [15 3 6] may now just sneak past [14 2 7].
sum[0] = sum[16:0] parity:
sum[15] = sum[16:0] parity, other bits shifted right:
Xoroshiro32+ sum bits sum[15] = sum[16:0] parity sum[15:1] -> sum[14:0] [15:0] [15:8] [7:0] [15] ============================================ [14 2 7] 512M 256M 128M 1G [15 3 6] 512M 512M 128M 1GParity on its own get a 1G so bits 31 or 16 or 15 or 0 of XORO32 output could all be used for a high-quality random bit. Low byte not so good now, therefore best to keep things as they are with parity in bit 0.
I'd imagine Melissa's geometric tests will be more favourable to CMWC.
David Roberts has also used CMWC:
https://forum.powerbasic.com/forum/user-to-user-discussions/source-code/51476-complementary-multiply-with-carry-with-lag-prng
Other relevant posts of his:
https://forum.powerbasic.com/forum/user-to-user-discussions/programming/749040-xorshift128-prng
https://forum.powerbasic.com/forum/user-to-user-discussions/source-code/749403-xorshift-prng
Download from http://digitalcommons.wayne.edu/jmasm/vol2/iss1/2/
Including the carry was another bit of inspired thinking by Chip. I was moving in the other direction with only sum[15:1].
You can see the parity calculation in x86 code in post #9 (for some reason my browser cannot go directly to these posts). I think the carry is not included.
I'll try to get in touch with David Roberts and the inventors of the Xoroshiro+ algorithm over the weekend to tell them what we have done to improve it.
Thanks Evan. Our first 16 values agree and that's when I stopped!
* Replace bit 0 of sum with parity of all sum bits including the carry bit
* Parity is at worst as random as the most-significant bit, the original suggestion for a random Boolean value, from PractRand tests
PowerBASIC and x86 asm are entirely foreign to me.
EDIT: Actually, he probably deliberately didn't include a parity step because it's so processing costly for a CPU to execute without a custom instruction.
I like that you have agreement across a PC, P2 and a Z80.
Chip says, "so many neat things in P2", inspired by people's thoughts.
Yes.
Will be so very interesting to see what people do with it. Could be next year!
Random numbers are weird. Learned some new concepts following this work. Thank you.
I don't understand what you say there. I would like to think that any PRNG algorithm is independent of whatever machine runs it. P2, Z80, 6809, whatever.
Actually I have not understood this whole thread.
Seems to be a lot of random tweaking of PRNG generators and expecting the output is more "random" and has long periods.
Why not just use the algorithms as published that have been analysed already?
I think potatohead is amused at the different ways of testing the new and improved XORO32 algorithm: PASM2, Z80, QuickBASIC and C.
Even though we're suited, I'm slightly surprised nobody has done it in Forth.
The P2 needed a PRNG and because of this thread it has the best one there is as of October 2017, in terms of ease of implementation, ease of use, small state and high quality.
Until yesterday, we had to sum the XORO32 output to get only 15 high-quality bits as bit 0 was rubbish. Since yesterday, bit 0 is the most random of the lot and XORO32 gives us 32-bit PRNG bits directly.
There is still work to do, though. I want to get the jump function working, which will help us select non-overlapping sequences. As you can speak geek, perhaps you could help with the C code below. What does i < sizeof JUMP / sizeof *JUMP mean?
/* This is the jump function for the generator. It is equivalent to 2^64 calls to next(); it can be used to generate 2^64 non-overlapping subsequences for parallel computations. */ void jump(void) { static const uint64_t JUMP[] = { 0xbeac0467eba5facb, 0xd86b048b86aa9922 }; uint64_t s0 = 0; uint64_t s1 = 0; for(int i = 0; i < sizeof JUMP / sizeof *JUMP; i++) for(int b = 0; b < 64; b++) { if (JUMP[i] & 1ULL << b) { s0 ^= s[0]; s1 ^= s[1]; } next(); } s[0] = s0; s[1] = s1; }(sizeof ARRAY_VARIABLE / sizeof ARRAY_VARIABLE[0]), or
(sizeof ARRAY_VARIABLE / sizeof *ARRAY_VARIABLE),
gives the the number of elements in the array variable.
It's idiomatic C.
Thanks for the reply.
So sizeof JUMP and sizeof *JUMP are in effect the same thing? In this case 64?
sizeof *JUMP is just one element
Conga gave an alternative that I find way clearer in intent: sizeof JUMP / sizeof JUMP[0]
And normally you'd have {} brackets following a for() but since there isn't the subsequent indentation is a hint that that for() loop only contains the singular inner for() loop. Ie; s[0] = s0; s[1] = s1; are executed only after all loops are completed.
Sound about right, Heater?