1 | import { BN } from './bn.js';
|
2 | import { BN_MAX_INTEGER, BN_ONE, BN_SQRT_MAX_INTEGER } from './consts.js';
|
3 | import { bnToBn } from './toBn.js';
|
4 | /**
|
5 | * @name bnSqrt
|
6 | * @summary Calculates the integer square root of a BN
|
7 | * @example
|
8 | * <BR>
|
9 | *
|
10 | * ```javascript
|
11 | * import BN from 'bn.js';
|
12 | * import { bnSqrt } from '@polkadot/util';
|
13 | *
|
14 | * bnSqrt(new BN(16)).toString(); // => '4'
|
15 | * ```
|
16 | */
|
17 | export function bnSqrt(value) {
|
18 | const n = bnToBn(value);
|
19 | if (n.isNeg()) {
|
20 | throw new Error('square root of negative numbers is not supported');
|
21 | }
|
22 | // https://stackoverflow.com/questions/53683995/javascript-big-integer-square-root/
|
23 | // shortcut <= 2^53 - 1 to use the JS utils
|
24 | if (n.lte(BN_MAX_INTEGER)) {
|
25 | // ~~ More performant version of Math.floor
|
26 | return new BN(~~Math.sqrt(n.toNumber()));
|
27 | }
|
28 | // Use sqrt(MAX_SAFE_INTEGER) as starting point. since we already know the
|
29 | // output will be larger than this, we expect this to be a safe start
|
30 | let x0 = BN_SQRT_MAX_INTEGER.clone();
|
31 | while (true) {
|
32 | const x1 = n.div(x0).iadd(x0).ishrn(1);
|
33 | if (x0.eq(x1) || x0.eq(x1.sub(BN_ONE))) {
|
34 | return x0;
|
35 | }
|
36 | x0 = x1;
|
37 | }
|
38 | } |
\ | No newline at end of file |