Is there an organized effort in PRNG development?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
18 messages Options
Reply | Threaded
Open this post in threaded view
|

Is there an organized effort in PRNG development?

Tomas Lycken

Recently, i’ve stumbled over a couple of interesting posts in various places concerning random number generation, notable examples being Visualizing Algorithms (Mike Bostock) and this post on juliabloggers.com about parallel PRNG by Gray Calhoun. This got me interested to see what the current state and of RNG in Julia is, and if there is any focused effort on pushing forward. Unfortunately, a search among the github issues in the Julia repo didn’t come up with much - most open issues have not been touched in a long time…

In particular, I think it would be a fun learning exercise to try to implement something robust for parallel RNG streams (that can potentially be added to the package by Gray announced in the blog post) and/or N-dimensional version of the Poisson disc distribution (shown e.g. in Visualizing Algorithms). But I feel there might be better places to do this than just writing my own package - if others have already started some work, it would be more fun to collaborate and see if we can put something more complete together. So, is there a focused effort somewhere that I’m missing?

Thanks,

/T

Reply | Threaded
Open this post in threaded view
|

Re: Is there an organized effort in PRNG development?

Andreas Noack
I haven't seen anything, but I have been looking at http://www.deshawresearch.com/resources_random123.html which Stefan Karpinski suggested at some point. They postulate that it can produce independent streams. Unfortunately, it gets quite slow when I wrap it. I wonder if Keno's CXX work will change that.


2014-07-23 16:23 GMT+02:00 Tomas Lycken <[hidden email]>:

Recently, i’ve stumbled over a couple of interesting posts in various places concerning random number generation, notable examples being Visualizing Algorithms (Mike Bostock) and this post on juliabloggers.com about parallel PRNG by Gray Calhoun. This got me interested to see what the current state and of RNG in Julia is, and if there is any focused effort on pushing forward. Unfortunately, a search among the github issues in the Julia repo didn’t come up with much - most open issues have not been touched in a long time…

In particular, I think it would be a fun learning exercise to try to implement something robust for parallel RNG streams (that can potentially be added to the package by Gray announced in the blog post) and/or N-dimensional version of the Poisson disc distribution (shown e.g. in Visualizing Algorithms). But I feel there might be better places to do this than just writing my own package - if others have already started some work, it would be more fun to collaborate and see if we can put something more complete together. So, is there a focused effort somewhere that I’m missing?

Thanks,

/T




--
Med venlig hilsen

Andreas Noack Jensen
Reply | Threaded
Open this post in threaded view
|

Re: Is there an organized effort in PRNG development?

Tomas Lycken
It looks like it's MIT licensed - maybe we could just port it?

// T

On Wednesday, July 23, 2014 4:43:08 PM UTC+2, Andreas Noack wrote:
I haven't seen anything, but I have been looking at <a href="http://www.deshawresearch.com/resources_random123.html" target="_blank" onmousedown="this.href='http://www.google.com/url?q\75http%3A%2F%2Fwww.deshawresearch.com%2Fresources_random123.html\46sa\75D\46sntz\0751\46usg\75AFQjCNEo76P9G8cawhuV7CUoaZiWs8jkog';return true;" onclick="this.href='http://www.google.com/url?q\75http%3A%2F%2Fwww.deshawresearch.com%2Fresources_random123.html\46sa\75D\46sntz\0751\46usg\75AFQjCNEo76P9G8cawhuV7CUoaZiWs8jkog';return true;">http://www.deshawresearch.com/resources_random123.html which Stefan Karpinski suggested at some point. They postulate that it can produce independent streams. Unfortunately, it gets quite slow when I wrap it. I wonder if Keno's CXX work will change that.


2014-07-23 16:23 GMT+02:00 Tomas Lycken <<a href="javascript:" target="_blank" gdf-obfuscated-mailto="4a7dG3NuTVIJ" onmousedown="this.href='javascript:';return true;" onclick="this.href='javascript:';return true;">tomas....@...>:

