Skip to content

GitLab

  • Projects
  • Groups
  • Snippets
  • Help
    • Loading...
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
  • Sign in / Register
GHC
GHC
  • Project overview
    • Project overview
    • Details
    • Activity
    • Releases
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
    • Locked Files
  • Issues 4,323
    • Issues 4,323
    • List
    • Boards
    • Labels
    • Service Desk
    • Milestones
    • Iterations
  • Merge Requests 367
    • Merge Requests 367
  • Requirements
    • Requirements
    • List
  • CI / CD
    • CI / CD
    • Pipelines
    • Jobs
    • Schedules
  • Security & Compliance
    • Security & Compliance
    • Dependency List
    • License Compliance
  • Operations
    • Operations
    • Incidents
    • Environments
  • Analytics
    • Analytics
    • CI / CD
    • Code Review
    • Insights
    • Issue
    • Repository
    • Value Stream
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Members
    • Members
  • Collapse sidebar
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
  • Glasgow Haskell Compiler
  • GHCGHC
  • Issues
  • #8898

Closed
Open
Opened Mar 14, 2014 by novadenizen@trac-novadenizen

Overall improvement for randomIvalInteger

The current randomIvalInteger implementation uses repeated div operations to approximate the size of the desired random output, then generates that number of random values from the given RandomGen. It does not compensate for the ``mod base uniformity problem. It also assumes that all `RandomGen` implementations produce the same range of random values as `StdGen`.

My new implementation addresses all these correctness issues, with potentially a slight performance improvement.

Instead of performing repeated div base operations to determine the size of the desired range, this uses faster (* base) operations. An equivalent set of intermediate Integers is generated still.

To compensate for the ``mod base uniformity problem, the desired range size is multiplied by the q factor (1000 in my code). When k is the desired range and b^n^ is the range of numbers generated, and d = b^n^ div k, some elements will have probability d/b^n^ and others will have probability (d+1)/b^n^, resulting in significant non-uniformity when d is very small. When you extend the generated range beyond the minimum by a factor of q, you are guaranteed that d will be at least q, so the non-uniformity will be much less consequential.

This implementation also works with any RandomGen, even ones that produce as little as a single bit of entropy per next call or have a minimum bound other than zero.

Edited Mar 09, 2019 by Herbert Valerio Riedel
Assignee
Assign to
None
Milestone
None
Assign milestone
Time tracking
None
Due date
None
Reference: ghc/ghc#8898