CVS difference for ai12s/ai12-0144-1.txt

Differences between 1.2 and version 1.3
Log of other versions for file ai12s/ai12-0144-1.txt

--- ai12s/ai12-0144-1.txt	2015/02/27 01:20:19	1.2
+++ ai12s/ai12-0144-1.txt	2015/11/20 02:00:06	1.3
@@ -1,6 +1,8 @@
-!standard A.5.2(20)                          15-02-26   AI12-0144-1/02
+!standard A.5.2(20)                          15-11-19   AI12-0144-1/03
 !standard A.5.2(32)
+!standard A.5.2(41)
 !class Amendment 14-12-04
+!status ARG Approved 7-0-0  15-10-18
 !status Promising (10-0-0) 15-02-26
 !status work item 14-12-04
 !status received 14-11-06
@@ -67,6 +69,13 @@
 Constraint_Error is the existing exception for that (A.5.2.(39)), so we
 used that here.]
 
+Modify A.5.2(41):
+
+A sufficiently long sequence of random numbers obtained by successive calls to
+Random is approximately uniformly distributed over the range of the result
+subtype{, or in the case of the version of Random with First and Last
+parameters, over the range First .. Last.}.
+
 !discussion
 
 The author ran into this problem with a hobby solitaire program. It was
@@ -78,6 +87,25 @@
 select with ranges 1..52, then 1..51, then 1..50, etc.
 
 That's not possible with the Ada 95 definition of Discrete_Random.
+
+
+Users often accomplish this in ways that do not provide a truly uniform
+distribution. It's easy to come up with methods that don't work (see the
+!appendix for several such algorithms), but it's difficult to get right.
+
+One algorithm that is correct is to start with a uniform random generator
+that produces an integer in the range 0 .. Large. (Usually Large is some
+power of 2 - 1). Then, for a call to Random with bounds First and Last, we
+determine Len := (Last-First+1) and then Mult, which is the largest multiple
+of Len that is less than Large. (Len cannot be greater than Large.) We then
+loop, getting a random value, and exiting the loop when the random value is
+less than Mult. Finally, we mod the random value (now in the range 0 ..
+Mult-1) by Len and add First.
+
+This loop will usually exit on the first iteration, and even in the worst
+case (Len = Large/2+1), there is at least a 50% chance that the loop will
+exit on each iteration. So it is unlikely that many iterations will be needed.
+
 
 If this was 1994, we should have simply defined Random in Discrete_Random as
 follows:

Questions? Ask the ACAA Technical Agent