Application of the Central Limit Theorem to dice notation parsing

By Ian Frederick Vigogne Goodbody Hunter

dice notation dice algorithms games

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)

Comments

Please log in to add a comment.