random number issue

Bug #309467 reported by Nikodemus Siivola
2
Affects Status Importance Assigned to Milestone
SBCL
Fix Released
Low
Unassigned

Bug Description

  RANDOM-INTEGER-EXTRA-BITS=10 may not be large enough for the RANDOM
  RNG to be high quality near RANDOM-FIXNUM-MAX; it looks as though
  the mean of the distribution can be systematically O(0.1%) wrong.
  Just increasing R-I-E-B is probably not a good solution, since
  it would decrease efficiency more than is probably necessary. Perhaps
  using some sort of accept/reject method would be better.

Tags: random
Revision history for this message
Nikodemus Siivola (nikodemus) wrote :

Seems to still hold.

Changed in sbcl:
importance: Undecided → Low
status: New → Confirmed
Lutz Euler (lutz-euler)
Changed in sbcl:
status: Confirmed → In Progress
assignee: nobody → Lutz Euler (lutz-euler)
Revision history for this message
Lutz Euler (lutz-euler) wrote :

As promised on sbcl-devel, here is the first version of a patch for review.
I have some questions about it on my own which I will post to sbcl-devel.

Revision history for this message
Lutz Euler (lutz-euler) wrote :

I have just committed a reworked version of the patch from #2.
Differences:
- renamed "random-bignum.lisp" to "bignum-random.lisp"
- renamed RANDOM-CHUNK-LENGTH to N-RANDOM-CHUNK-BITS
- rewrote various comments to explain things better;
  use "accept-reject" instead of "accept/reject" throughout
- corrected a factual error in the commit message and a comment:
  %random-fixnum uses only one random chunk when sufficient
- added a NEWS entry
- added credits to the commit message

Changed in sbcl:
status: In Progress → Fix Committed
assignee: Lutz Euler (lutz-euler) → nobody
Stas Boukarev (stassats)
Changed in sbcl:
status: Fix Committed → Fix Released
To post a comment you must log in.
This report contains Public information  
Everyone can see this information.

Other bug subscribers

Remote bug watches

Bug watches keep track of this bug in other bug trackers.