By Ian Frederick Vigogne Goodbody Hunter

The Central Limit Theorem (Moivre, 1738) describes how a normal distribution can be used to approximate the sum of identical distributions.

This approximation can be used in optimizations for dice notation parsers to calculate the result of rolling a large number of dice.

A parser given a dice notation "1000000d6" will roll a six-sided dice 1000000 times. Instead a calculation can be done to select a value with a constant time independent of the number of dice.

  • calculate a random value in a normal distribution with mean 0 and std 1 (This can be done via an algorithm such as the Box-Muller Transform (Box, Muller, 1958)
  • scale the value by the size of the approximated range
  • increment the value by the minimum dice roll value (1 * 1000000)

This optimization was implemented on the GNOLL dice notation parser (Hunter, 2022) and eliminated the adverse scaling of the parser when using large values in dice notation statements.

A performance graph is attached.

Attachment: Performance_Delta.png (28.5 KB)


Please log in to add a comment.

Ian Frederick Vigogne Goodbody Hunter



Published: 29 Nov, 2022

Cc by