cfx_math/
lib.rs

1pub mod nth_root;
2
3pub use nth_root::{nth_inv_root, nth_root};
4
5use cfx_types::U256;
6use num::integer::Roots;
7
8pub fn sqrt_u256(input: U256) -> U256 {
9    let bits = input.bits();
10    if bits <= 64 {
11        return input.as_u64().sqrt().into();
12    }
13
14    /************************************************************
15    * Step 1: pick the most significant 64 bits and estimate an
16    * approximate root.
17    ===========================================================*/
18    let significant_bits = 64 - bits % 2;
19    // The `rest_bits` must be even number.
20    let rest_bits = bits - significant_bits;
21    // The `input >> rest_bits` has `significant_bits`
22    let significant_word = (input >> rest_bits).as_u64();
23    // The `init_root` is slightly larger than the correct root.
24    let init_root =
25        U256::from(significant_word.sqrt() + 1u64) << (rest_bits / 2);
26
27    /*=================================================================
28    * Step 2: use the Newton's method to estimate the accurate value.
29    =================================================================*/
30    let mut root = init_root;
31    // Will iterate for at most 4 rounds.
32    while root * root > input {
33        root = (input / root + root) / 2;
34    }
35
36    root
37}
38
39pub fn power_two_fractional(ratio: u64, increase: bool, precision: u8) -> U256 {
40    assert!(precision <= 127);
41
42    let mut base = U256::one();
43    base <<= 254usize;
44
45    for i in 0..64u64 {
46        if ratio & (1 << i) != 0 {
47            if increase {
48                base <<= 1usize;
49            } else {
50                base >>= 1usize;
51            }
52        }
53        base = sqrt_u256(base);
54        base <<= 127usize;
55    }
56
57    base >>= (254 - precision) as usize;
58    // Computing error < 5.2 * 2 ^ -127
59    base
60}
cfx_math/lib.rs

cfx_math/
lib.rs