Recently, i’ve stumbled over a couple of interesting posts in various places concerning random number generation, notable examples being <a href="http://bost.ocks.org/mike/algorithms/" target="_blank" onmousedown="this.href='http://www.google.com/url?q\75http%3A%2F%2Fbost.ocks.org%2Fmike%2Falgorithms%2F\46sa\75D\46sntz\0751\46usg\75AFQjCNH87Vo48-7xpriZQEINLD0Mo95raA';return true;" onclick="this.href='http://www.google.com/url?q\75http%3A%2F%2Fbost.ocks.org%2Fmike%2Falgorithms%2F\46sa\75D\46sntz\0751\46usg\75AFQjCNH87Vo48-7xpriZQEINLD0Mo95raA';return true;">Visualizing Algorithms (Mike Bostock) and <a href="http://www.juliabloggers.com/cobbling-together-parallel-random-number-generation-in-julia/" target="_blank" onmousedown="this.href='http://www.google.com/url?q\75http%3A%2F%2Fwww.juliabloggers.com%2Fcobbling-together-parallel-random-number-generation-in-julia%2F\46sa\75D\46sntz\0751\46usg\75AFQjCNE9cO9bVcPMDpLTllKpriNB2LuEjA';return true;" onclick="this.href='http://www.google.com/url?q\75http%3A%2F%2Fwww.juliabloggers.com%2Fcobbling-together-parallel-random-number-generation-in-julia%2F\46sa\75D\46sntz\0751\46usg\75AFQjCNE9cO9bVcPMDpLTllKpriNB2LuEjA';return true;">this post on juliabloggers.com about parallel PRNG by Gray Calhoun. This got me interested to see what the current state and of RNG in Julia is, and if there is any focused effort on pushing forward. Unfortunately, a search among the github issues in the Julia repo didn’t come up with much - most open issues have not been touched in a long time…

In particular, I think it would be a fun learning exercise to try to implement something robust for parallel RNG streams (that can potentially be added to the package by Gray announced in the blog post) and/or N-dimensional version of the Poisson disc distribution (shown e.g. in Visualizing Algorithms). But I feel there might be better places to do this than just writing my own package - if others have already started some work, it would be more fun to collaborate and see if we can put something more complete together. So, is there a focused effort somewhere that I’m missing?

Thanks,

/T




--
Med venlig hilsen

Andreas Noack Jensen
Reply | Threaded
Open this post in threaded view
|

Re: Is there an organized effort in PRNG development?

