[Octave-bug-tracker] [bug #54619] randi() is biased

[Rik]

Follow-up Comment #25, bug #54619 (project octave):

@Michael: All fair comments.  I saw that the loop would be executed
infrequently, but didn't continue to calculate how infrequently that might
be.

The worst case is unbounded.  But, what I had in mind was column 3 of Table 1,
"Maximal number of remainders per integer" which is Infinity for the Java
algorithm which is why I wasn't interested in it.

Total time = time_to_create_random_integer + time_map_integer_onto_range.  

Running the openbsd algorithm in randi_rej.cpp with


for i = 1:20
tic;
x=randi_rej (6004799503160661);
bm(i)=toc;
end

octave:19> mean (bm(2:end))
ans =  0.026421


If I change the code to


  for (octave_idx_type i = 0; i < sz; i++)
    {
      data[i] = octave::randi53 ();
      //data[i] = openbsd (s) + imin;
    }


, re-compile, and re-run the 20 point benchmark I get


octave:3> mean (bm(2:end))
ans =  0.011396


So the random number generation is about 43% of the total time and the mapping
is 57% of the time.  Since it is so balanced, I think there are opportunities
for improvement in both halves.  If I run the nearlydivisionless algorithm on
a range where it works, imax=9, the results are impressive.


octave:7> mean (bm(2:end))
ans =  0.018590


But, since it didn't work for all values of imax I can't advocate for it.

    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?54619>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/