Can I square root in Solidity?

Question

Is it possible to square root 50 or should I use 7.071067.

I'm very new in programming and I also understand that it's possible in all other languages, but I'm not able to see where the limitations are.

Answer 1

An implementation of a square root function was added to the dapp-bin as part of a maths library a while back.

Have a look at PR#50 (which is actually still open). I think the discussions boil down to the following:

function sqrt(uint x) returns (uint y) {
    uint z = (x + 1) / 2;
    y = x;
    while (z < y) {
        y = z;
        z = (x / z + z) / 2;
    }
}

Which is the Babylonian Method of finding the square root.

Answer 2

An alternative implementation for the Babylonian method, sourced from the Uniswap v2 code base:

function sqrt(uint y) internal pure returns (uint z) {
    if (y > 3) {
        z = y;
        uint x = y / 2 + 1;
        while (x < z) {
            z = x;
            x = (y / x + x) / 2;
        }
    } else if (y != 0) {
        z = 1;
    }
}

The advantage of using this over other implementations is that Uniswap is securing billions of dollars of trade volume (as of September 2020 the least). If it works for them, it should work for you too.

Answer 3

This is perhaps the fastest/ cheapest algorithm of all. Given an input x:

1. Calculate the square root of the perfect square of a power of two that is the closest to x.
2. Use the result from #1 as the initial guess for the Babylonian algorithm.

Here's an implementation:

/// @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.
/// @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;
    }

    // Calculate the square root of the perfect square of a power of two that is the closest to 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;
    }
}

The function above is copied from my advanced math library PRBMath, which offers more math functions than just the square root (e.g. logarithms, exponentials, powers).

Answer 4

Currently we are talking about implementing fixed point exponentiation which means that yes, in the near future, it should be possible to implement square roots and roots of all kinds...with one caveat...they cannot be infinitely repeating...you will have to cast them to a fixed size so you might lose some accuracy on it.

There is not, and will likely never be a floating point value running on ethereum....it's simply too expensive to make that happen. So we have chosen the fixed point route. Should be up within the coming weeks.

Without that...yes, there is something in the math library, but I'm afraid that without a fixed point value, there's not alot to be done with it.

Answer 5

There are no floats in solidity as far as I know. There's probably some code somewhere for calculating square roots using integer representations of floats, but that would be outside solidity. I'm about 80% certain of this answer, so someone who knows more might want to respond as well.

Answer 6

I've started working on a fixed-point math library for solidity. It's open source (apache 2) and you're invited to use and contribute. This library can solve your problem by providing a set of basic math functions such as log, power, root, etc., that use fixed point decimal numbers of the kind customarily used for ERC20 tokens and automatic market makers.

Please find the code here: https://github.com/extraterrestrial-tech/fixidity

It's low on documentation right now, so please contact me if you have any questions.