--- 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