search

haskell / mwc-random

A very fast Haskell library for generating high quality pseudo-random numbers.
http://hackage.haskell.org/package/mwc-random
BSD 2-Clause "Simplified" License
54 stars 25 forks source link

When a user specifies an invalid carry value (bigger than the multipl… #65

Closed OlivierSohn closed 6 years ago

OlivierSohn commented 6 years ago

…han the multiplicator : force the carry value to be smaller than the multiplicator by using modulo.

Makes the implementation conform to the algorithm as described here.

Might be seen as a breaking change for users specifying out-of-range values for the carry, because they will get different results than before.

OlivierSohn commented 6 years ago

Also, closes #63

OlivierSohn commented 6 years ago

@Shimuuar by any chance, did you have the time to look at this PR?

Shimuuar commented 6 years ago

I didn't sorry. Hopefully I'll do it this week

Shimuuar commented 6 years ago

I finally got to review of patch. This is indeed a bug and change have low impact. By default generator is initiialized with fixed carry 362436 < aa so any subsequent carry will be less than aa. So I will merge it.

One thing. aa = 1540315826 and 1540315826 ≠ 0x303EEE84. Where did you get that number. Still your proof holds irrespective of value of aa

Thanks for catching this!

OlivierSohn commented 6 years ago

Good catch, I think I took the other value from the "non complementary" version of mwc256, here : https://github.com/bos/mwc-random/issues/33, because at the time I was also investigating differences between the 2 algorithms, and trying to understand which of the 2 was implemented here (btw, I think here it is the complementary version that is implemented after all)

I'll update the comments to use the right hexa which is 0x5BCF5AB2.

OlivierSohn commented 6 years ago

The comments are fixed now!

Shimuuar commented 6 years ago

Actually proof could be simplified and generalized to arbitrary aa. Let b = 2^32, a < b and c < a. Then for every q :: Word32 c' < a

  1. ax <= a(b-1)
  2. ax + c <= a(b-1) + c = ab - a + c < ab

therefore ax + c / b < a

OlivierSohn commented 6 years ago

Right, this is a more general formulation.

Do you mean we should update the comments?

In the code, I liked having actual numbers because IMO it makes it easier to follow the reasonning.

Shimuuar commented 6 years ago

As you wish.

I plan to merge this commit, cherry pick optimizations from #66, and make 0.14 release tomorrow.

OlivierSohn commented 6 years ago

Ok, I'll add a commit to mention that the proof holds for any Word32 aa, but keep the rest as it is now.

OlivierSohn commented 6 years ago

@Shimuuar is it ok for you? I'll close #66 once you cherry picked what you needed from it.

Shimuuar commented 6 years ago

Rebased and merged! Sorry for delay. I'll need to update documentation as well I think. Also please keep #66 open for a while