changeset 26267:25d3e8e49d5c

randi.m: Implement rejection algorithm for unbiased results (bug #54619). * NEWS: Announce change to randi algorithm. * randi.m: Add input validation to expand 0, or 1, input arguments in to two dimensions. Implement rejection algorithm for random integers.
author Michael Leitner
date Tue, 18 Dec 2018 22:04:23 -0800
parents 50a161ee72e1
children 01f1e70c80b6
files NEWS scripts/general/randi.m
diffstat 2 files changed, 36 insertions(+), 8 deletions(-) [+]
line wrap: on
line diff
--- a/NEWS	Tue Dec 18 16:43:05 2018 -0800
+++ b/NEWS	Tue Dec 18 22:04:23 2018 -0800
@@ -8,6 +8,13 @@
     aforementioned functions by properly overloading the "size"
     function.
 
+ ** The function randi has been recoded to produce an unbiased (all
+    results are equally likely) sample of integers.  This may produce
+    different results in existing code.  If it is necessary to reproduce
+    the exact random integer sequence as in previous versions use
+    
+      ri = imin + floor ((imax - imin + 1) * rand ());
+
  ** A new core function movfun will apply a function to a sliding
     window of arbitrary size on a dataset and accumulate the results.
     Many common cases have been implemented using the naming
--- a/scripts/general/randi.m	Tue Dec 18 16:43:05 2018 -0800
+++ b/scripts/general/randi.m	Tue Dec 18 22:04:23 2018 -0800
@@ -79,13 +79,6 @@
     endif
   endif
 
-  if (nargin > 1 && ischar (varargin{end}))
-    rclass = varargin{end};
-    varargin(end) = [];
-  else
-    rclass = "double";
-  endif
-
   ## Limit set by use of class double in rand(): Any consecutive integer in the
   ## range [-flintmax(), flintmax()] can be represented by a double.
   if ((abs (imax) >= flintmax ()) || (abs (imin) >= flintmax ()))
@@ -95,7 +88,35 @@
     error ("randi: integer range must be smaller than flintmax()-1");
   endif
 
-  ri = imin + floor ((imax - imin + 1) * rand (varargin{:}));
+  if (nargin > 1 && ischar (varargin{end}))
+    rclass = varargin{end};
+    varargin(end) = [];
+    nargin = nargin - 1;
+  else
+    rclass = "double";
+  endif
+
+  ## Expand dimension argument to at least 2-D for reshape
+  if (nargin == 1)
+    varargin = {1, 1};
+  elseif (nargin == 2 && isscalar (varargin{1}))
+    varargin(2) = varargin(1);
+  endif
+    
+  ## Rejection Algorithm to guarantee unbiased results.  See bug #54619.
+  rng = (imax - imin) + 1;              # requested range
+  N = prod ([varargin{:}]);             # number of requested elements
+  K = floor ((flintmax () + 1) / rng);  # number of primary integers ...
+                                        # mapped to single output
+  p = (K*rng) / (flintmax () + 1);      # expected proportion of used primaries
+  
+  do  
+    M = ceil (N/p + 10*sqrt (N/p - N)); # number of requested primary integers
+    r_prim = floor (rand (M,1) * (flintmax () + 1));
+    r_prim = r_prim(r_prim < K*rng);
+  until (numel (r_prim) >= N)           # should practically always be true
+  
+  ri = imin + floor (reshape (r_prim(1:N), varargin{:}) / K);
 
   if (! strcmp (rclass, "double"))
     if (strfind (rclass, "int"))