digitalmars.D.bugs - [Issue 5249] New: Strongly pure random generator
- d-bugmail puremagic.com (63/63) Nov 21 2010 http://d.puremagic.com/issues/show_bug.cgi?id=5249
- d-bugmail puremagic.com (11/11) Nov 21 2010 http://d.puremagic.com/issues/show_bug.cgi?id=5249
- d-bugmail puremagic.com (8/10) Nov 21 2010 http://d.puremagic.com/issues/show_bug.cgi?id=5249
- d-bugmail puremagic.com (42/42) Nov 21 2010 http://d.puremagic.com/issues/show_bug.cgi?id=5249
- d-bugmail puremagic.com (10/10) Jan 09 2011 http://d.puremagic.com/issues/show_bug.cgi?id=5249
- d-bugmail puremagic.com (46/46) Aug 30 2011 http://d.puremagic.com/issues/show_bug.cgi?id=5249
- d-bugmail puremagic.com (8/8) Nov 15 2012 http://d.puremagic.com/issues/show_bug.cgi?id=5249
- d-bugmail puremagic.com (27/31) Aug 30 2013 http://d.puremagic.com/issues/show_bug.cgi?id=5249
http://d.puremagic.com/issues/show_bug.cgi?id=5249
Summary: Strongly pure random generator
Product: D
Version: D2
Platform: All
OS/Version: All
Status: NEW
Severity: enhancement
Priority: P2
Component: Phobos
AssignedTo: nobody puremagic.com
ReportedBy: bearophile_hugs eml.cc
As pure functions become more and more common in D2 programs, I'd like to
generate some random values inside them too. So I suggest to add to the
std.random module a strongly pure function that keeps no state and generates
random values.
This code shows that it's doable (but it's just for demonstration, because this
pseudo random generator is too much weak):
import std.stdio: writeln;
immutable struct rndPair {
double seed, rnd;
}
// strongly pure
// Probably with DMD 2.050 a std.typecons.Tuple can't
// be used as return value here
pure nothrow rndPair nextRandom(const double seed, const double max) {
enum int IA = 3_877, IC = 29_573, IM = 139_968;
immutable double new_seed = (seed * IA + IC) % IM;
return rndPair(new_seed, max * (new_seed * (1.0 / IM)));
}
// strongly pure
pure double[] foo(const int n, const double firstSeed=42) {
double seed = firstSeed;
auto res = new double[n];
foreach (ref r; res) {
auto seed_rnd = nextRandom(seed, 1.0);
r = seed_rnd.rnd;
seed = seed_rnd.seed;
}
return res;
}
void main() {
writeln(foo(5));
// Output:
// [0.37465, 0.729024, 0.636467, 0.793481, 0.538545]
}
If you want two different strongly pure functions may be added, one good enough
generator and one better generator.
Once some unpacking syntax for tuples is present in DMD the foo() may become
more elegant, similar to (this uses what Andrei calls the 'banana syntax', but
other syntaxes are possible):
pure double[] foo(const int n, const double firstSeed=42) {
double seed = firstSeed;
auto res = new double[n];
foreach (ref r; res)
(|r, seed|) = nextRandom(seed, 1.0);
return res;
}
See also bug 5124
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Nov 21 2010
d-bugmail puremagic.com
http://d.puremagic.com/issues/show_bug.cgi?id=5249
Jonathan M Davis <jmdavisProg gmx.com> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |jmdavisProg gmx.com
PST ---
So, essentially you want a random number generator which is monadic, like you'd
get in a language like Haskell.
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Nov 21 2010
http://d.puremagic.com/issues/show_bug.cgi?id=5249So, essentially you want a random number generator which is monadic, like you'd get in a language like Haskell.Right, but it's not a replacement for the normal random generator, it's one more function added. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Nov 21 2010
http://d.puremagic.com/issues/show_bug.cgi?id=5249
A bit more realistic (but not complete, not commented, etc) test using one of
the rnd generator of the std.random module:
pure nothrow UIntType pureLinearCongruential(UIntType, UIntType a, UIntType c,
UIntType m)
(UIntType x0) {
// perform compile-time tests on a, c, m here...
static if (m) {
UIntType _x = x0 % m; // slow?
static if (is(UIntType == uint) && m == uint.max) {
immutable ulong x = (cast(ulong) a * _x + c);
immutable ulong v = x >> 32;
immutable ulong w = x & uint.max;
immutable y = cast(uint)(v + w);
_x = (y < v || y == uint.max) ? (y + 1) : y;
} else static if (is(UIntType == uint) && m == int.max) {
immutable ulong x = (cast(ulong) a * _x + c);
immutable ulong v = x >> 31;
immutable ulong w = x & int.max;
immutable uint y = cast(uint)(v + w);
_x = (y >= int.max) ? (y - int.max) : y;
} else {
_x = cast(UIntType) ((cast(ulong) a * _x + c) % m);
}
} else {
UIntType _x = a * _x0 + c;
}
return _x;
}
alias pureLinearCongruential!(uint, 16807, 0, 2147483647) pureMinstdRand0;
import std.stdio: writeln;
void main() {
uint rnd = 100000;
foreach (_; 0 .. 10) {
rnd = pureMinstdRand0(rnd);
writeln(rnd);
}
}
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Nov 21 2010
http://d.puremagic.com/issues/show_bug.cgi?id=5249
Andrei Alexandrescu <andrei metalanguage.com> changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|NEW |ASSIGNED
CC| |andrei metalanguage.com
AssignedTo|nobody puremagic.com |andrei metalanguage.com
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jan 09 2011
http://d.puremagic.com/issues/show_bug.cgi?id=5249
In dmd 2.055 you are allowed to assign to an immutable value the result of
strongly pure functions. So purity becomes even more useful, and things that
break purity are even less handy. If you want to fill an array of immutables
you can't currently use uniform() as in gen2() because it's not pure:
import std.random;
struct Foo { int x; }
immutable(Foo[]) gen1(in int n) pure {
auto foos = new Foo[n];
foreach (i, ref f; foos)
f = Foo(i);
return foos;
}
// gen2 can't be pure because of uniform(),
// so I can't cast its result to immutable
const(Foo[]) gen2(in int n) /*pure*/ {
auto foos = new Foo[n];
foreach (ref f; foos)
f = Foo(uniform(0, 100));
return foos;
}
void main() {
immutable foos1 = gen1(10);
//immutable foos2 = gen2(10);
const foos2 = gen2(10);
}
With a strongly pure rnd generator functions you are allowed to generate an
array of immutable random values efficiently (efficiently means without using
array append):
import std.random;
struct Foo { int x; }
Tuple!(Foo[], TSeed) gen3(TSeed)(in int n, in TSeed seed) pure {
auto foos = new Foo[n];
foreach (ref f; foos) {
(int rndValue, seed) = nextUniform(seed, 0, 100);
f = Foo(rndValue);
}
return typeof(return)(foos, seed);
}
void main() {
immutable foos3 = gen3(10);
}
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 30 2011
http://d.puremagic.com/issues/show_bug.cgi?id=5249
bearophile_hugs eml.cc changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|ASSIGNED |NEW
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Nov 15 2012
http://d.puremagic.com/issues/show_bug.cgi?id=5249
Joseph Rushton Wakeling <joseph.wakeling webdrake.net> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |joseph.wakeling webdrake.ne
| |t
2013-08-30 04:33:02 PDT ---
As pure functions become more and more common in D2 programs, I'd like to
generate some random values inside them too. So I suggest to add to the
std.random module a strongly pure function that keeps no state and generates
random values.
It's theoretically possible for quite a few existing RNGs to have a much better
degree of purity.
If we consider the range interface, then we'd like to have:
enum bool empty = false;
auto front() property safe const pure nothrow {}
void popFront() safe pure nothrow {}
Among the current challenges are that the existing design/use of RNGs means
that initialization cannot be assumed, so many (e.g. Mersenne Twister) have
conditions inside front, popFront, etc. which amount to
if (/* is not initialized */)
{
seed();
}
... which kills const (where desirable) and may have an impact on purity as
well.
Some RNGs also have internals which mitigate against safe.
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 30 2013