www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 5249] New: Strongly pure random generator

reply d-bugmail puremagic.com writes:
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


--- Comment #0 from bearophile_hugs eml.cc 2010-11-21 15:47:51 PST ---
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
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5249


Jonathan M Davis <jmdavisProg gmx.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jmdavisProg gmx.com


--- Comment #1 from Jonathan M Davis <jmdavisProg gmx.com> 2010-11-21 16:37:52
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
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5249



--- Comment #2 from bearophile_hugs eml.cc 2010-11-21 16:40:59 PST ---
(In reply to comment #1)
 So, 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
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5249



--- Comment #3 from bearophile_hugs eml.cc 2010-11-21 20:03:55 PST ---
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
prev sibling next sibling parent d-bugmail puremagic.com writes:
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
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5249



--- Comment #4 from bearophile_hugs eml.cc 2011-08-30 04:49:26 PDT ---
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
prev sibling next sibling parent d-bugmail puremagic.com writes:
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
prev sibling parent d-bugmail puremagic.com writes:
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


--- Comment #5 from Joseph Rushton Wakeling <joseph.wakeling webdrake.net>
2013-08-30 04:33:02 PDT ---
(In reply to comment #0)
 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