muldiv.gno

 1package xmath
 2
 3import "math/bits"
 4
 5// maxInt64 is the largest int64. Unexported and spelled out because xmath
 6// already exports MaxInt64 as the max-of-two helper, and a constant sharing
 7// that name would shadow it.
 8const maxInt64 = int64(9223372036854775807)
 9
10// MulDiv returns a*b/c computed through a 128-bit intermediate, so the product
11// does not have to fit in an int64. It is the proportional-share calculation:
12// "this account's cut of the pot", "this stake's slice of the rewards".
13//
14// The naive a*b/c silently wraps when a*b exceeds an int64, and it wraps to a
15// plausible-looking number rather than to an obvious one, which is how a payout
16// split leaks money without anything failing. Ten realms deployed on gnoland-1
17// carry their own copy of this function for exactly that reason, and every one
18// of them reaches for math/bits the same way.
19//
20// MulDiv panics rather than returning a wrong number:
21//
22//   - a or b negative, or c at or below zero: the domain is unsigned ratios,
23//     and a negative share is a caller bug, not a value to propagate.
24//   - the quotient not fitting in an int64.
25//
26// Rounding is toward zero, like integer division. See [MulDivUp] when the
27// remainder must favour the payer instead.
28func MulDiv(a, b, c int64) int64 {
29	if a < 0 || b < 0 {
30		panic("xmath: MulDiv on a negative operand")
31	}
32	if c <= 0 {
33		panic("xmath: MulDiv by a non-positive denominator")
34	}
35	hi, lo := bits.Mul64(uint64(a), uint64(b))
36	if hi >= uint64(c) {
37		panic("xmath: MulDiv quotient overflows int64")
38	}
39	q, _ := bits.Div64(hi, lo, uint64(c))
40	if q > uint64(maxInt64) {
41		panic("xmath: MulDiv quotient overflows int64")
42	}
43	return int64(q)
44}
45
46// MulDivUp is [MulDiv] rounding away from zero when the division is not exact.
47//
48// Which way to round is a money question, not a style one: rounding a fee down
49// and a payout up is how a pool pays out more than it holds. Use MulDiv for
50// what someone receives and MulDivUp for what someone owes.
51func MulDivUp(a, b, c int64) int64 {
52	q := MulDiv(a, b, c)
53	hi, lo := bits.Mul64(uint64(a), uint64(b))
54	_, rem := bits.Div64(hi, lo, uint64(c))
55	if rem != 0 {
56		if q == maxInt64 {
57			panic("xmath: MulDivUp quotient overflows int64")
58		}
59		q++
60	}
61	return q
62}
63