[erlang-questions] RNG algorithm choice for uniform natural numbers
Krzysztof Jurewicz
krzysztof.jurewicz@REDACTED
Thu Aug 9 15:27:51 CEST 2018
> What I actually want to implement is a randomized apportionment scheme, as described on https://rangevoting.org/Apportion.html (“Truly unbiased methods”), but more efficient, like in the code below (not tested).
Tests revealed that the simple algorithm does not satisfy the quota property. Therefore I’ve used a more sophisticated one (code below), which however doesn’t require using a specific interval for drawing integers. Instead of the rand module, I use SHA-256 to generate random integers (taking first n bits). This is very interoperable between languages, though I don’t know whether SHA-256 satisfies all RNG properties desirable in that context. (Also I don’t have a proof that the distribution of apportioned seats is unbiased).
-type score() :: ({Votes :: non_neg_integer(), Id :: any()}).
-type result() :: {Id :: any(), Seats :: non_neg_integer()}.
-spec apportion(list(score()), pos_integer(), pos_integer(), binary()) -> list(result()).
apportion(Scores, TotalSeats, VotesSum, State) ->
{WholeSeatsMap, RemainderScores, RemainingSeats, _} =
lists:foldl(
fun (
{Votes, Id},
{WholeSeatsAcc,
RemainderScoresAcc,
RemSeatsAcc,
StateAcc}) ->
Seats = Votes * TotalSeats div VotesSum,
<<RandInt:32, _/binary>> = NewState = crypto:hash(sha256, StateAcc),
RemainderScore = (Votes * TotalSeats rem VotesSum) * (RandInt + 1),
{maps:put(Id, Seats, WholeSeatsAcc),
[{RemainderScore, Id}|RemainderScoresAcc],
RemSeatsAcc - Seats,
NewState}
end,
{#{},
[],
TotalSeats,
State},
Scores),
DrawnIds =
%% We actually need to sort the list only at first RemainderSeats places, so here is a room for optimization.
[Id || {_, Id} <- lists:sublist(lists:reverse(lists:sort(RemainderScores)), RemainingSeats)],
ResultMap =
lists:foldl(
fun (Id, ResultMapAcc) ->
maps:update_with(
Id,
fun (OldSeats) -> OldSeats + 1 end,
1,
ResultMapAcc)
end,
WholeSeatsMap,
DrawnIds),
lists:sort([{Id, Seats} || {Id, Seats} <- maps:to_list(ResultMap), Seats > 0]).
More information about the erlang-questions
mailing list