[erlang-questions] RNG algorithm choice for uniform natural numbers

[Krzysztof Jurewicz]

> 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]).