/
PRBMath.sol
647 lines (579 loc) · 24.7 KB
/
PRBMath.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
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
// SPDX-License-Identifier: WTFPL
pragma solidity >=0.8.4;
/// @notice Emitted when the result overflows uint256.
error PRBMath__MulDivFixedPointOverflow(uint256 prod1);
/// @notice Emitted when the result overflows uint256.
error PRBMath__MulDivOverflow(uint256 prod1, uint256 denominator);
/// @notice Emitted when one of the inputs is type(int256).min.
error PRBMath__MulDivSignedInputTooSmall();
/// @notice Emitted when the intermediary absolute result overflows int256.
error PRBMath__MulDivSignedOverflow(uint256 rAbs);
/// @notice Emitted when the input is MIN_SD59x18.
error PRBMathSD59x18__AbsInputTooSmall();
/// @notice Emitted when ceiling a number overflows SD59x18.
error PRBMathSD59x18__CeilOverflow(int256 x);
/// @notice Emitted when one of the inputs is MIN_SD59x18.
error PRBMathSD59x18__DivInputTooSmall();
/// @notice Emitted when one of the intermediary unsigned results overflows SD59x18.
error PRBMathSD59x18__DivOverflow(uint256 rAbs);
/// @notice Emitted when the input is greater than 133.084258667509499441.
error PRBMathSD59x18__ExpInputTooBig(int256 x);
/// @notice Emitted when the input is greater than 192.
error PRBMathSD59x18__Exp2InputTooBig(int256 x);
/// @notice Emitted when flooring a number underflows SD59x18.
error PRBMathSD59x18__FloorUnderflow(int256 x);
/// @notice Emitted when converting a basic integer to the fixed-point format overflows SD59x18.
error PRBMathSD59x18__FromIntOverflow(int256 x);
/// @notice Emitted when converting a basic integer to the fixed-point format underflows SD59x18.
error PRBMathSD59x18__FromIntUnderflow(int256 x);
/// @notice Emitted when the product of the inputs is negative.
error PRBMathSD59x18__GmNegativeProduct(int256 x, int256 y);
/// @notice Emitted when multiplying the inputs overflows SD59x18.
error PRBMathSD59x18__GmOverflow(int256 x, int256 y);
/// @notice Emitted when the input is less than or equal to zero.
error PRBMathSD59x18__LogInputTooSmall(int256 x);
/// @notice Emitted when one of the inputs is MIN_SD59x18.
error PRBMathSD59x18__MulInputTooSmall();
/// @notice Emitted when the intermediary absolute result overflows SD59x18.
error PRBMathSD59x18__MulOverflow(uint256 rAbs);
/// @notice Emitted when the intermediary absolute result overflows SD59x18.
error PRBMathSD59x18__PowuOverflow(uint256 rAbs);
/// @notice Emitted when the input is negative.
error PRBMathSD59x18__SqrtNegativeInput(int256 x);
/// @notice Emitted when the calculting the square root overflows SD59x18.
error PRBMathSD59x18__SqrtOverflow(int256 x);
/// @notice Emitted when addition overflows UD60x18.
error PRBMathUD60x18__AddOverflow(uint256 x, uint256 y);
/// @notice Emitted when ceiling a number overflows UD60x18.
error PRBMathUD60x18__CeilOverflow(uint256 x);
/// @notice Emitted when the input is greater than 133.084258667509499441.
error PRBMathUD60x18__ExpInputTooBig(uint256 x);
/// @notice Emitted when the input is greater than 192.
error PRBMathUD60x18__Exp2InputTooBig(uint256 x);
/// @notice Emitted when converting a basic integer to the fixed-point format format overflows UD60x18.
error PRBMathUD60x18__FromUintOverflow(uint256 x);
/// @notice Emitted when multiplying the inputs overflows UD60x18.
error PRBMathUD60x18__GmOverflow(uint256 x, uint256 y);
/// @notice Emitted when the input is less than 1.
error PRBMathUD60x18__LogInputTooSmall(uint256 x);
/// @notice Emitted when the calculting the square root overflows UD60x18.
error PRBMathUD60x18__SqrtOverflow(uint256 x);
/// @notice Emitted when subtraction underflows UD60x18.
error PRBMathUD60x18__SubUnderflow(uint256 x, uint256 y);
/// @dev Common mathematical functions used in both PRBMathSD59x18 and PRBMathUD60x18. Note that this shared library
/// does not always assume the signed 59.18-decimal fixed-point or the unsigned 60.18-decimal fixed-point
/// representation. When it does not, it is explictly mentioned in the NatSpec documentation.
library PRBMath {
/// STRUCTS ///
struct SD59x18 {
int256 value;
}
struct UD60x18 {
uint256 value;
}
/// STORAGE ///
/// @dev How many trailing decimals can be represented.
uint256 internal constant SCALE = 1e18;
/// @dev Largest power of two divisor of SCALE.
uint256 internal constant SCALE_LPOTD = 262144;
/// @dev SCALE inverted mod 2^256.
uint256 internal constant SCALE_INVERSE = 78156646155174841979727994598816262306175212592076161876661508869554232690281;
/// FUNCTIONS ///
/// @notice Calculates the binary exponent of x using the binary fraction method.
/// @dev Has to use 192.64-bit fixed-point numbers.
/// See https://ethereum.stackexchange.com/a/96594/24693.
/// @param x The exponent as an unsigned 192.64-bit fixed-point number.
/// @return result The result as an unsigned 60.18-decimal fixed-point number.
function exp2(uint256 x) internal pure returns (uint256 result) {
unchecked {
// Start from 0.5 in the 192.64-bit fixed-point format.
result = 0x800000000000000000000000000000000000000000000000;
// Multiply the result by root(2, 2^-i) when the bit at position i is 1. None of the intermediary results overflows
// because the initial result is 2^191 and all magic factors are less than 2^65.
if (x & 0x8000000000000000 > 0) {
result = (result * 0x16A09E667F3BCC909) >> 64;
}
if (x & 0x4000000000000000 > 0) {
result = (result * 0x1306FE0A31B7152DF) >> 64;
}
if (x & 0x2000000000000000 > 0) {
result = (result * 0x1172B83C7D517ADCE) >> 64;
}
if (x & 0x1000000000000000 > 0) {
result = (result * 0x10B5586CF9890F62A) >> 64;
}
if (x & 0x800000000000000 > 0) {
result = (result * 0x1059B0D31585743AE) >> 64;
}
if (x & 0x400000000000000 > 0) {
result = (result * 0x102C9A3E778060EE7) >> 64;
}
if (x & 0x200000000000000 > 0) {
result = (result * 0x10163DA9FB33356D8) >> 64;
}
if (x & 0x100000000000000 > 0) {
result = (result * 0x100B1AFA5ABCBED61) >> 64;
}
if (x & 0x80000000000000 > 0) {
result = (result * 0x10058C86DA1C09EA2) >> 64;
}
if (x & 0x40000000000000 > 0) {
result = (result * 0x1002C605E2E8CEC50) >> 64;
}
if (x & 0x20000000000000 > 0) {
result = (result * 0x100162F3904051FA1) >> 64;
}
if (x & 0x10000000000000 > 0) {
result = (result * 0x1000B175EFFDC76BA) >> 64;
}
if (x & 0x8000000000000 > 0) {
result = (result * 0x100058BA01FB9F96D) >> 64;
}
if (x & 0x4000000000000 > 0) {
result = (result * 0x10002C5CC37DA9492) >> 64;
}
if (x & 0x2000000000000 > 0) {
result = (result * 0x1000162E525EE0547) >> 64;
}
if (x & 0x1000000000000 > 0) {
result = (result * 0x10000B17255775C04) >> 64;
}
if (x & 0x800000000000 > 0) {
result = (result * 0x1000058B91B5BC9AE) >> 64;
}
if (x & 0x400000000000 > 0) {
result = (result * 0x100002C5C89D5EC6D) >> 64;
}
if (x & 0x200000000000 > 0) {
result = (result * 0x10000162E43F4F831) >> 64;
}
if (x & 0x100000000000 > 0) {
result = (result * 0x100000B1721BCFC9A) >> 64;
}
if (x & 0x80000000000 > 0) {
result = (result * 0x10000058B90CF1E6E) >> 64;
}
if (x & 0x40000000000 > 0) {
result = (result * 0x1000002C5C863B73F) >> 64;
}
if (x & 0x20000000000 > 0) {
result = (result * 0x100000162E430E5A2) >> 64;
}
if (x & 0x10000000000 > 0) {
result = (result * 0x1000000B172183551) >> 64;
}
if (x & 0x8000000000 > 0) {
result = (result * 0x100000058B90C0B49) >> 64;
}
if (x & 0x4000000000 > 0) {
result = (result * 0x10000002C5C8601CC) >> 64;
}
if (x & 0x2000000000 > 0) {
result = (result * 0x1000000162E42FFF0) >> 64;
}
if (x & 0x1000000000 > 0) {
result = (result * 0x10000000B17217FBB) >> 64;
}
if (x & 0x800000000 > 0) {
result = (result * 0x1000000058B90BFCE) >> 64;
}
if (x & 0x400000000 > 0) {
result = (result * 0x100000002C5C85FE3) >> 64;
}
if (x & 0x200000000 > 0) {
result = (result * 0x10000000162E42FF1) >> 64;
}
if (x & 0x100000000 > 0) {
result = (result * 0x100000000B17217F8) >> 64;
}
if (x & 0x80000000 > 0) {
result = (result * 0x10000000058B90BFC) >> 64;
}
if (x & 0x40000000 > 0) {
result = (result * 0x1000000002C5C85FE) >> 64;
}
if (x & 0x20000000 > 0) {
result = (result * 0x100000000162E42FF) >> 64;
}
if (x & 0x10000000 > 0) {
result = (result * 0x1000000000B17217F) >> 64;
}
if (x & 0x8000000 > 0) {
result = (result * 0x100000000058B90C0) >> 64;
}
if (x & 0x4000000 > 0) {
result = (result * 0x10000000002C5C860) >> 64;
}
if (x & 0x2000000 > 0) {
result = (result * 0x1000000000162E430) >> 64;
}
if (x & 0x1000000 > 0) {
result = (result * 0x10000000000B17218) >> 64;
}
if (x & 0x800000 > 0) {
result = (result * 0x1000000000058B90C) >> 64;
}
if (x & 0x400000 > 0) {
result = (result * 0x100000000002C5C86) >> 64;
}
if (x & 0x200000 > 0) {
result = (result * 0x10000000000162E43) >> 64;
}
if (x & 0x100000 > 0) {
result = (result * 0x100000000000B1721) >> 64;
}
if (x & 0x80000 > 0) {
result = (result * 0x10000000000058B91) >> 64;
}
if (x & 0x40000 > 0) {
result = (result * 0x1000000000002C5C8) >> 64;
}
if (x & 0x20000 > 0) {
result = (result * 0x100000000000162E4) >> 64;
}
if (x & 0x10000 > 0) {
result = (result * 0x1000000000000B172) >> 64;
}
if (x & 0x8000 > 0) {
result = (result * 0x100000000000058B9) >> 64;
}
if (x & 0x4000 > 0) {
result = (result * 0x10000000000002C5D) >> 64;
}
if (x & 0x2000 > 0) {
result = (result * 0x1000000000000162E) >> 64;
}
if (x & 0x1000 > 0) {
result = (result * 0x10000000000000B17) >> 64;
}
if (x & 0x800 > 0) {
result = (result * 0x1000000000000058C) >> 64;
}
if (x & 0x400 > 0) {
result = (result * 0x100000000000002C6) >> 64;
}
if (x & 0x200 > 0) {
result = (result * 0x10000000000000163) >> 64;
}
if (x & 0x100 > 0) {
result = (result * 0x100000000000000B1) >> 64;
}
if (x & 0x80 > 0) {
result = (result * 0x10000000000000059) >> 64;
}
if (x & 0x40 > 0) {
result = (result * 0x1000000000000002C) >> 64;
}
if (x & 0x20 > 0) {
result = (result * 0x10000000000000016) >> 64;
}
if (x & 0x10 > 0) {
result = (result * 0x1000000000000000B) >> 64;
}
if (x & 0x8 > 0) {
result = (result * 0x10000000000000006) >> 64;
}
if (x & 0x4 > 0) {
result = (result * 0x10000000000000003) >> 64;
}
if (x & 0x2 > 0) {
result = (result * 0x10000000000000001) >> 64;
}
if (x & 0x1 > 0) {
result = (result * 0x10000000000000001) >> 64;
}
// We're doing two things at the same time:
//
// 1. Multiply the result by 2^n + 1, where "2^n" is the integer part and the one is added to account for
// the fact that we initially set the result to 0.5. This is accomplished by subtracting from 191
// rather than 192.
// 2. Convert the result to the unsigned 60.18-decimal fixed-point format.
//
// This works because 2^(191-ip) = 2^ip / 2^191, where "ip" is the integer part "2^n".
result *= SCALE;
result >>= (191 - (x >> 64));
}
}
/// @notice Finds the zero-based index of the first one in the binary representation of x.
/// @dev See the note on msb in the "Find First Set" Wikipedia article https://en.wikipedia.org/wiki/Find_first_set
/// @param x The uint256 number for which to find the index of the most significant bit.
/// @return msb The index of the most significant bit as an uint256.
function mostSignificantBit(uint256 x) internal pure returns (uint256 msb) {
if (x >= 2**128) {
x >>= 128;
msb += 128;
}
if (x >= 2**64) {
x >>= 64;
msb += 64;
}
if (x >= 2**32) {
x >>= 32;
msb += 32;
}
if (x >= 2**16) {
x >>= 16;
msb += 16;
}
if (x >= 2**8) {
x >>= 8;
msb += 8;
}
if (x >= 2**4) {
x >>= 4;
msb += 4;
}
if (x >= 2**2) {
x >>= 2;
msb += 2;
}
if (x >= 2**1) {
// No need to shift x any more.
msb += 1;
}
}
/// @notice Calculates floor(x*y÷denominator) with full precision.
///
/// @dev Credit to Remco Bloemen under MIT license https://xn--2-umb.com/21/muldiv.
///
/// Requirements:
/// - The denominator cannot be zero.
/// - The result must fit within uint256.
///
/// Caveats:
/// - This function does not work with fixed-point numbers.
///
/// @param x The multiplicand as an uint256.
/// @param y The multiplier as an uint256.
/// @param denominator The divisor as an uint256.
/// @return result The result as an uint256.
function mulDiv(
uint256 x,
uint256 y,
uint256 denominator
) internal pure returns (uint256 result) {
// 512-bit multiply [prod1 prod0] = x * y. Compute the product mod 2^256 and mod 2^256 - 1, then use
// use the Chinese Remainder Theorem to reconstruct the 512 bit result. The result is stored in two 256
// variables such that product = prod1 * 2^256 + prod0.
uint256 prod0; // Least significant 256 bits of the product
uint256 prod1; // Most significant 256 bits of the product
assembly {
let mm := mulmod(x, y, not(0))
prod0 := mul(x, y)
prod1 := sub(sub(mm, prod0), lt(mm, prod0))
}
// Handle non-overflow cases, 256 by 256 division.
if (prod1 == 0) {
unchecked {
result = prod0 / denominator;
}
return result;
}
// Make sure the result is less than 2^256. Also prevents denominator == 0.
if (prod1 >= denominator) {
revert PRBMath__MulDivOverflow(prod1, denominator);
}
///////////////////////////////////////////////
// 512 by 256 division.
///////////////////////////////////////////////
// Make division exact by subtracting the remainder from [prod1 prod0].
uint256 remainder;
assembly {
// Compute remainder using mulmod.
remainder := mulmod(x, y, denominator)
// Subtract 256 bit number from 512 bit number.
prod1 := sub(prod1, gt(remainder, prod0))
prod0 := sub(prod0, remainder)
}
// Factor powers of two out of denominator and compute largest power of two divisor of denominator. Always >= 1.
// See https://cs.stackexchange.com/q/138556/92363.
unchecked {
// Does not overflow because the denominator cannot be zero at this stage in the function.
uint256 lpotdod = denominator & (~denominator + 1);
assembly {
// Divide denominator by lpotdod.
denominator := div(denominator, lpotdod)
// Divide [prod1 prod0] by lpotdod.
prod0 := div(prod0, lpotdod)
// Flip lpotdod such that it is 2^256 / lpotdod. If lpotdod is zero, then it becomes one.
lpotdod := add(div(sub(0, lpotdod), lpotdod), 1)
}
// Shift in bits from prod1 into prod0.
prod0 |= prod1 * lpotdod;
// Invert denominator mod 2^256. Now that denominator is an odd number, it has an inverse modulo 2^256 such
// that denominator * inv = 1 mod 2^256. Compute the inverse by starting with a seed that is correct for
// four bits. That is, denominator * inv = 1 mod 2^4.
uint256 inverse = (3 * denominator) ^ 2;
// Now use Newton-Raphson iteration to improve the precision. Thanks to Hensel's lifting lemma, this also works
// in modular arithmetic, doubling the correct bits in each step.
inverse *= 2 - denominator * inverse; // inverse mod 2^8
inverse *= 2 - denominator * inverse; // inverse mod 2^16
inverse *= 2 - denominator * inverse; // inverse mod 2^32
inverse *= 2 - denominator * inverse; // inverse mod 2^64
inverse *= 2 - denominator * inverse; // inverse mod 2^128
inverse *= 2 - denominator * inverse; // inverse mod 2^256
// Because the division is now exact we can divide by multiplying with the modular inverse of denominator.
// This will give us the correct result modulo 2^256. Since the preconditions guarantee that the outcome is
// less than 2^256, this is the final result. We don't need to compute the high bits of the result and prod1
// is no longer required.
result = prod0 * inverse;
return result;
}
}
/// @notice Calculates floor(x*y÷1e18) with full precision.
///
/// @dev Variant of "mulDiv" with constant folding, i.e. in which the denominator is always 1e18. Before returning the
/// final result, we add 1 if (x * y) % SCALE >= HALF_SCALE. Without this, 6.6e-19 would be truncated to 0 instead of
/// being rounded to 1e-18. See "Listing 6" and text above it at https://accu.org/index.php/journals/1717.
///
/// Requirements:
/// - The result must fit within uint256.
///
/// Caveats:
/// - The body is purposely left uncommented; see the NatSpec comments in "PRBMath.mulDiv" to understand how this works.
/// - It is assumed that the result can never be type(uint256).max when x and y solve the following two equations:
/// 1. x * y = type(uint256).max * SCALE
/// 2. (x * y) % SCALE >= SCALE / 2
///
/// @param x The multiplicand as an unsigned 60.18-decimal fixed-point number.
/// @param y The multiplier as an unsigned 60.18-decimal fixed-point number.
/// @return result The result as an unsigned 60.18-decimal fixed-point number.
function mulDivFixedPoint(uint256 x, uint256 y) internal pure returns (uint256 result) {
uint256 prod0;
uint256 prod1;
assembly {
let mm := mulmod(x, y, not(0))
prod0 := mul(x, y)
prod1 := sub(sub(mm, prod0), lt(mm, prod0))
}
if (prod1 >= SCALE) {
revert PRBMath__MulDivFixedPointOverflow(prod1);
}
uint256 remainder;
uint256 roundUpUnit;
assembly {
remainder := mulmod(x, y, SCALE)
roundUpUnit := gt(remainder, 499999999999999999)
}
if (prod1 == 0) {
unchecked {
result = (prod0 / SCALE) + roundUpUnit;
return result;
}
}
assembly {
result := add(
mul(
or(
div(sub(prod0, remainder), SCALE_LPOTD),
mul(sub(prod1, gt(remainder, prod0)), add(div(sub(0, SCALE_LPOTD), SCALE_LPOTD), 1))
),
SCALE_INVERSE
),
roundUpUnit
)
}
}
/// @notice Calculates floor(x*y÷denominator) with full precision.
///
/// @dev An extension of "mulDiv" for signed numbers. Works by computing the signs and the absolute values separately.
///
/// Requirements:
/// - None of the inputs can be type(int256).min.
/// - The result must fit within int256.
///
/// @param x The multiplicand as an int256.
/// @param y The multiplier as an int256.
/// @param denominator The divisor as an int256.
/// @return result The result as an int256.
function mulDivSigned(
int256 x,
int256 y,
int256 denominator
) internal pure returns (int256 result) {
if (x == type(int256).min || y == type(int256).min || denominator == type(int256).min) {
revert PRBMath__MulDivSignedInputTooSmall();
}
// Get hold of the absolute values of x, y and the denominator.
uint256 ax;
uint256 ay;
uint256 ad;
unchecked {
ax = x < 0 ? uint256(-x) : uint256(x);
ay = y < 0 ? uint256(-y) : uint256(y);
ad = denominator < 0 ? uint256(-denominator) : uint256(denominator);
}
// Compute the absolute value of (x*y)÷denominator. The result must fit within int256.
uint256 rAbs = mulDiv(ax, ay, ad);
if (rAbs > uint256(type(int256).max)) {
revert PRBMath__MulDivSignedOverflow(rAbs);
}
// Get the signs of x, y and the denominator.
uint256 sx;
uint256 sy;
uint256 sd;
assembly {
sx := sgt(x, sub(0, 1))
sy := sgt(y, sub(0, 1))
sd := sgt(denominator, sub(0, 1))
}
// XOR over sx, sy and sd. This is checking whether there are one or three negative signs in the inputs.
// If yes, the result should be negative.
result = sx ^ sy ^ sd == 0 ? -int256(rAbs) : int256(rAbs);
}
/// @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.
///
/// Caveats:
/// - This function does not work with fixed-point numbers.
///
/// @param x The uint256 number for which to calculate the square root.
/// @return result The result as an uint256.
function sqrt(uint256 x) internal pure returns (uint256 result) {
if (x == 0) {
return 0;
}
// Set the initial guess to the closest power of two that is higher than x.
uint256 xAux = uint256(x);
result = 1;
if (xAux >= 0x100000000000000000000000000000000) {
xAux >>= 128;
result <<= 64;
}
if (xAux >= 0x10000000000000000) {
xAux >>= 64;
result <<= 32;
}
if (xAux >= 0x100000000) {
xAux >>= 32;
result <<= 16;
}
if (xAux >= 0x10000) {
xAux >>= 16;
result <<= 8;
}
if (xAux >= 0x100) {
xAux >>= 8;
result <<= 4;
}
if (xAux >= 0x10) {
xAux >>= 4;
result <<= 2;
}
if (xAux >= 0x8) {
result <<= 1;
}
// The operations can never overflow because the result is max 2^127 when it enters this block.
unchecked {
result = (result + x / result) >> 1;
result = (result + x / result) >> 1;
result = (result + x / result) >> 1;
result = (result + x / result) >> 1;
result = (result + x / result) >> 1;
result = (result + x / result) >> 1;
result = (result + x / result) >> 1; // Seven iterations should be enough
uint256 roundedDownResult = x / result;
return result >= roundedDownResult ? roundedDownResult : result;
}
}
}