Permalink
Commits on Aug 21, 2018
Commits on Jul 4, 2018
  1. Verify that SplitMix avoids pathological γ-values

    moodmosaic authored and thumphries committed Jun 29, 2018
    As discussed by Melissa E. O'Neill in 'Bugs in SplitMix(es)' at
    http://www.pcg-random.org/posts/bugs-in-splitmix.html
Commits on May 25, 2018
  1. Merge pull request #198 from moodmosaic/bugfix/seed-from-and-mixgamma

    moodmosaic committed May 25, 2018
     Avoid weak gamma values in Hedgehog.Internal.Seed
Commits on May 23, 2018
  1. Avoid weak gamma values in Hedgehog.Internal.Seed

    moodmosaic committed May 23, 2018
    See also:
    - http://www.pcg-random.org/posts/bugs-in-splitmix.html
    - #191
    - http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/SplittableRandom.java
    - http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/SplittableRandom.java
    
    In http://www.pcg-random.org/posts/bugs-in-splitmix.html, most of the output is horribly formatted.
    
    So I went on and formatted the important part of the output from that article, where it highlights the bug:
    
    >```
    >Prelude System.Random.SplitMix> map mkSMGen
    > [ 0x61c8864680b583eb
    > , 0xf8364607e9c949bd
    > , 0x88e48f4fcc823718
    > , 0x7f83ab8da2e71dd1
    > , 0x7957d809e827ff4c
    > , 0xf8d059aee4c53639
    > , 0x9cd9f015db4e58b7
    > , 0xf4077b0dbebc73c0
    > , 0x305cb877109d0686
    > , 0x359e58eeafebd527
    > , 0xbeb721c511b0da6d
    > , 0x86466fd0fcc363a6
    > , 0xefee3e7b93db3075
    > , 0x79629ee76aa83059
    > , 0x05d507d05e785673
    > , 0x76442b62dddf926c ]
    >
    > [ SMGen {_seed = 16269636050940713694, _gamma =  1}
    > , SMGen {_seed = 11331281847540010644, _gamma =  1}
    > , SMGen {_seed = 5619286150931196027 , _gamma =  1}
    > , SMGen {_seed = 10281499533683189089, _gamma =  1}
    > , SMGen {_seed = 17485363145453140727, _gamma =  7}
    > , SMGen {_seed = 17937441790592959953, _gamma =  7}
    > , SMGen {_seed = 15529190628949695919, _gamma =  7}
    > , SMGen {_seed = 6957216782316743206 , _gamma =  7}
    > , SMGen {_seed = 13022414457527836317, _gamma = 15}
    > , SMGen {_seed = 2127073997383595602 , _gamma = 15}
    > , SMGen {_seed = 7685868475082380828 , _gamma = 15}
    > , SMGen {_seed = 6396586367974718702 , _gamma = 15}
    > , SMGen {_seed = 13838712901582905874, _gamma = 31}
    > , SMGen {_seed = 15464227283579875280, _gamma = 31}
    > , SMGen {_seed = 17142043965827948305, _gamma = 31}
    > , SMGen {_seed = 10266498716653543189, _gamma = 31} ]
    >Prelude System.Random.SplitMix>
    >```
    
    It compares just *one* implementation of SplitMix, [this](https://github.com/phadej/splitmix/blob/f6895c4137b14e4752b0575c178199201eb41810/src/System/Random/SplitMix.hs) one, at some particular point in time.
    
    (I can see that the author went and fixed it recently as shown from the diff-output [here](phadej/splitmix@bd0692b) and [here](phadej/splitmix@c6ba2f3), so this means that now *The Bug* section of http://www.pcg-random.org/posts/bugs-in-splitmix.html is outdated.)
    
    ---
    
    Here's the exact same test with *Hedgehog.Internal.Seed*:
    
    ```
    λ :t from
    from :: GHC.Word.Word64 -> Seed
    
    λ Prelude.map from
      [ 0x61c8864680b583eb
      , 0xf8364607e9c949bd
      , 0x88e48f4fcc823718
      , 0x7f83ab8da2e71dd1
      , 0x7957d809e827ff4c
      , 0xf8d059aee4c53639
      , 0x9cd9f015db4e58b7
      , 0xf4077b0dbebc73c0
      , 0x305cb877109d0686
      , 0x359e58eeafebd527
      , 0xbeb721c511b0da6d
      , 0x86466fd0fcc363a6
      , 0xefee3e7b93db3075
      , 0x79629ee76aa83059
      , 0x05d507d05e785673
      , 0x76442b62dddf926c ]
    
    [ Seed 7046029254386353131  11400714819323198485
    , Seed 17885559969949501885 11400714819323198485
    , Seed 9864166656744503064  11400714819323198485
    , Seed 9188376289577737681  11400714819323198485
    , Seed 8743694738624347980  11400714819323198485
    , Seed 17928928724259255865 11400714819323198485
    , Seed 11302328716527294647 11400714819323198485
    , Seed 17584158569056203712 11400714819323198485
    , Seed 3484863033197266566  11400714819323198485
    , Seed 3863623312507393319  11400714819323198485
    , Seed 13742489918233434733 11400714819323198485
    , Seed 9675543792836633510  11400714819323198485
    , Seed 17288824720004427893 11400714819323198485
    , Seed 8746728143070965849  11400714819323198485
    , Seed 420250731748546163   11400714819323198485
    , Seed 8521984098521027180  11400714819323198485 ]
    λ
    ```
    
    This looks weird, as I'm getting the *exact same γ* through all the seeds. If I change Hedgehog.Internal.Seed's [`from`](https://github.com/hedgehogqa/haskell-hedgehog/blob/615880fcabcbd07f4c583fd9913c8a6985c16c44/hedgehog/src/Hedgehog/Internal/Seed.hs#L108-L110) according to [Oracle's JDK8 implementation](http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/SplittableRandom.java#l214):
    
    ```diff
    λ :! git diff
    diff --git a/hedgehog/src/Hedgehog/Internal/Seed.hs b/hedgehog/src/Hedgehog/Internal/Seed.hs
    index 61cacb2..fe1a0be 100644
    --- a/hedgehog/src/Hedgehog/Internal/Seed.hs
    +++ b/hedgehog/src/Hedgehog/Internal/Seed.hs
    @@ -98,11 +98,11 @@ random =
     -- | Create a 'Seed' using a 'Word64'.
     --
     from :: Word64 -> Seed
     from x =
    -  Seed x goldenGamma
    +  Seed (mix64 x) (mixGamma (x + goldenGamma))
    λ
    ```
    
    I can now reproduce the bug [*exactly* as shown in the article](http://www.pcg-random.org/posts/bugs-in-splitmix.html#the-bug):
    
    ```
    λ Prelude.map from
      [ 0x61c8864680b583eb
      , 0xf8364607e9c949bd
      , 0x88e48f4fcc823718
      , 0x7f83ab8da2e71dd1
      , 0x7957d809e827ff4c
      , 0xf8d059aee4c53639
      , 0x9cd9f015db4e58b7
      , 0xf4077b0dbebc73c0
      , 0x305cb877109d0686
      , 0x359e58eeafebd527
      , 0xbeb721c511b0da6d
      , 0x86466fd0fcc363a6
      , 0xefee3e7b93db3075
      , 0x79629ee76aa83059
      , 0x05d507d05e785673
      , 0x76442b62dddf926c ]
    
    [ Seed 15210016002011668638  1
    , Seed 11409286845259996466  1
    , Seed 1931727433621677744   1
    , Seed 307741759840609752    1
    , Seed 8606169619657412120   7
    , Seed 13651108307767328632  7
    , Seed 125750466559701114    7
    , Seed 6781260234005250507   7
    , Seed 15306535823716590088 15
    , Seed 7344074043290227165  15
    , Seed 9920554987610416076  15
    , Seed 3341781972484278810  15
    , Seed 12360157267739240775 31
    , Seed 600595566262245170   31
    , Seed 1471112649570176389  31
    , Seed 8100917074368564322  31 ]
    λ
    ```
    
    This is actually great so far, as it points out that we got Hedgehog.Internal.Seed's [`from`](https://github.com/hedgehogqa/haskell-hedgehog/blob/615880fcabcbd07f4c583fd9913c8a6985c16c44/hedgehog/src/Hedgehog/Internal/Seed.hs#L108-L110) wrong and we can now 'fix' it according to the 'reference' source.
    
    (At this point, I can tell that the only reliable source is the one found in Oracle's JDK8 implementation.)
    
    ---
    
    And finally, If I go and change the glorious Hedgehog.Internal.Seed [`mixGamma`](https://github.com/hedgehogqa/haskell-hedgehog/blob/615880fcabcbd07f4c583fd9913c8a6985c16c44/hedgehog/src/Hedgehog/Internal/Seed.hs#L202) according to [Oracle's JDK8 implementation](http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/SplittableRandom.java#l214) (essentially, reverting #124):
    
    ```diff
    λ :! git diff
    diff --git a/hedgehog/src/Hedgehog/Internal/Seed.hs b/hedgehog/src/Hedgehog/Internal/Seed.hs
    index 61cacb2..5428927 100644
    --- a/hedgehog/src/Hedgehog/Internal/Seed.hs
    +++ b/hedgehog/src/Hedgehog/Internal/Seed.hs
    @@ -100,7 +100,7 @@ random =
     --
     from :: Word64 -> Seed
     from x =
    -  Seed x goldenGamma
    +  Seed (mix64 x) (mixGamma (x + goldenGamma))
    
     -- | A predefined gamma value's needed for initializing the "root" instances of
     --   'Seed'. That is, instances not produced by splitting an already existing
    @@ -192,7 +192,7 @@ mixGamma x =
         y = mix64variant13 x .|. 1
         n = popCount $ y `xor` (y `shiftR` 1)
       in
    -    if n >= 24 then
    +    if n < 24 then
           y `xor` 0xaaaaaaaaaaaaaaaa
         else
           y
    λ
    ```
    
    It 'fixes' the gamma value:
    
    ```
    λ Prelude.map from
      [ 0x61c8864680b583eb
      , 0xf8364607e9c949bd
      , 0x88e48f4fcc823718
      , 0x7f83ab8da2e71dd1
      , 0x7957d809e827ff4c
      , 0xf8d059aee4c53639
      , 0x9cd9f015db4e58b7
      , 0xf4077b0dbebc73c0
      , 0x305cb877109d0686
      , 0x359e58eeafebd527
      , 0xbeb721c511b0da6d
      , 0x86466fd0fcc363a6
      , 0xefee3e7b93db3075
      , 0x79629ee76aa83059
      , 0x05d507d05e785673
      , 0x76442b62dddf926c ]
    
    [ Seed 15210016002011668638 12297829382473034411
    , Seed 11409286845259996466 12297829382473034411
    , Seed 1931727433621677744  12297829382473034411
    , Seed 307741759840609752   12297829382473034411
    , Seed 8606169619657412120  12297829382473034413
    , Seed 13651108307767328632 12297829382473034413
    , Seed 125750466559701114   12297829382473034413
    , Seed 6781260234005250507  12297829382473034413
    , Seed 15306535823716590088 12297829382473034405
    , Seed 7344074043290227165  12297829382473034405
    , Seed 9920554987610416076  12297829382473034405
    , Seed 3341781972484278810  12297829382473034405
    , Seed 12360157267739240775 12297829382473034421
    , Seed 600595566262245170   12297829382473034421
    , Seed 1471112649570176389  12297829382473034421
    , Seed 8100917074368564322  12297829382473034421 ]
    λ
    ```
Commits on Apr 27, 2018
Commits on Apr 26, 2018
  1. Use 64-bit unsigned integers (Word64) in Seed

    moodmosaic committed Apr 26, 2018
    See also
     - http://gee.cs.oswego.edu/dl/papers/oopsla14.pdf
     - https://github.com/janestreet/splittable_random/blob/2a21d48eeb4eb4c92d8591ef0ba19c75dcd0885d/src/splittable_random.ml#L33-L34
     - https://github.com/phadej/splitmix/blob/2b3945095ce9d907b802ecad63b803abf2d040db/src/System/Random/SplitMix.hs#L57-L58
     - https://github.com/fscheck/FsCheck/blob/0a1d7c7e122a0b77346d150b66587bc34fc4054c/src/FsCheck/Random.fs#L30-L33
     - http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/SplittableRandom.java
    
    Given the following program
    
        import           Data.ByteString.Builder (Builder)
        import qualified Data.ByteString.Builder as Builder
        import           System.IO (stdout)
    
        import           Hedgehog.Internal.Seed (Seed(..), nextWord64, random)
    
        main :: IO ()
        main =
          Builder.hPutBuilder stdout . go =<< random
          where
            go :: Seed -> Builder
            go s0 =
              case nextWord64 s0 of
                 ~(v0, s1) -> Builder.word64LE v0 `mappend` go s1
    
    and adding a test-suite in hedgehog.cabal
    
        test-suite dieharder
          type:
            exitcode-stdio-1.0
    
          main-is:
            Dieharder.hs
    
          ghc-options:
            -Wall -threaded -O2
    
          hs-source-dirs:
            test
    
          build-depends:
              hedgehog
            , base                            >= 3          && < 5
            , bytestring                      >=0.10.4.0    && < 0.11
    
    Running dieharder passes all tests, as shown in
    http://manpages.ubuntu.com/manpages/xenial/man1/dieharder.1.html#contenttoc6
    
        #=============================================================================#
        #            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
        #=============================================================================#
           rng_name    |rands/second|   Seed   |
        stdin_input_raw|  3.73e+06  |3112223130|
        #=============================================================================#
                test_name   |ntup| tsamples |psamples|  p-value |Assessment
        #=============================================================================#
           diehard_birthdays|   0|       100|     100|0.34563424|  PASSED
              diehard_operm5|   0|   1000000|     100|0.91055807|  PASSED
          diehard_rank_32x32|   0|     40000|     100|0.54739259|  PASSED
            diehard_rank_6x8|   0|    100000|     100|0.26505805|  PASSED
           diehard_bitstream|   0|   2097152|     100|0.08284214|  PASSED
                diehard_opso|   0|   2097152|     100|0.00752931|  PASSED
                diehard_oqso|   0|   2097152|     100|0.99546974|   WEAK
                 diehard_dna|   0|   2097152|     100|0.17733131|  PASSED
        diehard_count_1s_str|   0|    256000|     100|0.57339628|  PASSED
        diehard_count_1s_byt|   0|    256000|     100|0.64992966|  PASSED
         diehard_parking_lot|   0|     12000|     100|0.16680695|  PASSED
            diehard_2dsphere|   2|      8000|     100|0.68902795|  PASSED
            diehard_3dsphere|   3|      4000|     100|0.99992722|   WEAK
             diehard_squeeze|   0|    100000|     100|0.94137755|  PASSED
                diehard_sums|   0|       100|     100|0.50267983|  PASSED
                diehard_runs|   0|    100000|     100|0.79817449|  PASSED
                diehard_runs|   0|    100000|     100|0.21850798|  PASSED
               diehard_craps|   0|    200000|     100|0.92958876|  PASSED
               diehard_craps|   0|    200000|     100|0.62629655|  PASSED
         marsaglia_tsang_gcd|   0|  10000000|     100|0.47671094|  PASSED
         marsaglia_tsang_gcd|   0|  10000000|     100|0.42735871|  PASSED
                 sts_monobit|   1|    100000|     100|0.92317911|  PASSED
                    sts_runs|   2|    100000|     100|0.78842199|  PASSED
                  sts_serial|   1|    100000|     100|0.77489764|  PASSED
                  sts_serial|   2|    100000|     100|0.96104267|  PASSED
                  sts_serial|   3|    100000|     100|0.30179030|  PASSED
                  sts_serial|   3|    100000|     100|0.12929165|  PASSED
                  sts_serial|   4|    100000|     100|0.95686266|  PASSED
                  sts_serial|   4|    100000|     100|0.46981192|  PASSED
                  sts_serial|   5|    100000|     100|0.68755789|  PASSED
                  sts_serial|   5|    100000|     100|0.51597633|  PASSED
                  sts_serial|   6|    100000|     100|0.80927343|  PASSED
                  sts_serial|   6|    100000|     100|0.99992079|   WEAK
                  sts_serial|   7|    100000|     100|0.94245243|  PASSED
                  sts_serial|   7|    100000|     100|0.94625255|  PASSED
                  sts_serial|   8|    100000|     100|0.81975829|  PASSED
                  sts_serial|   8|    100000|     100|0.59703661|  PASSED
                  sts_serial|   9|    100000|     100|0.96646876|  PASSED
                  sts_serial|   9|    100000|     100|0.72616335|  PASSED
                  sts_serial|  10|    100000|     100|0.94215083|  PASSED
                  sts_serial|  10|    100000|     100|0.64812061|  PASSED
                  sts_serial|  11|    100000|     100|0.33255018|  PASSED
                  sts_serial|  11|    100000|     100|0.34827077|  PASSED
                  sts_serial|  12|    100000|     100|0.56818982|  PASSED
                  sts_serial|  12|    100000|     100|0.51835009|  PASSED
                  sts_serial|  13|    100000|     100|0.47037623|  PASSED
                  sts_serial|  13|    100000|     100|0.85810264|  PASSED
                  sts_serial|  14|    100000|     100|0.28607292|  PASSED
                  sts_serial|  14|    100000|     100|0.03414349|  PASSED
                  sts_serial|  15|    100000|     100|0.67423768|  PASSED
                  sts_serial|  15|    100000|     100|0.56303644|  PASSED
                  sts_serial|  16|    100000|     100|0.31462994|  PASSED
                  sts_serial|  16|    100000|     100|0.90478391|  PASSED
                 rgb_bitdist|   1|    100000|     100|0.95021276|  PASSED
                 rgb_bitdist|   2|    100000|     100|0.63340855|  PASSED
                 rgb_bitdist|   3|    100000|     100|0.94626759|  PASSED
                 rgb_bitdist|   4|    100000|     100|0.05343869|  PASSED
                 rgb_bitdist|   5|    100000|     100|0.05472197|  PASSED
                 rgb_bitdist|   6|    100000|     100|0.79748521|  PASSED
                 rgb_bitdist|   7|    100000|     100|0.53616218|  PASSED
                 rgb_bitdist|   8|    100000|     100|0.20352776|  PASSED
                 rgb_bitdist|   9|    100000|     100|0.46809570|  PASSED
                 rgb_bitdist|  10|    100000|     100|0.71940373|  PASSED
                 rgb_bitdist|  11|    100000|     100|0.05294303|  PASSED
                 rgb_bitdist|  12|    100000|     100|0.89183483|  PASSED
        rgb_minimum_distance|   2|     10000|    1000|0.82703854|  PASSED
        rgb_minimum_distance|   3|     10000|    1000|0.50017724|  PASSED
        rgb_minimum_distance|   4|     10000|    1000|0.04900225|  PASSED
        rgb_minimum_distance|   5|     10000|    1000|0.46461538|  PASSED
            rgb_permutations|   2|    100000|     100|0.76572585|  PASSED
            rgb_permutations|   3|    100000|     100|0.55150618|  PASSED
            rgb_permutations|   4|    100000|     100|0.69989462|  PASSED
            rgb_permutations|   5|    100000|     100|0.12805292|  PASSED
              rgb_lagged_sum|   0|   1000000|     100|0.56055497|  PASSED
              rgb_lagged_sum|   1|   1000000|     100|0.52548113|  PASSED
              rgb_lagged_sum|   2|   1000000|     100|0.97868238|  PASSED
              rgb_lagged_sum|   3|   1000000|     100|0.64319424|  PASSED
              rgb_lagged_sum|   4|   1000000|     100|0.81184518|  PASSED
              rgb_lagged_sum|   5|   1000000|     100|0.91426183|  PASSED
              rgb_lagged_sum|   6|   1000000|     100|0.43130599|  PASSED
              rgb_lagged_sum|   7|   1000000|     100|0.20481828|  PASSED
              rgb_lagged_sum|   8|   1000000|     100|0.48736601|  PASSED
              rgb_lagged_sum|   9|   1000000|     100|0.93720003|  PASSED
              rgb_lagged_sum|  10|   1000000|     100|0.16670530|  PASSED
              rgb_lagged_sum|  11|   1000000|     100|0.88148050|  PASSED
              rgb_lagged_sum|  12|   1000000|     100|0.67551637|  PASSED
              rgb_lagged_sum|  13|   1000000|     100|0.77455480|  PASSED
              rgb_lagged_sum|  14|   1000000|     100|0.36246394|  PASSED
              rgb_lagged_sum|  15|   1000000|     100|0.12116804|  PASSED
              rgb_lagged_sum|  16|   1000000|     100|0.88373307|  PASSED
              rgb_lagged_sum|  17|   1000000|     100|0.02209034|  PASSED
              rgb_lagged_sum|  18|   1000000|     100|0.92576558|  PASSED
              rgb_lagged_sum|  19|   1000000|     100|0.54040518|  PASSED
              rgb_lagged_sum|  20|   1000000|     100|0.29900201|  PASSED
              rgb_lagged_sum|  21|   1000000|     100|0.23348961|  PASSED
              rgb_lagged_sum|  22|   1000000|     100|0.49675291|  PASSED
              rgb_lagged_sum|  23|   1000000|     100|0.06393575|  PASSED
              rgb_lagged_sum|  24|   1000000|     100|0.60661627|  PASSED
              rgb_lagged_sum|  25|   1000000|     100|0.17661266|  PASSED
              rgb_lagged_sum|  26|   1000000|     100|0.30398633|  PASSED
              rgb_lagged_sum|  27|   1000000|     100|0.85102164|  PASSED
              rgb_lagged_sum|  28|   1000000|     100|0.82477733|  PASSED
              rgb_lagged_sum|  29|   1000000|     100|0.90980482|  PASSED
              rgb_lagged_sum|  30|   1000000|     100|0.66624618|  PASSED
              rgb_lagged_sum|  31|   1000000|     100|0.62473778|  PASSED
              rgb_lagged_sum|  32|   1000000|     100|0.43643499|  PASSED
             rgb_kstest_test|   0|     10000|    1000|0.53860519|  PASSED
             dab_bytedistrib|   0|  51200000|       1|0.24021340|  PASSED
                     dab_dct| 256|     50000|       1|0.51809345|  PASSED
        Preparing to run test 207.  ntuple = 0
                dab_filltree|  32|  15000000|       1|0.00818897|  PASSED
                dab_filltree|  32|  15000000|       1|0.06469865|  PASSED
        Preparing to run test 208.  ntuple = 0
               dab_filltree2|   0|   5000000|       1|0.81755887|  PASSED
               dab_filltree2|   1|   5000000|       1|0.01399998|  PASSED
        Preparing to run test 209.  ntuple = 0
                dab_monobit2|  12|  65000000|       1|0.92987365|  PASSED
Commits on Jul 19, 2017
Commits on Jun 29, 2017
Commits on May 10, 2017
Commits on Apr 18, 2017
  1. Correct a small typo

    moodmosaic committed Apr 18, 2017
Commits on Apr 14, 2017
Commits on Apr 12, 2017
  1. Remove redundant do-notation

    moodmosaic authored and jystic committed Apr 12, 2017
  2. Remove redundant $

    moodmosaic authored and jystic committed Apr 12, 2017
  3. Remove redundant do-notation

    moodmosaic authored and jystic committed Apr 12, 2017
Commits on Apr 9, 2017