20

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.

1
22

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.

3
  • 2
    You're amazing, I will use Babylonian methods in the future.
    – Sileniced
    Apr 12 '16 at 19:32
  • Until the PR is merged, see here: github.com/ethereum/dapp-bin/pull/50/files for the latest implementation. Jul 25 '18 at 20:07
  • 3
    Note error is big for small numbers, as Solidity doesn't deal with floats. One way to reduce the error, if your calculations only rely on mul/div, is to multiply the input by 10000, and once your done mul/div the result, divide it by 100. Jan 21 '19 at 0:13
5

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.

3
  • 1
    fixed point square root can be very useful. It's not a requirement to have floating point, you can roll your own fixed point implementation (I just multiply everyhing by 1e6 myself). Be happy when I don't have to do that however.
    – Paul S
    Apr 12 '16 at 23:18
  • it's Jan 2019, unfortunately the near future never came Jan 20 '19 at 23:49
  • Apr 2021 and it's still a WIP in Solidity. However Vyper has decimal fixed-point types. Apr 7 at 10:24
5

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.

4
3

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.

1
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).

0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.