Tomas Lycken
(There's also a paper describing the algorithm: http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=6114424&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D6114424)

// T

On Wednesday, July 23, 2014 4:51:10 PM UTC+2, Tomas Lycken wrote:
It looks like it's MIT licensed - maybe we could just port it?

// T

On Wednesday, July 23, 2014 4:43:08 PM UTC+2, Andreas Noack wrote:
I haven't seen anything, but I have been looking at <a href="http://www.deshawresearch.com/resources_random123.html" target="_blank" onmousedown="this.href='http://www.google.com/url?q\75http%3A%2F%2Fwww.deshawresearch.com%2Fresources_random123.html\46sa\75D\46sntz\0751\46usg\75AFQjCNEo76P9G8cawhuV7CUoaZiWs8jkog';return true;" onclick="this.href='http://www.google.com/url?q\75http%3A%2F%2Fwww.deshawresearch.com%2Fresources_random123.html\46sa\75D\46sntz\0751\46usg\75AFQjCNEo76P9G8cawhuV7CUoaZiWs8jkog';return true;">http://www.deshawresearch.com/resources_random123.html which Stefan Karpinski suggested at some point. They postulate that it can produce independent streams. Unfortunately, it gets quite slow when I wrap it. I wonder if Keno's CXX work will change that.


2014-07-23 16:23 GMT+02:00 Tomas Lycken <[hidden email]>:

Recently, i’ve stumbled over a couple of interesting posts in various places concerning random number generation, notable examples being <a href="http://bost.ocks.org/mike/algorithms/" target="_blank" onmousedown="this.href='http://www.google.com/url?q\75http%3A%2F%2Fbost.ocks.org%2Fmike%2Falgorithms%2F\46sa\75D\46sntz\0751\46usg\75AFQjCNH87Vo48-7xpriZQEINLD0Mo95raA';return true;" onclick="this.href='http://www.google.com/url?q\75http%3A%2F%2Fbost.ocks.org%2Fmike%2Falgorithms%2F\46sa\75D\46sntz\0751\46usg\75AFQjCNH87Vo48-7xpriZQEINLD0Mo95raA';return true;">Visualizing Algorithms (Mike Bostock) and <a href="http://www.juliabloggers.com/cobbling-together-parallel-random-number-generation-in-julia/" target="_blank" onmousedown="this.href='http://www.google.com/url?q\75http%3A%2F%2Fwww.juliabloggers.com%2Fcobbling-together-parallel-random-number-generation-in-julia%2F\46sa\75D\46sntz\0751\46usg\75AFQjCNE9cO9bVcPMDpLTllKpriNB2LuEjA';return true;" onclick="this.href='http://www.google.com/url?q\75http%3A%2F%2Fwww.juliabloggers.com%2Fcobbling-together-parallel-random-number-generation-in-julia%2F\46sa\75D\46sntz\0751\46usg\75AFQjCNE9cO9bVcPMDpLTllKpriNB2LuEjA';return true;">this post on juliabloggers.com about parallel PRNG by Gray Calhoun. This got me interested to see what the current state and of RNG in Julia is, and if there is any focused effort on pushing forward. Unfortunately, a search among the github issues in the Julia repo didn’t come up with much - most open issues have not been touched in a long time…

In particular, I think it would be a fun learning exercise to try to implement something robust for parallel RNG streams (that can potentially be added to the package by Gray announced in the blog post) and/or N-dimensional version of the Poisson disc distribution (shown e.g. in Visualizing Algorithms). But I feel there might be better places to do this than just writing my own package - if others have already started some work, it would be more fun to collaborate and see if we can put something more complete together. So, is there a focused effort somewhere that I’m missing?

Thanks,

/T




--
Med venlig hilsen

Andreas Noack Jensen
Reply | Threaded
Open this post in threaded view
|

Re: Is there an organized effort in PRNG development?

Andreas Noack
I have translated some of it already, but the C-source uses fancy instructions which makes it difficult to match in terms of speed. Maybe this will change and maybe it is okay with a small speed penalty if it is ensured that the streams are independent. The library also has cryptographic RNG's which could also be interesting to have.


2014-07-23 16:53 GMT+02:00 Tomas Lycken <[hidden email]>:
(There's also a paper describing the algorithm: http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=6114424&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D6114424)

// T


On Wednesday, July 23, 2014 4:51:10 PM UTC+2, Tomas Lycken wrote:
It looks like it's MIT licensed - maybe we could just port it?

// T

On Wednesday, July 23, 2014 4:43:08 PM UTC+2, Andreas Noack wrote:
I haven't seen anything, but I have been looking at http://www.deshawresearch.com/resources_random123.html which Stefan Karpinski suggested at some point. They postulate that it can produce independent streams. Unfortunately, it gets quite slow when I wrap it. I wonder if Keno's CXX work will change that.


2014-07-23 16:23 GMT+02:00 Tomas Lycken <[hidden email]>:

Recently, i’ve stumbled over a couple of interesting posts in various places concerning random number generation, notable examples being Visualizing Algorithms (Mike Bostock) and this post on juliabloggers.com about parallel PRNG by Gray Calhoun. This got me interested to see what the current state and of RNG in Julia is, and if there is any focused effort on pushing forward. Unfortunately, a search among the github issues in the Julia repo didn’t come up with much - most open issues have not been touched in a long time…

In particular, I think it would be a fun learning exercise to try to implement something robust for parallel RNG streams (that can potentially be added to the package by Gray announced in the blog post) and/or N-dimensional version of the Poisson disc distribution (shown e.g. in Visualizing Algorithms). But I feel there might be better places to do this than just writing my own package - if others have already started some work, it would be more fun to collaborate and see if we can put something more complete together. So, is there a focused effort somewhere that I’m missing?

Thanks,

/T




--
Med venlig hilsen

Andreas Noack Jensen



--
Med venlig hilsen

Andreas Noack Jensen
Reply | Threaded
Open this post in threaded view
|

Re: Is there an organized effort in PRNG development?

Stefan Karpinski-2
What kind of fancy instructions?

On Jul 23, 2014, at 8:04 AM, Andreas Noack <[hidden email]> wrote:

I have translated some of it already, but the C-source uses fancy instructions which makes it difficult to match in terms of speed. Maybe this will change and maybe it is okay with a small speed penalty if it is ensured that the streams are independent. The library also has cryptographic RNG's which could also be interesting to have.


2014-07-23 16:53 GMT+02:00 Tomas Lycken <[hidden email]>:
(There's also a paper describing the algorithm: http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=6114424&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D6114424)

// T


On Wednesday, July 23, 2014 4:51:10 PM UTC+2, Tomas Lycken wrote:
It looks like it's MIT licensed - maybe we could just port it?

// T

On Wednesday, July 23, 2014 4:43:08 PM UTC+2, Andreas Noack wrote:
I haven't seen anything, but I have been looking at http://www.deshawresearch.com/resources_random123.html which Stefan Karpinski suggested at some point. They postulate that it can produce independent streams. Unfortunately, it gets quite slow when I wrap it. I wonder if Keno's CXX work will change that.


2014-07-23 16:23 GMT+02:00 Tomas Lycken <[hidden email]>:

Recently, i’ve stumbled over a couple of interesting posts in various places concerning random number generation, notable examples being Visualizing Algorithms (Mike Bostock) and this post on juliabloggers.com about parallel PRNG by Gray Calhoun. This got me interested to see what the current state and of RNG in Julia is, and if there is any focused effort on pushing forward. Unfortunately, a search among the github issues in the Julia repo didn’t come up with much - most open issues have not been touched in a long time…

In particular, I think it would be a fun learning exercise to try to implement something robust for parallel RNG streams (that can potentially be added to the package by Gray announced in the blog post) and/or N-dimensional version of the Poisson disc distribution (shown e.g. in Visualizing Algorithms). But I feel there might be better places to do this than just writing my own package - if others have already started some work, it would be more fun to collaborate and see if we can put something more complete together. So, is there a focused effort somewhere that I’m missing?

Thanks,

/T




--
Med venlig hilsen

Andreas Noack Jensen



--
Med venlig hilsen

Andreas Noack Jensen
Reply | Threaded
Open this post in threaded view
|

Re: Is there an organized effort in PRNG development?

Andreas Noack
SIMD, I think. There are things in the code that I don't understand and the library is much faster in the C version compared to my translation. The actual algorithm is not that hard to follow.


2014-07-23 17:08 GMT+02:00 Stefan Karpinski <[hidden email]>:
What kind of fancy instructions?

On Jul 23, 2014, at 8:04 AM, Andreas Noack <[hidden email]> wrote:

I have translated some of it already, but the C-source uses fancy instructions which makes it difficult to match in terms of speed. Maybe this will change and maybe it is okay with a small speed penalty if it is ensured that the streams are independent. The library also has cryptographic RNG's which could also be interesting to have.


2014-07-23 16:53 GMT+02:00 Tomas Lycken <[hidden email]>:
(There's also a paper describing the algorithm: http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=6114424&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D6114424)

// T


On Wednesday, July 23, 2014 4:51:10 PM UTC+2, Tomas Lycken wrote:
It looks like it's MIT licensed - maybe we could just port it?

// T

On Wednesday, July 23, 2014 4:43:08 PM UTC+2, Andreas Noack wrote:
I haven't seen anything, but I have been looking at http://www.deshawresearch.com/resources_random123.html which Stefan Karpinski suggested at some point. They postulate that it can produce independent streams. Unfortunately, it gets quite slow when I wrap it. I wonder if Keno's CXX work will change that.


2014-07-23 16:23 GMT+02:00 Tomas Lycken <[hidden email]>:

Recently, i’ve stumbled over a couple of interesting posts in various places concerning random number generation, notable examples being Visualizing Algorithms (Mike Bostock) and this post on juliabloggers.com about parallel PRNG by Gray Calhoun. This got me interested to see what the current state and of RNG in Julia is, and if there is any focused effort on pushing forward. Unfortunately, a search among the github issues in the Julia repo didn’t come up with much - most open issues have not been touched in a long time…

In particular, I think it would be a fun learning exercise to try to implement something robust for parallel RNG streams (that can potentially be added to the package by Gray announced in the blog post) and/or N-dimensional version of the Poisson disc distribution (shown e.g. in Visualizing Algorithms). But I feel there might be better places to do this than just writing my own package - if others have already started some work, it would be more fun to collaborate and see if we can put something more complete together. So, is there a focused effort somewhere that I’m missing?

Thanks,

/T




--
Med venlig hilsen

Andreas Noack Jensen



--
Med venlig hilsen

Andreas Noack Jensen



--
Med venlig hilsen

Andreas Noack Jensen
Reply | Threaded
Open this post in threaded view
|

Re: Is there an organized effort in PRNG development?

Stefan Karpinski
Well, maybe we could investigate using inline LLVM for this. Keno has an llvmcall branch which might be applicable. Is the C version, when called from C and presumably inlined comparable to dSFMT?


On Wed, Jul 23, 2014 at 8:11 AM, Andreas Noack <[hidden email]> wrote:
SIMD, I think. There are things in the code that I don't understand and the library is much faster in the C version compared to my translation. The actual algorithm is not that hard to follow.


2014-07-23 17:08 GMT+02:00 Stefan Karpinski <[hidden email]>:

What kind of fancy instructions?

On Jul 23, 2014, at 8:04 AM, Andreas Noack <[hidden email]> wrote:

I have translated some of it already, but the C-source uses fancy instructions which makes it difficult to match in terms of speed. Maybe this will change and maybe it is okay with a small speed penalty if it is ensured that the streams are independent. The library also has cryptographic RNG's which could also be interesting to have.


2014-07-23 16:53 GMT+02:00 Tomas Lycken <[hidden email]>:
(There's also a paper describing the algorithm: http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=6114424&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D6114424)

// T


On Wednesday, July 23, 2014 4:51:10 PM UTC+2, Tomas Lycken wrote:
It looks like it's MIT licensed - maybe we could just port it?

// T

On Wednesday, July 23, 2014 4:43:08 PM UTC+2, Andreas Noack wrote:
I haven't seen anything, but I have been looking at http://www.deshawresearch.com/resources_random123.html which Stefan Karpinski suggested at some point. They postulate that it can produce independent streams. Unfortunately, it gets quite slow when I wrap it. I wonder if Keno's CXX work will change that.


2014-07-23 16:23 GMT+02:00 Tomas Lycken <[hidden email]>:

Recently, i’ve stumbled over a couple of interesting posts in various places concerning random number generation, notable examples being Visualizing Algorithms (Mike Bostock) and this post on juliabloggers.com about parallel PRNG by Gray Calhoun. This got me interested to see what the current state and of RNG in Julia is, and if there is any focused effort on pushing forward. Unfortunately, a search among the github issues in the Julia repo didn’t come up with much - most open issues have not been touched in a long time…

In particular, I think it would be a fun learning exercise to try to implement something robust for parallel RNG streams (that can potentially be added to the package by Gray announced in the blog post) and/or N-dimensional version of the Poisson disc distribution (shown e.g. in Visualizing Algorithms). But I feel there might be better places to do this than just writing my own package - if others have already started some work, it would be more fun to collaborate and see if we can put something more complete together. So, is there a focused effort somewhere that I’m missing?

Thanks,

/T




--
Med venlig hilsen

Andreas Noack Jensen



--
Med venlig hilsen

Andreas Noack Jensen



--
Med venlig hilsen

Andreas Noack Jensen

Reply | Threaded
Open this post in threaded view
|

Re: Is there an organized effort in PRNG development?

Gray Calhoun
In reply to this post by Tomas Lycken
On Wednesday, July 23, 2014 9:23:17 AM UTC-5, Tomas Lycken wrote:

> Recently, i’ve stumbled over a couple of interesting posts in
> various places concerning random number generation, notable examples
> being Visualizing Algorithms (Mike Bostock) and this post on
> juliabloggers.com about parallel PRNG by Gray Calhoun. This got me
> interested to see what the current state and of RNG in Julia is, and
> if there is any focused effort on pushing forward. Unfortunately, a
> search among the github issues in the Julia repo didn’t come up with
> much - most open issues have not been touched in a long time…
>
> In particular, I think it would be a fun learning exercise to try to
> implement something robust for parallel RNG streams (that can
> potentially be added to the package by Gray announced in the blog
> post) and/or N-dimensional version of the Poisson disc distribution
> (shown e.g. in Visualizing Algorithms). But I feel there might be
> better places to do this than just writing my own package - if
> others have already started some work, it would be more fun to
> collaborate and see if we can put something more complete
> together. So, is there a focused effort somewhere that I’m missing?

Hi Tomas, thanks for bringing this up. I have a few thoughts on this :)

A reliable and well-tested parallel RNG is going to be necessary for
some of Julia's natural applications (e.g. stochastic simulations). A
good starting point might be L'Ecuyer's RNG. He provides C and C++
code here:

http://www.iro.umontreal.ca/~lecuyer/myftp/streams00

but it's usable under "noncommercial use only." There seems to be a
GPL version of the same source code contained in R's (depreciated)
"rlecuyer" package:

http://cran.r-project.org/web/packages/rlecuyer

I think (maybe mistakenly) that the Julia community prefers to not use
the GPL, but wrapping L'Ecuyer's existing code could be a good
starting point, and the codebase would be very useful in a separate
package as a reference implementation even if it gets rewritten under
a different license. (i.e. to verify that new versions give identical
output.) I'm most concerned about having reliable implementations of
widely used RNGs, and the code in R is widely used, so it should be
fairly solid by now.

It should be straightforward to put new RNGs in a new package, so
that's something that anyone could start working on quickly. But it
looks like there needs to be some coordination on how RNGs integrate
with Julia and packages. As far as I can tell, there's no way to
replace the default RNG --- rand() without arguments looks like it's
hard-coded to a particular C call [1] --- and the packages I've looked
at (Distributions and MCMC) don't seem to allow the use of non-default
RNGs. I assume it would be simple to add methods for
rand(r::AbstractRNG, whatever) to these packages, but there should
probably be some consensus about the best way to do it.

Of course, that's probably only important when there's more than one
RNG, so it might not be a priority yet.

[1] https://github.com/JuliaLang/julia/blob/29b83d1776aac160e4cf7cb1e897bde579d7f1ff/base/random.jl#L89

and

https://github.com/JuliaLang/julia/blob/29b83d1776aac160e4cf7cb1e897bde579d7f1ff/base/dSFMT.jl#L67

--Gray

<http://gray.clhn.co>

Reply | Threaded
Open this post in threaded view
|

Re: Is there an organized effort in PRNG development?

Simon Byrne


On Thursday, 24 July 2014 03:59:36 UTC+1, Gray Calhoun wrote:
... the packages I've looked
at (Distributions and MCMC) don't seem to allow the use of non-default
RNGs. I assume it would be simple to add methods for
rand(r::AbstractRNG, whatever) to these packages, but there should
probably be some consensus about the best way to do it.

This is the eventual plan, but we need to remove the dependence on Rmath first, see:
https://github.com/JuliaStats/Distributions.jl/issues/197 

-simon
Reply | Threaded
Open this post in threaded view
|

Re: Is there an organized effort in PRNG development?

Viral Shah
In reply to this post by Tomas Lycken
One possibility is just to implement the dsfmt jump algorithm in Julia. It should hopefully not be too difficult. Then, set the state of the RNG, and you can get multiple streams, which should be good to go for us for parallel RNGs.

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/JUMP/dsfmt-jump.html

-viral

On Wednesday, July 23, 2014 7:53:17 PM UTC+5:30, Tomas Lycken wrote:

Recently, i’ve stumbled over a couple of interesting posts in various places concerning random number generation, notable examples being <a href="http://bost.ocks.org/mike/algorithms/" target="_blank" onmousedown="this.href='http://www.google.com/url?q\75http%3A%2F%2Fbost.ocks.org%2Fmike%2Falgorithms%2F\46sa\75D\46sntz\0751\46usg\75AFQjCNH87Vo48-7xpriZQEINLD0Mo95raA';return true;" onclick="this.href='http://www.google.com/url?q\75http%3A%2F%2Fbost.ocks.org%2Fmike%2Falgorithms%2F\46sa\75D\46sntz\0751\46usg\75AFQjCNH87Vo48-7xpriZQEINLD0Mo95raA';return true;">Visualizing Algorithms (Mike Bostock) and <a href="http://www.juliabloggers.com/cobbling-together-parallel-random-number-generation-in-julia/" target="_blank" onmousedown="this.href='http://www.google.com/url?q\75http%3A%2F%2Fwww.juliabloggers.com%2Fcobbling-together-parallel-random-number-generation-in-julia%2F\46sa\75D\46sntz\0751\46usg\75AFQjCNE9cO9bVcPMDpLTllKpriNB2LuEjA';return true;" onclick="this.href='http://www.google.com/url?q\75http%3A%2F%2Fwww.juliabloggers.com%2Fcobbling-together-parallel-random-number-generation-in-julia%2F\46sa\75D\46sntz\0751\46usg\75AFQjCNE9cO9bVcPMDpLTllKpriNB2LuEjA';return true;">this post on juliabloggers.com about parallel PRNG by Gray Calhoun. This got me interested to see what the current state and of RNG in Julia is, and if there is any focused effort on pushing forward. Unfortunately, a search among the github issues in the Julia repo didn’t come up with much - most open issues have not been touched in a long time…

In particular, I think it would be a fun learning exercise to try to implement something robust for parallel RNG streams (that can potentially be added to the package by Gray announced in the blog post) and/or N-dimensional version of the Poisson disc distribution (shown e.g. in Visualizing Algorithms). But I feel there might be better places to do this than just writing my own package - if others have already started some work, it would be more fun to collaborate and see if we can put something more complete together. So, is there a focused effort somewhere that I’m missing?

Thanks,

/T

Reply | Threaded
Open this post in threaded view
|

Re: Is there an organized effort in PRNG development?

Viral Shah
In reply to this post by Simon Byrne


On Thursday, July 24, 2014 1:12:26 PM UTC+5:30, Simon Byrne wrote:


On Thursday, 24 July 2014 03:59:36 UTC+1, Gray Calhoun wrote:
... the packages I've looked
at (Distributions and MCMC) don't seem to allow the use of non-default
RNGs. I assume it would be simple to add methods for
rand(r::AbstractRNG, whatever) to these packages, but there should
probably be some consensus about the best way to do it.

This is the eventual plan, but we need to remove the dependence on Rmath first, see:
<a href="https://github.com/JuliaStats/Distributions.jl/issues/197" target="_blank" onmousedown="this.href='https://www.google.com/url?q\75https%3A%2F%2Fgithub.com%2FJuliaStats%2FDistributions.jl%2Fissues%2F197\46sa\75D\46sntz\0751\46usg\75AFQjCNFRF2A1l-wHiDUWOKFx2D4bsfqOAw';return true;" onclick="this.href='https://www.google.com/url?q\75https%3A%2F%2Fgithub.com%2FJuliaStats%2FDistributions.jl%2Fissues%2F197\46sa\75D\46sntz\0751\46usg\75AFQjCNFRF2A1l-wHiDUWOKFx2D4bsfqOAw';return true;">https://github.com/JuliaStats/Distributions.jl/issues/197 

Also, it is not difficult to make Rmath use our AbstractRNG, but given that we want to move away from it, the effort doesn't seem worthwhile.

-viral 


 
Reply | Threaded
Open this post in threaded view
|

Re: Is there an organized effort in PRNG development?

Gray Calhoun
In reply to this post by Simon Byrne
Simon Byrne: (12:42AM on Thu, Jul 24)

>On Thursday, 24 July 2014 03:59:36 UTC+1, Gray Calhoun wrote:
>> ... the packages I've looked
>> at (Distributions and MCMC) don't seem to allow the use of non-default
>> RNGs. I assume it would be simple to add methods for
>> rand(r::AbstractRNG, whatever) to these packages, but there should
>> probably be some consensus about the best way to do it.
>
>This is the eventual plan, but we need to remove the dependence on Rmath
>first, see:
>https://github.com/JuliaStats/Distributions.jl/issues/197

Okay, that makes a lot of sense. Thanks for pointing out that discussion.

--Gray
Reply | Threaded
Open this post in threaded view
|

Re: Is there an organized effort in PRNG development?

Gray Calhoun
In reply to this post by Viral Shah
Viral Shah: (05:52AM on Thu, Jul 24)

>On Thursday, July 24, 2014 1:12:26 PM UTC+5:30, Simon Byrne wrote:
>> On Thursday, 24 July 2014 03:59:36 UTC+1, Gray Calhoun wrote:
>>> ... the packages I've looked
>>> at (Distributions and MCMC) don't seem to allow the use of non-default
>>> RNGs. I assume it would be simple to add methods for
>>> rand(r::AbstractRNG, whatever) to these packages, but there should
>>> probably be some consensus about the best way to do it.
>>
>> This is the eventual plan, but we need to remove the dependence on Rmath
>> first, see:
>> https://github.com/JuliaStats/Distributions.jl/issues/197
>
>Also, it is not difficult to make Rmath use our AbstractRNG, but given that
>we want to move away from it, the effort doesn't seem worthwhile.

So, let me start by apologizing for reopening a topic that's probably
been heavily discussed already. That said...

If the goal is to appeal to statisticians, it might be worthwhile to
keep RMath up to date as a separate & optional implementation of some
of these functions; and also track future updates made in R. Most
academic users (and I imagine many consultants too) aren't going to
care about licensing, and may need to be able to be able to
(re)produce identical results to work done in R (and future versions
of R).

Also, the R code is heavily used and may be viewed as more reliable
than other implementations, at least for a little while, so some users
could prefer it --- statisticians in particular. It would be really
nice to give those users that option entirely in Julia.

Of course, separating out (and maintaining!) an optional
implementation of that code is a bunch of work.

--Gray
Reply | Threaded
Open this post in threaded view
|

Re: Is there an organized effort in PRNG development?

John Myles White
One problem with using RMath is that it currently uses our RNG, which means that it doesn't produces the same answers as R would. If it were switched back to using the RNG that R uses, it would produce answers that are inconsistent with those Julia would produce.

Still worth exploring, but I think somebody needs to claim that task as their own project for it to get done.

 -- John

On Jul 24, 2014, at 9:01 AM, Gray Calhoun <[hidden email]> wrote:

> Viral Shah: (05:52AM on Thu, Jul 24)
>> On Thursday, July 24, 2014 1:12:26 PM UTC+5:30, Simon Byrne wrote:
>>> On Thursday, 24 July 2014 03:59:36 UTC+1, Gray Calhoun wrote:
>>>> ... the packages I've looked
>>>> at (Distributions and MCMC) don't seem to allow the use of non-default
>>>> RNGs. I assume it would be simple to add methods for
>>>> rand(r::AbstractRNG, whatever) to these packages, but there should
>>>> probably be some consensus about the best way to do it.
>>>
>>> This is the eventual plan, but we need to remove the dependence on Rmath
>>> first, see:
>>> https://github.com/JuliaStats/Distributions.jl/issues/197
>>
>> Also, it is not difficult to make Rmath use our AbstractRNG, but given that
>> we want to move away from it, the effort doesn't seem worthwhile.
>
> So, let me start by apologizing for reopening a topic that's probably
> been heavily discussed already. That said...
>
> If the goal is to appeal to statisticians, it might be worthwhile to
> keep RMath up to date as a separate & optional implementation of some
> of these functions; and also track future updates made in R. Most
> academic users (and I imagine many consultants too) aren't going to
> care about licensing, and may need to be able to be able to
> (re)produce identical results to work done in R (and future versions
> of R).
>
> Also, the R code is heavily used and may be viewed as more reliable
> than other implementations, at least for a little while, so some users
> could prefer it --- statisticians in particular. It would be really
> nice to give those users that option entirely in Julia.
>
> Of course, separating out (and maintaining!) an optional
> implementation of that code is a bunch of work.
>
> --Gray

Reply | Threaded
Open this post in threaded view
|

Re: Is there an organized effort in PRNG development?

Gray Calhoun
Didn't mean to imply that other people should be doing more work. If
there's support for it, I'd be happy to give it a try.

--Gray

John Myles White: (09:46AM on Thu, Jul 24)

>One problem with using RMath is that it currently uses our RNG, which
>means that it doesn't produces the same answers as R would. If it
>were switched back to using the RNG that R uses, it would produce
>answers that are inconsistent with those Julia would produce.
>
>Still worth exploring, but I think somebody needs to claim that task
>as their own project for it to get done.
>
> -- John
>
>On Jul 24, 2014, at 9:01 AM, Gray Calhoun <[hidden email]> wrote:
[cut...]

>> If the goal is to appeal to statisticians, it might be worthwhile to
>> keep RMath up to date as a separate & optional implementation of some
>> of these functions; and also track future updates made in R. Most
>> academic users (and I imagine many consultants too) aren't going to
>> care about licensing, and may need to be able to be able to
>> (re)produce identical results to work done in R (and future versions
>> of R).
>>
>> Also, the R code is heavily used and may be viewed as more reliable
>> than other implementations, at least for a little while, so some users
>> could prefer it --- statisticians in particular. It would be really
>> nice to give those users that option entirely in Julia.
>>
>> Of course, separating out (and maintaining!) an optional
>> implementation of that code is a bunch of work.
Reply | Threaded
Open this post in threaded view
|

Re: Is there an organized effort in PRNG development?

John Myles White
Don't worry about it. Personally I don't see why there wouldn't be support for your idea since it doesn't seem to have any potential to break anything.

 -- John

On Jul 24, 2014, at 10:00 AM, Gray Calhoun <[hidden email]> wrote:

> Didn't mean to imply that other people should be doing more work. If
> there's support for it, I'd be happy to give it a try.
>
> --Gray
>
> John Myles White: (09:46AM on Thu, Jul 24)
>> One problem with using RMath is that it currently uses our RNG, which
>> means that it doesn't produces the same answers as R would. If it
>> were switched back to using the RNG that R uses, it would produce
>> answers that are inconsistent with those Julia would produce.
>>
>> Still worth exploring, but I think somebody needs to claim that task
>> as their own project for it to get done.
>>
>> -- John
>>
>> On Jul 24, 2014, at 9:01 AM, Gray Calhoun <[hidden email]> wrote:
> [cut...]
>>> If the goal is to appeal to statisticians, it might be worthwhile to
>>> keep RMath up to date as a separate & optional implementation of some
>>> of these functions; and also track future updates made in R. Most
>>> academic users (and I imagine many consultants too) aren't going to
>>> care about licensing, and may need to be able to be able to
>>> (re)produce identical results to work done in R (and future versions
>>> of R).
>>>
>>> Also, the R code is heavily used and may be viewed as more reliable
>>> than other implementations, at least for a little while, so some users
>>> could prefer it --- statisticians in particular. It would be really
>>> nice to give those users that option entirely in Julia.
>>>
>>> Of course, separating out (and maintaining!) an optional
>>> implementation of that code is a bunch of work.

Reply | Threaded
Open this post in threaded view
|

Re: Is there an organized effort in PRNG development?

Jason Riedy
In reply to this post by Andreas Noack
And Andreas Noack writes:
> I haven't seen anything, but I have been looking at http://
> www.deshawresearch.com/resources_random123.html which Stefan
> Karpinski suggested at some point. They postulate that it can produce
> independent streams.

Actually, Random123 is a collection of hash functions.  They're
not cryptographically strong but can be fast PRNGs if used just
right.  They can be used as a typical PRNG, but the real strength
(imho) is in being utterly reproducible once you define your
problem space as a set of indices used as hash inputs.  For
parallel streams you just slice those indices however your
parallelism does and keep the reproducibility no matter the
distribution.  To get full speed, you also need to use all 128
bits output from a single call.  (You also can cheat and never
store your random input; just recompute based on the indices.
Handy for "big data" benchmarks.)

One problem with Random123 is that the contact email address is a
black hole.  I added platforms (e.g. xlc & Power7+) a few years
ago and sent the patch.  They never responded, yet late last year
the added some of same platforms.