Is there any way to get square root of Nat numbers bigger than 64 bits?

Hello Dear All!

Is there any way to get square root of Nat numbers bigger than 64 bits?
I tried this but it produces error canister trapped explicitly: losing precision

var num = 112345678912345678900 * 112345678912345678900; // OK
var ftval = Float.fromInt(num); // <- error
var sqr = Float.sqrt(ftval);

Yes, that is rather unhelpful. I created an issue.

Until that’s fixed, you’ll have to use your own conversion routine, e.g.:

let base = 0x1000_0000_0000_0000;
func nontrappingNatToFloat(n : Nat) : Float {
    var m : Nat = n;
    var x : Float = 0;
    var p : Float = 1;
    while (m > 0) {
        x += p * Float.fromInt(m % base);
        p *= Float.fromInt(base);
        m /= base;
    };
    return x;
};
1 Like

@rossberg Thank you for your reply!

But the routine produces different result than Nat version

var num = 112345678912345678900 * 112345678912345678900; // OK
Debug.print("Nat num: " # _Nat.toText(num));
var newFt = nontrappingNatToFloat(num);
Debug.print("Flt num: " # _Float.toText(newFt));

Results:

Nat num: 12621551570275872565156226207501905210000
Flt num: 12621551570275871845290248787080326938624.000000

That’s expected. 64 bit floats only have a mantissa precision of 53 bits, which corresponds to roughly 16 decimal digits. So you get rounding errors when you convert larger integers. See here for more background. Floats are inappropriate if you need exact precision.

3 Likes

It took its time, but after https://github.com/dfinity/motoko-base/pull/281 has been merged, the next release of Motoko will have non-trapping Float to Int (and back) conversions, as inherited from the underlying LibTomMath library. Still, many caveats apply, as round-tripping is lossy on many levels, and NaNs and Infinities will probably have surprising behaviours.

Addendum: moc 0.6.9 is now released, Next up: dfx.

2 Likes

I use Newton iterative method to implement the code as follows:

 public func sqrt(x : Nat) : Nat {
        if (x == 0) {
           return 0;
        };

        var pre : Int = 0;
        var cur : Int = 1;

        loop {
            pre := cur;
            cur := (cur + x/cur)/2;

            if (Int.abs(cur - pre) <= 1) {
                return Int.abs(cur);
            };
        } while(true);

        Int.abs(cur);
    };
1 Like