-
-
Notifications
You must be signed in to change notification settings - Fork 118
/
Math.sol
502 lines (459 loc) · 20.5 KB
/
Math.sol
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
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
// SPDX-License-Identifier: MIT
pragma solidity >=0.8.13;
import { msb, mulDiv, mulDiv18, prbExp2, prbSqrt } from "../Common.sol";
import { unwrap, wrap } from "./Casting.sol";
import { uHALF_UNIT, uLOG2_10, uLOG2_E, uMAX_UD60x18, uMAX_WHOLE_UD60x18, UNIT, uUNIT, ZERO } from "./Constants.sol";
import {
PRBMath_UD60x18_Ceil_Overflow,
PRBMath_UD60x18_Exp_InputTooBig,
PRBMath_UD60x18_Exp2_InputTooBig,
PRBMath_UD60x18_Gm_Overflow,
PRBMath_UD60x18_Log_InputTooSmall,
PRBMath_UD60x18_Sqrt_Overflow
} from "./Errors.sol";
import { UD60x18 } from "./ValueType.sol";
/*//////////////////////////////////////////////////////////////////////////
MATHEMATICAL FUNCTIONS
//////////////////////////////////////////////////////////////////////////*/
/// @notice Calculates the arithmetic average of x and y, rounding down.
///
/// @dev Based on the formula:
///
/// $$
/// avg(x, y) = (x & y) + ((xUint ^ yUint) / 2)
/// $$
//
/// In English, what this formula does is:
///
/// 1. AND x and y.
/// 2. Calculate half of XOR x and y.
/// 3. Add the two results together.
///
/// This technique is known as SWAR, which stands for "SIMD within a register". You can read more about it here:
/// https://devblogs.microsoft.com/oldnewthing/20220207-00/?p=106223
///
/// @param x The first operand as an UD60x18 number.
/// @param y The second operand as an UD60x18 number.
/// @return result The arithmetic average as an UD60x18 number.
function avg(UD60x18 x, UD60x18 y) pure returns (UD60x18 result) {
uint256 xUint = unwrap(x);
uint256 yUint = unwrap(y);
unchecked {
result = wrap((xUint & yUint) + ((xUint ^ yUint) >> 1));
}
}
/// @notice Yields the smallest whole UD60x18 number greater than or equal to x.
///
/// @dev This is optimized for fractional value inputs, because for every whole value there are "1e18 - 1" fractional
/// counterparts. See https://en.wikipedia.org/wiki/Floor_and_ceiling_functions.
///
/// Requirements:
/// - x must be less than or equal to `MAX_WHOLE_UD60x18`.
///
/// @param x The UD60x18 number to ceil.
/// @param result The least number greater than or equal to x, as an UD60x18 number.
function ceil(UD60x18 x) pure returns (UD60x18 result) {
uint256 xUint = unwrap(x);
if (xUint > uMAX_WHOLE_UD60x18) {
revert PRBMath_UD60x18_Ceil_Overflow(x);
}
assembly ("memory-safe") {
// Equivalent to "x % UNIT" but faster.
let remainder := mod(x, uUNIT)
// Equivalent to "UNIT - remainder" but faster.
let delta := sub(uUNIT, remainder)
// Equivalent to "x + delta * (remainder > 0 ? 1 : 0)" but faster.
result := add(x, mul(delta, gt(remainder, 0)))
}
}
/// @notice Divides two UD60x18 numbers, returning a new UD60x18 number. Rounds towards zero.
///
/// @dev Uses `mulDiv` to enable overflow-safe multiplication and division.
///
/// Requirements:
/// - The denominator cannot be zero.
///
/// @param x The numerator as an UD60x18 number.
/// @param y The denominator as an UD60x18 number.
/// @param result The quotient as an UD60x18 number.
function div(UD60x18 x, UD60x18 y) pure returns (UD60x18 result) {
result = wrap(mulDiv(unwrap(x), uUNIT, unwrap(y)));
}
/// @notice Calculates the natural exponent of x.
///
/// @dev Based on the formula:
///
/// $$
/// e^x = 2^{x * log_2{e}}
/// $$
///
/// Requirements:
/// - All from `log2`.
/// - x must be less than 133.084258667509499441.
///
/// @param x The exponent as an UD60x18 number.
/// @return result The result as an UD60x18 number.
function exp(UD60x18 x) pure returns (UD60x18 result) {
uint256 xUint = unwrap(x);
// Without this check, the value passed to `exp2` would be greater than 192.
if (xUint >= 133_084258667509499441) {
revert PRBMath_UD60x18_Exp_InputTooBig(x);
}
unchecked {
// We do the fixed-point multiplication inline rather than via the `mul` function to save gas.
uint256 doubleUnitProduct = xUint * uLOG2_E;
result = exp2(wrap(doubleUnitProduct / uUNIT));
}
}
/// @notice Calculates the binary exponent of x using the binary fraction method.
///
/// @dev See https://ethereum.stackexchange.com/q/79903/24693.
///
/// Requirements:
/// - x must be 192 or less.
/// - The result must fit within `MAX_UD60x18`.
///
/// @param x The exponent as an UD60x18 number.
/// @return result The result as an UD60x18 number.
function exp2(UD60x18 x) pure returns (UD60x18 result) {
uint256 xUint = unwrap(x);
// Numbers greater than or equal to 2^192 don't fit within the 192.64-bit format.
if (xUint >= 192e18) {
revert PRBMath_UD60x18_Exp2_InputTooBig(x);
}
// Convert x to the 192.64-bit fixed-point format.
uint256 x_192x64 = (xUint << 64) / uUNIT;
// Pass x to the `prbExp2` function, which uses the 192.64-bit fixed-point number representation.
result = wrap(prbExp2(x_192x64));
}
/// @notice Yields the greatest whole UD60x18 number less than or equal to x.
/// @dev Optimized for fractional value inputs, because for every whole value there are (1e18 - 1) fractional
/// counterparts. See https://en.wikipedia.org/wiki/Floor_and_ceiling_functions.
/// @param x The UD60x18 number to floor.
/// @param result The greatest integer less than or equal to x, as an UD60x18 number.
function floor(UD60x18 x) pure returns (UD60x18 result) {
assembly ("memory-safe") {
// Equivalent to "x % UNIT" but faster.
let remainder := mod(x, uUNIT)
// Equivalent to "x - remainder * (remainder > 0 ? 1 : 0)" but faster.
result := sub(x, mul(remainder, gt(remainder, 0)))
}
}
/// @notice Yields the excess beyond the floor of x.
/// @dev Based on the odd function definition https://en.wikipedia.org/wiki/Fractional_part.
/// @param x The UD60x18 number to get the fractional part of.
/// @param result The fractional part of x as an UD60x18 number.
function frac(UD60x18 x) pure returns (UD60x18 result) {
assembly ("memory-safe") {
result := mod(x, uUNIT)
}
}
/// @notice Calculates the geometric mean of x and y, i.e. $$sqrt(x * y)$$, rounding down.
///
/// @dev Requirements:
/// - x * y must fit within `MAX_UD60x18`, lest it overflows.
///
/// @param x The first operand as an UD60x18 number.
/// @param y The second operand as an UD60x18 number.
/// @return result The result as an UD60x18 number.
function gm(UD60x18 x, UD60x18 y) pure returns (UD60x18 result) {
uint256 xUint = unwrap(x);
uint256 yUint = unwrap(y);
if (xUint == 0 || yUint == 0) {
return ZERO;
}
unchecked {
// Checking for overflow this way is faster than letting Solidity do it.
uint256 xyUint = xUint * yUint;
if (xyUint / xUint != yUint) {
revert PRBMath_UD60x18_Gm_Overflow(x, y);
}
// We don't need to multiply the result by `UNIT` here because the x*y product had picked up a factor of `UNIT`
// during multiplication. See the comments in the `prbSqrt` function.
result = wrap(prbSqrt(xyUint));
}
}
/// @notice Calculates 1 / x, rounding toward zero.
///
/// @dev Requirements:
/// - x cannot be zero.
///
/// @param x The UD60x18 number for which to calculate the inverse.
/// @return result The inverse as an UD60x18 number.
function inv(UD60x18 x) pure returns (UD60x18 result) {
unchecked {
// 1e36 is UNIT * UNIT.
result = wrap(1e36 / unwrap(x));
}
}
/// @notice Calculates the natural logarithm of x.
///
/// @dev Based on the formula:
///
/// $$
/// ln{x} = log_2{x} / log_2{e}$$.
/// $$
///
/// Requirements:
/// - All from `log2`.
///
/// Caveats:
/// - All from `log2`.
/// - This doesn't return exactly 1 for 2.718281828459045235, for that more fine-grained precision is needed.
///
/// @param x The UD60x18 number for which to calculate the natural logarithm.
/// @return result The natural logarithm as an UD60x18 number.
function ln(UD60x18 x) pure returns (UD60x18 result) {
unchecked {
// We do the fixed-point multiplication inline to save gas. This is overflow-safe because the maximum value
// that `log2` can return is 196.205294292027477728.
result = wrap((unwrap(log2(x)) * uUNIT) / uLOG2_E);
}
}
/// @notice Calculates the common logarithm of x.
///
/// @dev First checks if x is an exact power of ten and it stops if yes. If it's not, calculates the common
/// logarithm based on the formula:
///
/// $$
/// log_{10}{x} = log_2{x} / log_2{10}
/// $$
///
/// Requirements:
/// - All from `log2`.
///
/// Caveats:
/// - All from `log2`.
///
/// @param x The UD60x18 number for which to calculate the common logarithm.
/// @return result The common logarithm as an UD60x18 number.
function log10(UD60x18 x) pure returns (UD60x18 result) {
uint256 xUint = unwrap(x);
if (xUint < uUNIT) {
revert PRBMath_UD60x18_Log_InputTooSmall(x);
}
// Note that the `mul` in this assembly block is the assembly multiplication operation, not the UD60x18 `mul`.
// prettier-ignore
assembly ("memory-safe") {
switch x
case 1 { result := mul(uUNIT, sub(0, 18)) }
case 10 { result := mul(uUNIT, sub(1, 18)) }
case 100 { result := mul(uUNIT, sub(2, 18)) }
case 1000 { result := mul(uUNIT, sub(3, 18)) }
case 10000 { result := mul(uUNIT, sub(4, 18)) }
case 100000 { result := mul(uUNIT, sub(5, 18)) }
case 1000000 { result := mul(uUNIT, sub(6, 18)) }
case 10000000 { result := mul(uUNIT, sub(7, 18)) }
case 100000000 { result := mul(uUNIT, sub(8, 18)) }
case 1000000000 { result := mul(uUNIT, sub(9, 18)) }
case 10000000000 { result := mul(uUNIT, sub(10, 18)) }
case 100000000000 { result := mul(uUNIT, sub(11, 18)) }
case 1000000000000 { result := mul(uUNIT, sub(12, 18)) }
case 10000000000000 { result := mul(uUNIT, sub(13, 18)) }
case 100000000000000 { result := mul(uUNIT, sub(14, 18)) }
case 1000000000000000 { result := mul(uUNIT, sub(15, 18)) }
case 10000000000000000 { result := mul(uUNIT, sub(16, 18)) }
case 100000000000000000 { result := mul(uUNIT, sub(17, 18)) }
case 1000000000000000000 { result := 0 }
case 10000000000000000000 { result := uUNIT }
case 100000000000000000000 { result := mul(uUNIT, 2) }
case 1000000000000000000000 { result := mul(uUNIT, 3) }
case 10000000000000000000000 { result := mul(uUNIT, 4) }
case 100000000000000000000000 { result := mul(uUNIT, 5) }
case 1000000000000000000000000 { result := mul(uUNIT, 6) }
case 10000000000000000000000000 { result := mul(uUNIT, 7) }
case 100000000000000000000000000 { result := mul(uUNIT, 8) }
case 1000000000000000000000000000 { result := mul(uUNIT, 9) }
case 10000000000000000000000000000 { result := mul(uUNIT, 10) }
case 100000000000000000000000000000 { result := mul(uUNIT, 11) }
case 1000000000000000000000000000000 { result := mul(uUNIT, 12) }
case 10000000000000000000000000000000 { result := mul(uUNIT, 13) }
case 100000000000000000000000000000000 { result := mul(uUNIT, 14) }
case 1000000000000000000000000000000000 { result := mul(uUNIT, 15) }
case 10000000000000000000000000000000000 { result := mul(uUNIT, 16) }
case 100000000000000000000000000000000000 { result := mul(uUNIT, 17) }
case 1000000000000000000000000000000000000 { result := mul(uUNIT, 18) }
case 10000000000000000000000000000000000000 { result := mul(uUNIT, 19) }
case 100000000000000000000000000000000000000 { result := mul(uUNIT, 20) }
case 1000000000000000000000000000000000000000 { result := mul(uUNIT, 21) }
case 10000000000000000000000000000000000000000 { result := mul(uUNIT, 22) }
case 100000000000000000000000000000000000000000 { result := mul(uUNIT, 23) }
case 1000000000000000000000000000000000000000000 { result := mul(uUNIT, 24) }
case 10000000000000000000000000000000000000000000 { result := mul(uUNIT, 25) }
case 100000000000000000000000000000000000000000000 { result := mul(uUNIT, 26) }
case 1000000000000000000000000000000000000000000000 { result := mul(uUNIT, 27) }
case 10000000000000000000000000000000000000000000000 { result := mul(uUNIT, 28) }
case 100000000000000000000000000000000000000000000000 { result := mul(uUNIT, 29) }
case 1000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 30) }
case 10000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 31) }
case 100000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 32) }
case 1000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 33) }
case 10000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 34) }
case 100000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 35) }
case 1000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 36) }
case 10000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 37) }
case 100000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 38) }
case 1000000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 39) }
case 10000000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 40) }
case 100000000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 41) }
case 1000000000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 42) }
case 10000000000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 43) }
case 100000000000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 44) }
case 1000000000000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 45) }
case 10000000000000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 46) }
case 100000000000000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 47) }
case 1000000000000000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 48) }
case 10000000000000000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 49) }
case 100000000000000000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 50) }
case 1000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 51) }
case 10000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 52) }
case 100000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 53) }
case 1000000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 54) }
case 10000000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 55) }
case 100000000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 56) }
case 1000000000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 57) }
case 10000000000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 58) }
case 100000000000000000000000000000000000000000000000000000000000000000000000000000 { result := mul(uUNIT, 59) }
default { result := uMAX_UD60x18 }
}
if (unwrap(result) == uMAX_UD60x18) {
unchecked {
// Do the fixed-point division inline to save gas.
result = wrap((unwrap(log2(x)) * uUNIT) / uLOG2_10);
}
}
}
/// @notice Calculates the binary logarithm of x.
///
/// @dev Based on the iterative approximation algorithm.
/// https://en.wikipedia.org/wiki/Binary_logarithm#Iterative_approximation
///
/// Requirements:
/// - x must be greater than or equal to UNIT, otherwise the result would be negative.
///
/// Caveats:
/// - The results are nor perfectly accurate to the last decimal, due to the lossy precision of the iterative
/// approximation.
///
/// @param x The UD60x18 number for which to calculate the binary logarithm.
/// @return result The binary logarithm as an UD60x18 number.
function log2(UD60x18 x) pure returns (UD60x18 result) {
uint256 xUint = unwrap(x);
if (xUint < uUNIT) {
revert PRBMath_UD60x18_Log_InputTooSmall(x);
}
unchecked {
// Calculate the integer part of the logarithm, add it to the result and finally calculate y = x * 2^(-n).
uint256 n = msb(xUint / uUNIT);
// This is the integer part of the logarithm as an UD60x18 number. The operation can't overflow because n
// n is maximum 255 and UNIT is 1e18.
uint256 resultUint = n * uUNIT;
// This is $y = x * 2^{-n}$.
uint256 y = xUint >> n;
// If y is 1, the fractional part is zero.
if (y == uUNIT) {
return wrap(resultUint);
}
// Calculate the fractional part via the iterative approximation.
// The "delta.rshift(1)" part is equivalent to "delta /= 2", but shifting bits is faster.
uint256 DOUBLE_UNIT = 2e18;
for (uint256 delta = uHALF_UNIT; delta > 0; delta >>= 1) {
y = (y * y) / uUNIT;
// Is y^2 > 2 and so in the range [2,4)?
if (y >= DOUBLE_UNIT) {
// Add the 2^{-m} factor to the logarithm.
resultUint += delta;
// Corresponds to z/2 on Wikipedia.
y >>= 1;
}
}
result = wrap(resultUint);
}
}
/// @notice Multiplies two UD60x18 numbers together, returning a new UD60x18 number.
/// @dev See the documentation for the `Common.mulDiv18` function.
/// @param x The multiplicand as an UD60x18 number.
/// @param y The multiplier as an UD60x18 number.
/// @return result The product as an UD60x18 number.
function mul(UD60x18 x, UD60x18 y) pure returns (UD60x18 result) {
result = wrap(mulDiv18(unwrap(x), unwrap(y)));
}
/// @notice Raises x to the power of y.
///
/// @dev Based on the formula:
///
/// $$
/// x^y = 2^{log_2{x} * y}
/// $$
///
/// Requirements:
/// - All from `exp2`, `log2` and `mul`.
///
/// Caveats:
/// - All from `exp2`, `log2` and `mul`.
/// - Assumes 0^0 is 1.
///
/// @param x Number to raise to given power y, as an UD60x18 number.
/// @param y Exponent to raise x to, as an UD60x18 number.
/// @return result x raised to power y, as an UD60x18 number.
function pow(UD60x18 x, UD60x18 y) pure returns (UD60x18 result) {
uint256 xUint = unwrap(x);
uint256 yUint = unwrap(y);
if (xUint == 0) {
result = yUint == 0 ? UNIT : ZERO;
} else {
if (yUint == uUNIT) {
result = x;
} else {
result = exp2(mul(log2(x), y));
}
}
}
/// @notice Raises x (an UD60x18 number) to the power y (unsigned basic integer) using the famous algorithm
/// "exponentiation by squaring".
///
/// @dev See https://en.wikipedia.org/wiki/Exponentiation_by_squaring
///
/// Requirements:
/// - The result must fit within `MAX_UD60x18`.
///
/// Caveats:
/// - All from "Common.mulDiv18".
/// - Assumes 0^0 is 1.
///
/// @param x The base as an UD60x18 number.
/// @param y The exponent as an uint256.
/// @return result The result as an UD60x18 number.
function powu(UD60x18 x, uint256 y) pure returns (UD60x18 result) {
// Calculate the first iteration of the loop in advance.
uint256 xUint = unwrap(x);
uint256 resultUint = y & 1 > 0 ? xUint : uUNIT;
// Equivalent to "for(y /= 2; y > 0; y /= 2)" but faster.
for (y >>= 1; y > 0; y >>= 1) {
xUint = mulDiv18(xUint, xUint);
// Equivalent to "y % 2 == 1" but faster.
if (y & 1 > 0) {
resultUint = mulDiv18(resultUint, xUint);
}
}
result = wrap(resultUint);
}
/// @notice Calculates the square root of x, rounding down.
/// @dev Uses the Babylonian method https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method.
///
/// Requirements:
/// - x must be less than `MAX_UD60x18` divided by `UNIT`.
///
/// @param x The UD60x18 number for which to calculate the square root.
/// @return result The result as an UD60x18 number.
function sqrt(UD60x18 x) pure returns (UD60x18 result) {
uint256 xUint = unwrap(x);
unchecked {
if (xUint > uMAX_UD60x18 / uUNIT) {
revert PRBMath_UD60x18_Sqrt_Overflow(x);
}
// Multiply x by `UNIT` to account for the factor of `UNIT` that is picked up when multiplying two UD60x18
// numbers together (in this case, the two numbers are both the square root).
result = wrap(prbSqrt(xUint * uUNIT));
}
}