Re: [Chicken-hackers] [C5] About `random` and its future

[Kooda]

As said on IRC, we could merge this with the packet signing proposal.
If we are going to use the NaCl API for that, we can borrow some random
data procedures as well.

For example the libsodium library has been carefully audited and
provides a nice bunch of procedures :
https://download.libsodium.org/doc/generating_random_data/

___
Chicken-hackers mailing list
Chicken-hackers@nongnu.org
https://lists.nongnu.org/mailman/listinfo/chicken-hackers

Re: [Chicken-hackers] [C5] About `random` and its future

[lemonboy]

Of course finding a solution was a matter of minutes: using `random-bsd`,
`srfi-27` or a custom implementation of some algorithm solves the problem at
hand just fine.

But the point of the proposal is to find out if there's interest in providing a 
better (and portable) random number generator as part of the "(tiny bunch of) 
batteries included".

___
Chicken-hackers mailing list
Chicken-hackers@nongnu.org
https://lists.nongnu.org/mailman/listinfo/chicken-hackers

Re: [Chicken-hackers] [C5] About `random` and its future

[John Cowan]

On Sun, Sep 17, 2017 at 1:43 PM, lemonboy  wrote:

AFAICT the `extras` module contains a bunch of useful procedures to get one
> started writing so it'd be nice if we could choose and implement a single
> PRNG,
> taking advantage of the (light) breakage introduced by C5.
>

Is there anything wrong with SRFI 27 and its MRG32k3a generator?  It's fast,
clean, splittable (you need splitting whenever you are dealing with
independent
random sources and don't want to spend a lot of entropy on them, not just
for
parallel processing), and works well on both 32-bit CPUs (with 64-bit
floats)
and 64-bit CPUs.   I have not seen any indication that MRG32k3a has been
broken.

-- 
John Cowan  http://vrici.lojban.org/~cowanco...@ccil.org
If I have not seen as far as others, it is because giants were standing
on my shoulders.  --Hal Abelson
___
Chicken-hackers mailing list
Chicken-hackers@nongnu.org
https://lists.nongnu.org/mailman/listinfo/chicken-hackers

Re: [Chicken-hackers] [C5] About `random` and its future

[Jim Ursetto]

You could use random-bsd as a drop-in replacement if you want.

http://api.call-cc.org/doc/random-bsd

> On Sep 17, 2017, at 12:43 PM, lemonboy  wrote:
> 
> Hello hackers,
> this time there's no patch and no code involved. I recently had some code that
> used the `random`/`randomize` duo from the `extras` module to do some 
> operations
> on some data. The code came with a modest test suite that worked just fine on 
> my
> laptop but failed when run on other systems running different OSs because of 
> the
> different underlying PRNG implementation used by `random()`.
> 
> Many programming languages offer in their standard library a portable and
> standardized PRNG beside the system's one (or, better, the libc's one) to
> provide a uniform and coherent experience across all the supported systems and
> avoid problems such as the one described just above.
> 
> AFAICT the `extras` module contains a bunch of useful procedures to get one
> started writing so it'd be nice if we could choose and implement a single 
> PRNG,
> taking advantage of the (light) breakage introduced by C5.
> 
> Of course shopping for a PRNG is no easy task so I did some research to get 
> the
> ball rolling, here's a list of contenders:
> 
> * SplittableRandom (aka splitmix64)
>  url: 
> https://www.researchgate.net/publication/273188325_Fast_Splittable_Pseudorandom_Number_Generators
>  (there's a small errata in the paper as outlined here [1])
> 
>  Used by Java, it is pretty simple to implement and has a state consisting of 
> a
>  single u64. There are a few minor caveats with this PRNG like the "small"
>  period of 2^64, I don't think that's a big problem for our use-case.
>  The nice thing about this PRNG is the ability to "split" a single stream but 
>  we may not really need it since CHICKEN is effectively single-threaded (let's
>  have each fork()'ed process have its own stream instead ?)
> 
> * xorshift128+
>  url: http://www.jstatsoft.org/v08/i14/paper / http://xoroshiro.di.unimi.it
> 
>  Implemented by rust, v8, Nim and a few other. Simple in its implementation 
> and
>  very compact (2 u64s) and it has a "big enough" period, it must be carefully
>  seeded [2]. It's been replaced by xoroshiro128 which sports similar qualities
>  and better statistical properties and it's being used in Erlang's OTP library
>  in a slightly different variant made to produce 58bit numbers.
> 
> * ISAAC / ChaCha{12,20}
>  url: http://burtleburtle.net/bob/rand/isaacafa.html
>  (ISAAC's algorithm has been slightly modified in a following paper [4])
> 
>  Those are CSPRNG, yes. Beside the big state required and the relative 
> slowness
>  of those algorithms the only downside I see in using one of those
>  "heavy handed" algorithms is that being stream-based we'd have to implement
>  some buffer-juggling to squeeze a single fixnum out of it.
>  ChaCha20 is what OpenBSD uses for their `arc4random` [3] and rust's `rand`
>  crate implements both at the time of writing [5].
> 
> * PCG
>  url: http://www.pcg-random.org/
> 
>  This is the new kid on the block as you can probably see by the fancy 
> website,
>  this means it hasn't been thoroughly scrutinized and is not battle tested.
>  Nevertheless its the one that's been already adopted by the Crystal
>  programming language and it seems that the next Go iteration is gonna go that
>  way too [6].
>  This one is pretty fast, has a small state, comes in different "sizes" (32,
>  64, 128) while providing a reasonably good output as seen on the website
>  (how much you can trust the results coming from the implementor is still TBD 
> :)
>  and as shown by Daniel Lemire in his blog [7].
> 
> In the end it's all about choosing an algorithm that's good enough for 99% of
> the cases, trying to cover every use case is not going to cut it. I'm no 
> expert
> so feel free to correct whatever error you may find, my English isn't not
> perfect either so you can be pedantic about that if you want. And please do :)
> 
> Thank you for reading,
> LemonBoy
> 
> [1] http://www.pcg-random.org/posts/bugs-in-splitmix.html
> [2] http://www.pcg-random.org/posts/predictability-party-tricks.html
> [3] http://bxr.su/OpenBSD/lib/libc/crypt/arc4random.c
> [4] https://131002.net/data/papers/Aum06b.pdf
> [5] https://doc.rust-lang.org/rand/rand/index.html
> [6] https://github.com/golang/go/issues/21835
> [7] https://lemire.me/blog/
> 
> ___
> Chicken-hackers mailing list
> Chicken-hackers@nongnu.org
> https://lists.nongnu.org/mailman/listinfo/chicken-hackers


___
Chicken-hackers mailing list
Chicken-hackers@nongnu.org
https://lists.nongnu.org/mailman/listinfo/chicken-hackers