NAME
   Math::Round::Fair - distribute rounding errors fairly

SYNOPSIS
     use Math::Round::Fair 'round_fair', 'round_adjacent';

     my $cents = 7;
     my @weights = (1, 2, 3, 2, 1);
     my @allocation = round_fair($cents, @weights);

     print "@allocation\n";

     # output will be one of the following:
     # 0 1 3 2 1
     # 0 2 2 2 1
     # 0 2 3 1 1
     # 0 2 3 2 0
     # 1 1 2 2 1
     # 1 1 3 1 1
     # 1 1 3 2 0
     # 1 2 2 1 1
     # 1 2 2 2 0

     my @total;
     for ( 1..900 ) {
         @allocation = round_fair($cents, @weights);
         @total[$_] += @allocation[$_] for 0..$#allocation;
     }
     print "@total\n";

     # output will be *near* 700 1400 2100 1400 700, e.g.:
     # 698 1411 2096 1418 677


     my @rounded = round_adjacent(0.95, 0.65, 0.41, 0.99);
     # @rounded will be one of the following:
     # 59% of the time: 1, 1, 0, 1
     # 35% of the time: 1, 0, 1, 1
     #  5% of the time: 0, 1, 1, 1
     #  1% of the time: 1, 1, 1, 0

DESCRIPTION
   This module provides two exportable functions, "round_fair", which
   allocates an integer value, fairly distributing rounding errors, and
   "round_adjacent", which takes a list of real numbers and rounds them up,
   or down, to an adjacent integer, fairly. Both functions return a list of
   fairly rounded integer values.

   "round_fair" and "round_adjacent" round up, or down, randomly, where the
   probability of rounding up is equal to the fraction to round. For
   example, 0.5 will round to 1.0 with a probability of 0.5. 0.3 will round
   to 1.0 3 out of 10 times and to zero 7 out of 10 times, on average.

   Consider the problem of distributing one indivisible item, for example a
   penny, across three evenly weighted accounts, A, B, and C.

   Using a naive approach, none of the accounts will receive an allocation
   since the allocated portion to each is 1/3 and 1/3 rounds to zero. We
   are left with 1 unallocated item.

   Another approach is to adjust the basis at each step. We start with 1
   item to allocate to 3 accounts. 1/3 rounds to 0, so account A receives
   no allocation, and we drop it from consideration. Now, we have 2
   accounts and one item to allocate. 1/2 rounds to 1, so we allocate 1
   item to account B. Account C gets no allocation since there is nothing
   left to allocate.

   But what happens if we allocate one item to the same three accounts
   10,000 times? Ideally, two accounts should end up with 3,333 items and
   one should end up with 3,334 items.

   Using the naive approach, all three accounts receive no allocation since
   at each round the allocation is 1/3 which rounds to zero. Using the
   second method, account A and account C will receive no allocation, and
   account B will receive a total allocation of 10,000 items. Account B
   always receives the benefit of the rounding errors using the second
   method.

   The algorithm employed by this module uses randomness to ensure a fair
   distribution of rounding errors. In our example problem, we start with 1
   item to allocate. We calculate account A's share, 1/3. Since it is less
   than one item, we give it a 1/3 chance of rounding up (and, therefore, a
   2/3 chance of rounding down). It wins the allocation 1/3 of the time.
   2/3 of the time we continue to B. We calculate B's allocation as 1/2
   (since there are only 2 accounts remaining and one item to allocate). B
   rounds up 1/2 of 2/3 (or 1/3) of the time and down 1/2 of 2/3 (or 1/3)
   of the time. If neither A nor B rounds up (which occurs 2/3 * 1/2, or
   1/3 of the time), C's allocation is calculated as 1/1 since we have one
   item to allocate and only one account to allocate it to. So, 1/3 of the
   time C receives the benefit of the rounding error. We never end up with
   any unallocated items.

   This algorithm works for any number of weighted allocations.

   round_fair($value, @weights)
       Returns a list of integer values that sum to $value where each
       return value is a portion of $value allocated by the respective
       weights in @weights. The number of return values is equal to the
       number of elements in @weights

       $value must be an integer.

   round_adjacent(@input_values)
       Returns a list of integer values, each of which is numerically
       adjacent to the corresponding element of @input_values, and whose
       total is numerically adjacent to the total of @input_values.

       The expected value of each output value is equal to the
       corresponding element of @input_values (within a small error margin
       due to the limited machine precision).

CAVEATS
   * A number of in-situ integrity checks are enabled by setting
     $ENV{MATH_ROUND_FAIR_DEBUG} before loading "Math::Round::Fair". These
     integrity checks increase runtime by approximately one-third. Set
     $ENV{MATH_ROUND_FAIR_DEBUG} to 1 to enable integrity checks, 2 for
     some extra debug output, 0, or unset to disable the checks. By
     default, the integrity checks are disabled.

   * The algorithm that satisfies these constraints is not necessarily
     unique, and the implementation may change over time.

   * Randomness is obtained via calls to rand(). You might want to call
     srand() first. The number of invocations to rand() per call may change
     in subsequent versions.

   * The rounding of each element in the list is *not* independent of the
     rounding of the other elements. This is the price that you pay for
     guaranteeing that the total is also fair and accurate.

AUTHORS
   Marc Mims <[email protected]>, Anders Johnson <[email protected]>

LICENSE
   Copyright (c) 2009-2010 Marc Mims

   This is free software. You may use it, distributed it, and modify it
   under the same terms as Perl itself.

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.