random number issue

Bug #309467 reported by Nikodemus Siivola on 2008-12-18
Affects Status Importance Assigned to Milestone

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.

Nikodemus Siivola (nikodemus) wrote :

Seems to still hold.

Changed in sbcl:
importance: Undecided → Low
status: New → Confirmed
Lutz Euler (lutz-euler) on 2012-03-28
Changed in sbcl:
status: Confirmed → In Progress
assignee: nobody → Lutz Euler (lutz-euler)
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.

Lutz Euler (lutz-euler) wrote :

I have just committed a reworked version of the patch from #2.
- renamed "random-bignum.lisp" to "bignum-random.lisp"
- 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) on 2012-05-21
Changed in sbcl:
status: Fix Committed → Fix Released
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers