-
Notifications
You must be signed in to change notification settings - Fork 91
/
big_math.go
267 lines (236 loc) · 8.81 KB
/
big_math.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
package lib
import (
"fmt"
"math"
"math/big"
)
// BigMulPow10 returns the result of `val * 10^exponent`, in *big.Rat.
func BigMulPow10(
val *big.Int,
exponent int32,
) (
result *big.Rat,
) {
ratPow10 := RatPow10(exponent)
return ratPow10.Mul(
new(big.Rat).SetInt(val),
ratPow10,
)
}
// bigPow10Memo is a cache of the most common exponent value requests. Since bigPow10Memo will be
// accessed from different go-routines, the map should only ever be read from or collision
// could occur.
var bigPow10Memo = warmCache()
// BigPow10 returns the result of `10^exponent`. Caches all calculated values and
// re-uses cached values in any following calls to BigPow10.
func BigPow10(exponent uint64) *big.Int {
result := bigPow10Helper(exponent)
// Copy the result, such that no values can be modified by reference in the
// `bigPow10Memo` cache.
copy := new(big.Int).Set(result)
return copy
}
// RatPow10 returns the result of `10^exponent`. Re-uses the cached values by
// calling bigPow10Helper.
func RatPow10(exponent int32) *big.Rat {
result := new(big.Rat).SetInt(bigPow10Helper(uint64(AbsInt32(exponent))))
if exponent < 0 {
result.Inv(result)
}
return result
}
// BigIntMulPpm takes a `big.Int` and returns the result of `input * ppm / 1_000_000`. This method rounds towards
// negative infinity.
func BigIntMulPpm(input *big.Int, ppm uint32) *big.Int {
result := new(big.Int)
result.Mul(input, big.NewInt(int64(ppm)))
return result.Div(result, big.NewInt(int64(OneMillion)))
}
// BigIntMulSignedPpm takes a `big.Int` and returns the result of `input * ppm / 1_000_000`.
func BigIntMulSignedPpm(input *big.Int, ppm int32, roundUp bool) *big.Int {
result := new(big.Rat)
result.Mul(
new(big.Rat).SetInt(input),
new(big.Rat).SetInt64(int64(ppm)),
)
result.Quo(result, BigRatOneMillion())
return BigRatRound(result, roundUp)
}
// BigMin takes two `big.Int` as parameters and returns the smaller one.
func BigMin(a, b *big.Int) *big.Int {
result := new(big.Int)
// If `a` is greater than `b`, return `b` since it is smaller.
// Else, return `a` since it is smaller than or equal to `b`.
if a.Cmp(b) > 0 {
result.Set(b)
} else {
result.Set(a)
}
return result
}
// BigMax takes two `big.Int` as parameters and returns the larger one.
func BigMax(a, b *big.Int) *big.Int {
result := new(big.Int)
// If `a` is greater than `b`, return `a` since it is larger.
// Else, return `b` since it is greater than or equal to `a`.
if a.Cmp(b) > 0 {
result.Set(a)
} else {
result.Set(b)
}
return result
}
// BigRatMulPpm takes a `big.Rat` and returns the result of `input * ppm / 1_000_000`.
func BigRatMulPpm(input *big.Rat, ppm uint32) *big.Rat {
return new(big.Rat).Mul(
input,
new(big.Rat).SetFrac64(
int64(ppm),
int64(OneMillion),
),
)
}
// bigGenericClamp is a helper function for BigRatClamp and BigIntClamp
// takes an input, upper bound, and lower bound. It returns the result
// bounded within the upper and lower bound, inclusive.
// Note that if there is overlap between the bounds (`lower > upper`), this
// function will do the following:
// - If `n < lower`, the lower bound is returned.
// - Else, the upper bound is returned (since `n >= lower`, then `n > upper` must be true).
func bigGenericClamp[T big.Int | big.Rat, P interface {
Cmp(P) int
Set(P) P
*T
}](n P, lowerBound P, upperBound P) P {
// If `n` is less than the lower bound, copy and return the lower bound.
result := P(new(T))
if n.Cmp(lowerBound) == -1 {
result.Set(lowerBound)
return result
}
// If `n` is greater than the upper bound, copy and return the upper bound.
if n.Cmp(upperBound) == 1 {
result.Set(upperBound)
return result
}
// `n` is between the lower and upper bound, therefore copy and return `n`.
result.Set(n)
return result
}
// See `bigGenericClamp` for specification.
func BigRatClamp(n *big.Rat, lowerBound *big.Rat, upperBound *big.Rat) *big.Rat {
return bigGenericClamp(n, lowerBound, upperBound)
}
// See `bigGenericClamp` for specification.
func BigIntClamp(n *big.Int, lowerBound *big.Int, upperBound *big.Int) *big.Int {
return bigGenericClamp(n, lowerBound, upperBound)
}
// BigRatRound takes an input and a direction to round (true for up, false for down).
// It returns the result rounded to a `*big.Int` in the specified direction.
func BigRatRound(n *big.Rat, roundUp bool) *big.Int {
numeratorBig := n.Num()
denominatorBig := n.Denom()
resultBig, remainderBig := new(big.Int).DivMod(numeratorBig, denominatorBig, new(big.Int))
// If the remainder is non-zero, then round up by adding 1.
// Note this works for negative numbers due to the following reasons:
// - In euclidean division, the remainder is always positive so the resulting division rounds
// down instead of towards zero.
// - The denominator of `big.Rat` is always positive. Therefore if `n` is negative, that means
// the numerator is negative.
if remainderBig.Sign() > 0 && roundUp {
resultBig.Add(resultBig, big.NewInt(1))
}
return resultBig
}
// BigIntRoundToMultiple takes an input, a multiple, and a direction to round (true for up,
// false for down). It returns a rounded result such that it is evenly divided by `multiple`.
// This function always expects the `multiple` parameter to be positive, otherwise it will panic.
func BigIntRoundToMultiple(
n *big.Int,
multiple *big.Int,
roundUp bool,
) *big.Int {
if multiple.Sign() <= 0 {
panic("BigIntRoundToMultiple: multiple must be positive")
}
result, remainder := new(big.Int).DivMod(n, multiple, new(big.Int))
if roundUp && remainder.Sign() > 0 {
result = result.Add(result, big.NewInt(1))
}
return result.Mul(result, multiple)
}
// BigInt32Clamp takes a `big.Int` as input, and `int32` upper and lower bounds. It returns
// `int32` bounded within the upper and lower bound, inclusive.
// Note that if there is overlap between the bounds (`lower > upper`), this
// function will do the following:
// - If `n < lower`, the lower bound is returned.
// - Else, the upper bound is returned (since `n >= lower`, then `n > upper` must be true).
func BigInt32Clamp(n *big.Int, lowerBound, upperBound int32) int32 {
// If `n` is less than the lower bound, return the lower bound.
if n.Cmp(new(big.Int).SetInt64(int64(lowerBound))) == -1 {
return lowerBound
}
// If `n` is greater than the upper bound, return the upper bound.
if n.Cmp(new(big.Int).SetInt64(int64(upperBound))) == 1 {
return upperBound
}
// `n` is between the lower and upper bound, which also means it must fit in a `int32`.
// Therefore return `n`.
return int32(n.Int64())
}
// BigUint64Clamp takes a `big.Int` as input, and `uint64` upper and lower bounds. It returns
// `uint64` bounded within the upper and lower bound, inclusive.
// Note that if there is overlap between the bounds (`lower > upper`), this
// function will do the following:
// - If `n < lower`, the lower bound is returned.
// - Else, the upper bound is returned (since `n >= lower`, then `n > upper` must be true).
func BigUint64Clamp(n *big.Int, lowerBound, upperBound uint64) uint64 {
// If `n` is less than the lower bound, return the lower bound.
if n.Cmp(new(big.Int).SetUint64(lowerBound)) == -1 {
return lowerBound
}
// If `n` is greater than the upper bound, return the upper bound.
if n.Cmp(new(big.Int).SetUint64(upperBound)) == 1 {
return upperBound
}
// `n` is between the lower and upper bound, which also means it must fit in a `uint64`.
// Therefore return `n`.
return n.Uint64()
}
// `MustConvertBigIntToInt32` converts a `big.Int` to an `int32` and panics if the input value overflows
// or underflows `int32`.
func MustConvertBigIntToInt32(n *big.Int) int32 {
// If `n` is greater than maxInt32 or less than minInt32, panic.
if n.Cmp(new(big.Int).SetInt64(math.MaxInt32)) > 0 || n.Cmp(new(big.Int).SetInt64(math.MinInt32)) < 0 {
panic("MustConvertBigIntToInt32: input value overflows or underflows int32")
}
return int32(n.Int64())
}
func bigPow10Helper(exponent uint64) *big.Int {
m, ok := bigPow10Memo[exponent]
if ok {
return m
}
// Subdivide the exponent and recursively calculate each result, then multiply
// both results together (given that `10^exponent = 10^(exponent / 2) *
// 10^(exponent - (exponent / 2))`.
e1 := exponent / 2
e2 := exponent - e1
return new(big.Int).Mul(bigPow10Helper(e1), bigPow10Helper(e2))
}
// warmCache is used to populate `bigPow10Memo` with the most common exponent requests. Since,
// none of the exponents should ever be invalid - panic immediately if an exponent is cannot be
// parsed.
func warmCache() map[uint64]*big.Int {
exponentString := "1"
bigExponentValues := make(map[uint64]*big.Int, 100)
for i := 0; i < 100; i++ {
bigValue, ok := new(big.Int).SetString(exponentString, 0)
if !ok {
panic(fmt.Sprintf("Failed to get big from string for exponent memo: %v", exponentString))
}
bigExponentValues[uint64(i)] = bigValue
exponentString = exponentString + "0"
}
return bigExponentValues
}