Hey, what if we made another sum from the two 16-bit halves, but did so using their bits in reverse, then we took those two sums and combined them in some way?
Or, we could just concatenate the upper 8 bits of each sum.
This way, all result bits are the sum of at least two whole bytes (no thinly-veiled LFSR bits showing through). Also, the two bytes that make up the result word are sums of different sets of whole bits, with the fractional bits being each other's whole bits.
Chip, xoroshiro+ can run backwards using same amount of logic as forwards: two rotates, one shift and one add. Would that be useful? One of the spare opcode bits could select the direction.
Chip, xoroshiro+ can run backwards using same amount of logic as forwards: two rotates, one shift and one add. Would that be useful? One of the spare opcode bits could select the direction.
Yes, maybe. And we'd only need to run the iterator backwards. The sum can be computed the same.
Wait, there is some shifting, not just rotating in the iteration step. Shifting is not reversible. Are you sure?
Chip, xoroshiro+ can run backwards using same amount of logic as forwards: two rotates, one shift and one add. Would that be useful? One of the spare opcode bits could select the direction.
Yes, maybe. And we'd only need to run the iterator backwards. The sum can be computed the same.
Wait, there is some shifting, not just rotating in the iteration step. Shifting is not reversible. Are you sure?
Yes.
You XOR the same shift going backwards to counteract the XOR of that shift going forwards.
I think the first test to do next should be aimed at improving bit 1 as shown in the last line above. We know that 16-bit parity improves bit 0 and it might do the same for bit 1. We can't keep going to the parity well after that because 15-bit parity or less won't be random.
If [15:0] and [7:0] scores are the same, bit 1 will need testing on its own, before and after, to detect any difference.
The significant thing seems to be that there are at least a few stages of carry underneath the high-quality bits, or the bits are affected by what amounts to a few stages of carry - the more the better.
I'm anxious to see if Evanh can run the test on the normal and reverse-field adds, where every bit of the final result has at least 8 stages of carry under it.
;Reverse xoroshiro algorithm for triplet [a,b,c]
x = s1 ROR c ;x = s0 XOR s1
s0 := (s0 XOR (x SHL b) XOR x) ROR a
s1 := s0 XOR x
I think reverse code needs changing to this:
;Reverse xoroshiro algorithm for triplet [a,b,c]
x = s1 ROR c ;x = s0 XOR s1
s0 := (s0 XOR (x SHL b) XOR x) ROR a
s1 := ((s0 XOR (x SHL b) XOR x) ROR a) XOR x
The significant thing seems to be that there are at least a few stages of carry underneath the high-quality bits, or the bits are affected by what amounts to a few stages of carry - the more the better.
I'm anxious to see if Evanh can run the test on the normal and reverse-field adds, where every bit of the final result has at least 8 stages of carry under it.
It's not a case of either/or, just the order of the tests.
LFSR artifacts have gone from bit 0 now. Try to do the same for bit 1 where they are not so bad, so if any improvement is only a small one that's all we need, probably.
Two PRNGs could start off with the same seed in different directions. They wouldn't meet again for 2^31 or 2^31-1 iterations, the maximum gap possible. If they use all 32-bits as one PRN, the high word in one would be the low word in the other due to the odd period.
Comments
I thought of saying that - good job I didn't!
Adding scrambles the bits to a certain extent and this latest idea unscrambles them, it seems.
Or, we could just concatenate the upper 8 bits of each sum.
I think you're right about the unscrambling.
sum_a[15:0] = state[31:16] + state[15:0]
sum_b[15:0] = state[16:31] + state[0:15]
result[15:0] = {sum_a[15:8], sum_b[15:8]}
This way, all result bits are the sum of at least two whole bytes (no thinly-veiled LFSR bits showing through). Also, the two bytes that make up the result word are sums of different sets of whole bits, with the fractional bits being each other's whole bits.
Yes, maybe. And we'd only need to run the iterator backwards. The sum can be computed the same.
Wait, there is some shifting, not just rotating in the iteration step. Shifting is not reversible. Are you sure?
Yes.
You XOR the same shift going backwards to counteract the XOR of that shift going forwards.
What does the code look like that does that?
I'm not so good with C-style operators. I hope this pseudo-code is right.
Added forward code as a check.
I think the first test to do next should be aimed at improving bit 1 as shown in the last line above. We know that 16-bit parity improves bit 0 and it might do the same for bit 1. We can't keep going to the parity well after that because 15-bit parity or less won't be random.
If [15:0] and [7:0] scores are the same, bit 1 will need testing on its own, before and after, to detect any difference.
I'm anxious to see if Evanh can run the test on the normal and reverse-field adds, where every bit of the final result has at least 8 stages of carry under it.
I think reverse code needs changing to this:
It's not a case of either/or, just the order of the tests.
LFSR artifacts have gone from bit 0 now. Try to do the same for bit 1 where they are not so bad, so if any improvement is only a small one that's all we need, probably.
Reversing something like this seems complicated. And that shift still bothers me.
If you can go forward 100 iterations and then backward 100 iterations, and wind up where you started, I guess you've got it figured out.
Chip,
64K iterations backwards from state $0000_0001 gives state $0A5A_9287 and you could try that forwards.
Somehow, I'm getting $0001_0009 after 64k iterations, which is 32k XORO32 instructions, right?
Chip, what state do you get after 1024 XORO32's from state $0000_0001?
I'm not at my computer, anymore, for the next few hours. When I get home I'll check.
As xoroshiro32+ can run in reverse on the Z80, I'm sure it would be possible on the P2!
Another thought:
CZ opcode bits in XORO32 could select forward/reverse iterations and bits in each word normal/reversed.
I've just noticed that $0001_0009 is the 32-bit sum, not the state which should be $0000_0001. Nothing was wrong at my end.
Yes! I was thinking that was probably the case on the way back home. I was going to try it out.
So, it looks like it IS possible to reverse our PRNG pretty easily.
Now, I'm wondering if it's useful to do so. Any ideas?