prorata.gno
5.48 Kb · 173 lines
1// Package prorata splits an integer amount across weighted claimants without
2// leaking or inventing a unit.
3//
4// Every payout in a game is this operation: a pot, a roster, and a weight each.
5// Written the obvious way, `amount*weight/total` per claimant, it is wrong in
6// two ways that only show up with real money in the contract. The shares are
7// each rounded down, so their sum is short of the amount by up to one unit per
8// claimant, and that dust either accumulates in the contract forever or gets
9// handed to whoever the code happens to pay last. And `amount*weight` overflows
10// an int64 long before either factor does, which turns a large payout negative.
11//
12// Split fixes both. It distributes by largest remainder: floor every share,
13// then hand the leftover units out one at a time to the claimants whose
14// truncated fraction was largest, ties going to the lower index. The result
15// sums to EXACTLY the amount, every time, and the rule is deterministic, so
16// every node computes the same split and a Render of it does not change between
17// calls.
18//
19// Nothing here reads the chain and nothing holds coins: the caller owns the
20// roster and the custody. A game built on this package is at
21// [r/moul/x/games/lastwords](/r/nym-moultest123/x/games/lastwords/v0).
22package prorata
23
24import (
25 "errors"
26 "sort"
27)
28
29const maxInt64 = int64(9223372036854775807)
30
31var (
32 // ErrNegativeAmount is returned when the amount to split is negative.
33 ErrNegativeAmount = errors.New("prorata: amount must not be negative")
34 // ErrNegativeWeight is returned when any weight is negative.
35 ErrNegativeWeight = errors.New("prorata: weights must not be negative")
36 // ErrNoWeight is returned when there is nobody to pay, or every weight is
37 // zero. The caller must decide where the amount goes instead: silently
38 // returning an empty split would strand it.
39 ErrNoWeight = errors.New("prorata: total weight is zero, nothing to split across")
40 // ErrOverflow is returned when the arithmetic does not fit in an int64.
41 ErrOverflow = errors.New("prorata: weights overflow int64")
42)
43
44// Split divides amount across weights and returns one share per weight, in the
45// same order. The shares sum to exactly amount.
46//
47// A zero weight is allowed and receives nothing, including no remainder unit:
48// somebody with no claim is not paid dust.
49func Split(amount int64, weights []int64) ([]int64, error) {
50 if amount < 0 {
51 return nil, ErrNegativeAmount
52 }
53 total, err := Total(weights)
54 if err != nil {
55 return nil, err
56 }
57 if total == 0 {
58 return nil, ErrNoWeight
59 }
60
61 shares := make([]int64, len(weights))
62 if amount == 0 {
63 return shares, nil
64 }
65
66 // Floor each share, and keep the truncated numerator to rank by.
67 rems := make([]entry, 0, len(weights))
68 assigned := int64(0)
69 for i, w := range weights {
70 if w == 0 {
71 continue
72 }
73 share, rem, err := divide(amount, w, total)
74 if err != nil {
75 return nil, err
76 }
77 shares[i] = share
78 assigned += share
79 rems = append(rems, entry{index: i, rem: rem})
80 }
81
82 // Hand the leftover out by largest remainder. There are strictly fewer
83 // leftover units than claimants, so one pass over the ranking is enough.
84 left := amount - assigned
85 if left <= 0 {
86 return shares, nil
87 }
88 sort.Sort(byRemainder(rems))
89 for i := 0; i < len(rems) && left > 0; i++ {
90 shares[rems[i].index]++
91 left--
92 }
93 return shares, nil
94}
95
96// Share returns what one weight is owed out of amount, rounded down. It is the
97// "what would I get" query, and deliberately does NOT account for the
98// remainder: use Split when the shares have to add up.
99func Share(amount, weight, total int64) (int64, error) {
100 if amount < 0 {
101 return 0, ErrNegativeAmount
102 }
103 if weight < 0 || total < 0 {
104 return 0, ErrNegativeWeight
105 }
106 if total == 0 {
107 return 0, ErrNoWeight
108 }
109 if weight > total {
110 weight = total
111 }
112 share, _, err := divide(amount, weight, total)
113 return share, err
114}
115
116// Total sums weights, refusing an int64 overflow rather than wrapping into a
117// negative total that would make every share nonsense.
118func Total(weights []int64) (int64, error) {
119 sum := int64(0)
120 for _, w := range weights {
121 if w < 0 {
122 return 0, ErrNegativeWeight
123 }
124 if w > maxInt64-sum {
125 return 0, ErrOverflow
126 }
127 sum += w
128 }
129 return sum, nil
130}
131
132// divide returns amount*weight/total rounded down, plus the remainder of that
133// division, without ever computing amount*weight.
134//
135// It splits the amount into whole multiples of total and what is left over:
136// amount = q*total + r, so amount*weight/total is exactly q*weight +
137// r*weight/total. The first term is exact and the second multiplies a value
138// already smaller than total, which is what keeps the product in range.
139func divide(amount, weight, total int64) (share, rem int64, err error) {
140 q := amount / total
141 r := amount % total
142 if weight != 0 && q > maxInt64/weight {
143 return 0, 0, ErrOverflow
144 }
145 whole := q * weight
146 if weight != 0 && r > maxInt64/weight {
147 return 0, 0, ErrOverflow
148 }
149 part := r * weight
150 if whole > maxInt64-part/total {
151 return 0, 0, ErrOverflow
152 }
153 return whole + part/total, part % total, nil
154}
155
156// entry is one claimant's truncated fraction, for ranking the leftover.
157type entry struct {
158 index int
159 rem int64
160}
161
162// byRemainder ranks by largest truncated remainder, ties by lowest index, so
163// the split is identical on every node.
164type byRemainder []entry
165
166func (b byRemainder) Len() int { return len(b) }
167func (b byRemainder) Swap(i, j int) { b[i], b[j] = b[j], b[i] }
168func (b byRemainder) Less(i, j int) bool {
169 if b[i].rem != b[j].rem {
170 return b[i].rem > b[j].rem
171 }
172 return b[i].index < b[j].index
173}
