prorata.gno

  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/moul/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}