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