onflow/flow-core-contracts

Improve Fisher-Yates random distribution

Closed this issue · 1 comments

Problem

Fisher-yates randomness relies on the sampling of a random number modulo a moduli. Distribution of the output permutation depends on the distribution of the integer sampling.
Cadence v1 offers a uniformly distributed random function revertibleRandom(modulo) that should be used instead of the modulo operator % to avoid the known modulo bias.

Current implementation is

var randomIndex = randomNum % UInt64(i + 1)

Closed by #428