Feature request: @std/random

[lowlighter]

Is your feature request related to a problem? Please describe.

I'd like to request a @std/random package that export PRNG with various distributions (uniform, normal, exponential, lognormal, triangular, etc.)

Use cases for this are various, but it allows doing stuff based on probabilities and in my case I confess it's more game-oriented rather than mathematical, but it can be used for procedural generation, such as terrains, drop rates, dice simulation, etc.

Note that it cannot be achieved entirely by Math.random() (which is supposed to be a uniform distribution I think) even though deno provide a --seed flag simply because as far as I know, JS does not offer the ability to create new seedable PRNG (and I don't recall seeing a proposal for it, though I may be mistaken) hence the need of separate functions else you'd be limited to a single instance

Describe the solution you'd like

I've seen that #2774 was proposed two years ago, and from I understanding it was mostly rejected because of the unclear scope, but a @std/random would be pretty limited like its name implies so I guess it'll be less problematic.

Python has the random library natively for example: https://docs.python.org/3/library/random.html

I actually ported their implementation in js a few years ago from here (https://lecoq.io/random/demo), so I guess to integrate it in @std we could just port the python3 version instead as it's open as long as the licensing requirements are respected

I'm not sure it's worth implementing all distributions (I mean unless someone wants for the sake of completeness) but at least the uniform, normal, lognormal, gamma and triangular would be nice (actually once you have the uniform one, you can make all the other ones if I recall correctly).

I think for a TS port, using function* generators works really well so a simple API that exports distribution generators would be appropriate I think

Just for information, a PRNG looks like this (it's not that complicated if you ignore the math behind):

// Wichman-Hill random number generator
function *random(seed = Date.now()) {
     let a = 30269, b = 30307, c = 30323
     let x = seed%(a-1)+1, y = seed%(b-1)+1, z = seed%(c-1)+1
     while (1) {
         x = (x*171)%a, y = (y*172)%b, z = (z*170)%c
         yield (x/a + y/b + z/c) % 1
     }
 }

The only downside of generator is that they return an object where most users would just expect a number, so maybe another paradigm could be a better fit (or maybe just a wrapper around generators for convenience). Especially it'd be nice to still be able to access the original seed/params and maybe the iterationNumber so a PRNG can be "reloaded" from a previous saved state easily (e.g. like if you store it in a Deno.Kv and reuse them later).

Also in term of usability, it'd could offer helper like range/integer generators (rather than 0..1) instead of delegating this task to users for more convenience.

But as everything mathematical, once it's formulated they're aren't too much changes so I think it'd be a pretty low maintenance package. Additionally I'm pretty sure the python implementation is pretty mature and trustable by now.

In terms of unit testing, it's kind of "hard" because we try so simulate randomness in something that is inherently not, but I was thinking of just generating snapshots to ensure that they're deterministic and that input/return types are correct.

Describe alternatives you've considered

I think there are probably existing user-land package, but having a standard one would be nice to be par on other ecosystem such as python.

I could also just port the implementation in my code, but it'd still be less practical as it could fit for a @std package

If this feels reasonable and if a suitable API can be agreed on, I volunteer to port the five distributions I mentioned earlier (uniform, normal, lognormal, gamma and triangular) in an initial pull request. If not, it's okay, I'll just use make a package in userland and call it a day

Edit: added a few more points

[0f-0b]

There is an old proposal for seeded PRNG from 2018, and a very new proposal for common utility functions. Missing from the proposals are specialized random distributions. For these an API like this (modeled after part of C++'s <random> library) would be easy to use, easy to implement, and integrate well with the seeded PRNG proposal and other user-provided RNGs.

// distribution
export type Distribution = (randomSource: () => number) => number;

// exponential-distribution
export interface ExponentialDistributionParams {
  rate?: number;
}

export function exponentialDistribution(
  params?: ExponentialDistributionParams,
): Distribution;

// normal-distribution
export interface NormalDistributionParams {
  mean?: number;
  stddev?: number;
}

export function normalDistribution(
  params?: NormalDistributionParams,
): Distribution;

// …

Example usage

Say a user wants to simulate random events that on average occur every second.

import { delay } from "jsr:@std/async/delay";
import { SECOND } from "jsr:@std/datetime/constants";
import { exponentialDistribution } from "jsr:@std/random/exponential-distribution";

const dist = exponentialDistribution({ rate: 1 / SECOND });
for (;;) {
  await delay(dist(Math.random));
  console.log("event!");
}

What the implementation may look like

// exponential_distribution.ts
const { log } = Math;

export function exponentialDistribution(
  params?: ExponentialDistributionParams,
): Distribution {
  const invRate = -1 / (params?.rate ?? 1);
  return (s) => invRate * log(1 - s());
}

[lowlighter]

@0f-0b
Wow, seems these proposals didn't get much traction 😅
But it's nice seeing that they've been updated recently.

I think it's a safe choice to provide them until they're eventually are built-ins then, as they're only in stage 0/1.
The second proposal contains some really useful functions too that I think it'd be nice to polyfill in the meantime, mainly shuffle( array ) and pickFromList( array ). I think a pickFromObject( Record<string, number> ) could be nice to provide a weighted pick from a given record.

Anyway I think the API you provided are is pretty straightforward so I'm ok with it.
I like the fact that it make combination of different distributions easy and it's also compatible with the current Math.random out of the box.

So for the base PRNG, would it be a good idea to stay close to what is suggested in the first proposal ?

export function seededPRNG(
  {seed:number}
): {
  random:() => number
  randomSeed:() => number
  readonly seed: number
}

[lionel-rowe]

A utility for converting arbitrary strings into suitable prng seeds would also be useful.

shuffle would be useful to include as it's easy to implement wrong or with suboptimal efficiency. pickFromList, randBetween, randInt etc (subject to bikeshedding about names) are maybe too simple to be strictly necessary but might still be worthwhile...? I'm not sure exactly how pickFromObject would work, but picking with weights can definitely be useful:

function pickWeighted<T extends { weight: number }>(items: readonly T[], random = Math.random): T {
    const max = Object.values(items).reduce((sum, { weight }) => sum + weight, 0)

    const rand = random() * max
    let total = 0

    for (const item of items) {
        total += item.weight

        if (rand < total) {
            return item
        }
    }

    return items[0]
}