[m-users.] Announcement: mercury-mt Mercury only Mersenne Twister random numbers

[Mark Clements]

Mark,

This is very helpful - thank you.

I have now: dropped the grounded implementation; renamed the unique implementation to "mt"; added an array.copy() to ensure that the old state array is not updated; included a derived shared random type, including runif() and set_seed() predicates; and revised the test.

Kindly, Mark.
________________________________
From: Mark Brown <mark at mercurylang.org>
Sent: 20 February 2023 14:32
To: Mark Clements <mark.clements at ki.se>
Cc: users <users at lists.mercurylang.org>
Subject: Re: [m-users.] Announcement: mercury-mt Mercury only Mersenne Twister random numbers

[You don't often get email from mark at mercurylang.org. Learn why this is important at https://aka.ms/LearnAboutSenderIdentification ]

Hi Mark,

As Volker said, thanks for sharing your work.  In regards to your question,

> Question for Mercury users: is it better to do this as a ground generator or as a unique generator?

Short answer: it's generally best for a library to supply as many
instances as it can correctly implement.  For this application it
would be better to implement it as a unique generator, and use
adapters to make other instances as needed.

Long answer: the choice for the user is similar to the choice of
whether or not to use destructive update in other circumstances.  If
there is a significant amount of state that is frequently updated,
then destructive update is probably worthwhile even though the user
will need to manage uniqueness as a result.  Since MT requires about
2.5k of state and is likely to be used when lots of calls are made,
the unique generator will be the one that most users would want.

If a shared generator is required by the user and they don't mind
copying the state for every number generated, this can be done with
one of the adapters down near the bottom of the random.m interface
rather than re-implementing the algorithm. For example, you can import
mt_unique and define a type:

    :- type random == shared_random(params, ustate).

Then create a generator as follows:

    seed(12345u32, P, R),
    S0 = make_shared_random(P, R)

See the attached file test_mt_1.m.

It's also possible to attach a generator to the I/O state using
make_io_urandom, so that the generator can be used more conveniently
without copying, and without the generator itself needing to be
unique.

The "ugly truth" answer: the shared implementation you've given still
uses arrays underneath, and these are destructively updated and aren't
supposed to be shared.  As a consequence this typeclass instance
doesn't behave correctly if the generator is not actually used in a
unique way.  For example, if the runif test was called twice in
sequence, passing the final state from the first call as the initial
state of the second, we'd expect to observe different numbers.  If it
was run a third time, using the *first* state, it should reproduce the
first numbers again, but the attached file test_mt_2.m shows that it
doesn't.

The underlying problem is that if arrays are put in data structures,
and you refer to an array that has been elsewhere updated, you can get
the new value when logically it should return the old value.  The
correct way to handle this, aside from not referring to old arrays in
the first place, is to copy arrays when required.  That's what the
shared adapter does via urandom_dup   Ideally, the compiler would
check that this is done correctly, but unfortunately the current
implementation doesn't always do that - see the caveat at the start of
array.m.

I've included in the above test some code to demonstrate the problem
just with arrays on their own.

Shortest answer: I'll add some docs to the random.m module to clarify
for instance implementors.  :-)

Hope this helps!

Mark

On Sun, Feb 12, 2023 at 12:38 AM Mark Clements <mark.clements at ki.se> wrote:
>
> I have written a Mercury-only implementation of the Mersenne Twister random number generator. This is a very common and reasonably good pseudo random number generator. For details:
>
> https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fmclements%2Fmercury-mt&data=05%7C01%7Cmark.clements%40ki.se%7Cb48b433f28744e59a55d08db1346e47e%7Cbff7eef1cf4b4f32be3da1dda043c05d%7C0%7C0%7C638124967789194891%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000%7C%7C%7C&sdata=V4x8%2FyBaB5Eh11m73B2k4x9RhVEqTJVGyaAoT6Tc2DM%3D&reserved=0
>
> Sincerely, Mark.
>
>
> När du skickar e-post till Karolinska Institutet (KI) innebär detta att KI kommer att behandla dina personuppgifter. Här finns information om hur KI behandlar personuppgifter<https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fki.se%2Fmedarbetare%2Fintegritetsskyddspolicy&data=05%7C01%7Cmark.clements%40ki.se%7Cb48b433f28744e59a55d08db1346e47e%7Cbff7eef1cf4b4f32be3da1dda043c05d%7C0%7C0%7C638124967789194891%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000%7C%7C%7C&sdata=B7iJrTi5U7KcEbmXLh%2ByzeNZUQo9nq67xEsspy48Qu0%3D&reserved=0>.
>
>
> Sending email to Karolinska Institutet (KI) will result in KI processing your personal data. You can read more about KI’s processing of personal data here<https://ki.se/en/staff/data-protection-policy>.
> _______________________________________________
> users mailing list
> users at lists.mercurylang.org
> https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Flists.mercurylang.org%2Flistinfo%2Fusers&data=05%7C01%7Cmark.clements%40ki.se%7Cb48b433f28744e59a55d08db1346e47e%7Cbff7eef1cf4b4f32be3da1dda043c05d%7C0%7C0%7C638124967789194891%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000%7C%7C%7C&sdata=Ztb33y1WBBmyQA%2B3aasFSbbzuHOMATU0a10NxMYN0Xw%3D&reserved=0
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mercurylang.org/archives/users/attachments/20230304/26142f32/attachment.html>