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

[Rik]

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

I did some work on this problem over the weekend just to hack something up. 
First, I'm attaching the academic paper that Michael Godfrey pointed to
(Fast_Random_Integer_Generation_in_an_Interval.pdf).  This outlines two
methods used by existing libraries: 1) rejection (OpenBSD, GNU libc, others),
2) Java.  Of these, rejection is used by many and it has guaranteed worst case
behavior.  The Java library has better average performance, but unbounded
worst case behavior, which I'm not interested in adopting.  Finally, the
author proposes a third method of his own devising which I will call "new"
method.  The paper is from May, 2018 so this is very "new" compared to the
existing methods.

I appreciate Michael Leitner's m-file approach, but it does contain a do-until
loop.  Because Octave is interpreted, and we don't have a JIT implementation
for loops, any looping behavior involves a big performance hit.  In situations
where looping can't be avoided the suggestion is to move to C++ which is what
I have done.

Second attachment is a small change to expose the function randi53 (53-bit
random integer) from liboctave/numeric/randmtzig.cc.  See randi53.diff. 
Because of some vagaries of the build system to use this you will need to
patch the Octave source tree and then install Octave so that 'mkoctfile' has
the new header file randmtzig.h.  Instructions


cd octave_src_dir
patch -p1 < randi53.diff
make
make install


After that you can work with the two octfile samples I made: randi_rej.cpp and
randi_new.cpp.  These are not complete--there is no input validation,
documentation, support for specifying number of values, BIST tests, etc.--but
they do allow you to set imin and imax and they return a column vector [1e6,1]
of values.

To compile them use


mkoctfile -v -O2 randi_rej.cpp
mkoctfile -v -O2 randi_new.cpp


More to follow, but I can only attach 4 files at a time so I have to continue
in a new comment.



(file #44964, file #44965, file #44966, file #44967)
    _______________________________________________________

Additional Item Attachment:

File name: Fast_Random_Integer_Generation_in_an_Interval.pdf Size:949 KB
File name: randi_rej.cpp                  Size:0 KB
File name: randi53.diff                   Size:1 KB
File name: randi_new.cpp                  Size:1 KB


    _______________________________________________________

Reply to this item at:

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

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