Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!news.roellig-ltd.de!open-news-network.org!border2.nntp.ams1.giganews.com!nntp.giganews.com!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Date: Sun, 07 Jun 2015 12:41:53 +0200
From: Jonas Wielicki <jonas@wielicki.name>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.7.0
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: Testing random
References: <87oaksowwg.fsf@Equus.decebal.nl>
In-Reply-To: <87oaksowwg.fsf@Equus.decebal.nl>
Content-Type: multipart/signed; micalg=pgp-sha512; protocol="application/pgp-signature"; boundary="1GKjhpMdvVsF9BUc7Btup6Ip1OcNEcs3A"
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.237.1433674295.13271.python-list@python.org>
Lines: 110
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:92227

This is an OpenPGP/MIME signed message (RFC 4880 and 3156)
--1GKjhpMdvVsF9BUc7Btup6Ip1OcNEcs3A
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable

On 07.06.2015 08:27, Cecil Westerhof wrote:
> I wrote a very simple function to test random:
>     def test_random(length, multiplier =3D 10000):
>         number_list =3D length * [0]
>         for i in range(length * multiplier):
>             number_list[random.randint(0, length - 1)] +=3D 1
>         minimum =3D min(number_list)
>         maximum =3D max(number_list)
>         return (minimum, maximum, minimum / maximum)
>=20
> When running:
>     for i in range(1, 7):
>         print(test_random(100, 10 ** i))
> I get:
>     (3, 17, 0.17647058823529413)
>     (73, 127, 0.5748031496062992)
>     (915, 1086, 0.8425414364640884)
>     (9723, 10195, 0.9537027954879843)
>     (99348, 100620, 0.9873583780560524)
>     (997198, 1002496, 0.9947151908835546)
>=20
> and when running:
>     for i in range(1, 7):
>         print(test_random(1000, 10 ** i))
> I get:
>     (2, 20, 0.1)
>     (69, 138, 0.5)
>     (908, 1098, 0.8269581056466302)
>     (9684, 10268, 0.9431242695753799)
>     (99046, 100979, 0.9808574059953059)
>     (996923, 1003598, 0.9933489305478886)
>=20
> It shows that when the first parameter increases the deviation
> increases and when the second parameter increases the deviation
> decreases. Exactly what you would expect. But what are the ranges you
> would expect with a good random function.=20

Really depends on the number of samples. Appearantly, a good RNG would
come close to 1.0 for the ratio.

> Then it could be used to test a random function.

This is an interesting test (more interesting to me than it looks at the
first sight, and certainly better than what I had come up with), but
unfortunately, there is more to testing randomness.

The test clearly suggests that random functions should have a min/max
ratio of about 1.0. Think of a "random" function like this:

    def fake_random(minv, maxv, _cache=3D{}):
        try:
            return next(_cache[minv, maxv])
        except (StopIteration, KeyError):
            iterator =3D iter(range(minv, maxv+1))
            _cache[minv, maxv] =3D iterator
            return next(iterator)

(if that is hard to read, I agree; it returns the sequence from minv to
maxv (inclusively) over and over again for equal minv and maxv. don=E2=80=
=99t
pass anything to _cache :), just call it like random.randint)

This gives a "perfect" ratio of 1.0, but is not very random. This kind
of function would probably be ruled out by a compression or correlation
test. If you want to dig deeper into the algorithms for random testing,
the dieharder test suite [1] is probably worth a look.

It all boils down to the use case. For some use cases, the
``fake_random`` might be good enough (unittesting would be such a case:
it is certainly uniformly distributed and allows full coverage of the
tested range), for others it would fail catastrophically (don=E2=80=99t g=
enerate
your cryptographic keys with this!).

cheers,
Jonas

   [1]: http://www.phy.duke.edu/~rgb/General/dieharder.php



--1GKjhpMdvVsF9BUc7Btup6Ip1OcNEcs3A
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iQIcBAEBCgAGBQJVdB/8AAoJEMBiAyWXYliKovEP/jxV9xgduieASiL2TyvNzi8T
JWjjJRUSHezAhA23NPCvNdN9SP4G6VJGsuzBm2ACNSfHKBQoImSqSEaEt0Dpe/kN
uaFvMliREYqu1WbQTFFQoRMuxlt7jri1/E0IOSU89YmhGMWrJu7w72IgDgMVi/1w
s14a5yipvs2ONXC9PECI65G3L+22+HeBRnRcrEJx16pPRzh9dyuY87aq2sLi5TkD
Qk/0Nf1CKMLgI+oZqgpI5KqnDUBb4RGfHA7OGWAjoRHDCGt/WIarTe6GoVWucCW5
B4wN0bp4pm9eqHz5LpwA15StjXHKj6yF2IbEwlhg+Oi0Z8OkZOqOKGTs3CtItIAr
LewNvHL9ZqVUkzIJ6bUTOue5TvqN0egfjF8CfPYuaQqFK+/uCdYgde0MvA5d8bbJ
x/Ca7Hzj0kpcXKpnpdYqIJZaaikmRDu43YEJuUit6eUngVqFh2peAqF1GLVGYDnO
d+qQAbhCH01C6nVg9qoigYnJz6Mw3nAS/cZFgSzQfpWNZBEYVhC4Zs+1fUxaR+YO
klzpZTuTKPEtyHYVIoMJEUxd9hL4tjib0z8tSlFcsYIvdmv/zXr+24dmaLIkv52O
qGvhgwVTgXaDLoeth7B0LKzQ0oTOuV4lQPXXwl4iuWY9/XTaSwFLi4UQJ2t75FrQ
Puj2vCRZ4pjHWhEuCURE
=pqd2
-----END PGP SIGNATURE-----

--1GKjhpMdvVsF9BUc7Btup6Ip1OcNEcs3A--