Proper scaling of randoms

[Dylan Thurston]

--EeQfGwPcQSOJBaQU
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

(Redirected to haskell-cafe.)

On Mon, May 06, 2002 at 04:49:55PM -0700, oleg@pobox.com wrote:
> Problem: given an integer n within [0..maxn], design a scaling
> function sc(n) that returns an integer within [s..t], t>=3Ds.
> The function sc(n) must be 'monotonic':=20
> 	0<=3Da < b =3D=3D> sc(a) <=3D sc(b)
> and it must map the ends of the interval:
> 	sc(0) -> s and sc(maxn) -> t.

Just an aside (which Oleg surely knows): for actual random number
generation, you often don't care about the monotonicity, and only care
about uniform generation.  In this case, there is a very simple
algorithm: work modulo (s-t+1).

  scm(n) =3D (n `rem` (s-t+1)) + s

Warning: some, broken, random number generators do not behave well
when used like this.  Also, although this is as uniform as possible,
there is a systematic skew towards the lower end of the range [s..t].

--Dylan Thurston

--EeQfGwPcQSOJBaQU
Content-Type: application/pgp-signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE81/HLVeybfhaa3tcRAvGyAJsFm9q2w6kyDwNXKMMdjHWR9IjGYACdG0hp
1wpgseOGTNIdWlmTNfOf1to=
=QDMs
-----END PGP SIGNATURE-----

--EeQfGwPcQSOJBaQU--