Calculating roots in solidity

General
5

Here’s an implementation of Newton’s method -

    function nthRoot(uint _a, uint _n, uint _dp, uint _maxIts) public returns(uint) {
        assert (_n > 1);

        // The scale factor is a crude way to turn everything into integer calcs.
        // Actually do (a * (10 ^ ((dp + 1) * n))) ^ (1/n)
        // We calculate to one extra dp and round at the end
        uint one = 10 ** (1 + _dp);
        uint a0 = one ** _n * _a;

        // Initial guess: 1.0
        uint xNew = one;
        uint x;

        uint iter = 0;
        while (xNew != x && iter < _maxIts) {
            uint x = xNew;
            uint t0 = x ** (_n - 1);
            if (x * t0 > a0) {
                xNew = x - (x - a0 / t0) / _n;

            } else {
                xNew = x + (a0 / t0 - x) / _n;
            }
            ++iter;
        }

        // Round to nearest in the last dp.
        return (xNew + 5) / 10;
    }

It is fairly gas intensive, and doesn’t work a lot of the time. If you put in a different value for the decimal places, then it can never converges, even if it is a smaller value. Or if you ask for a smaller root, or a larger one, then it will converge quickly but to the wrong answer. And then for other inputs, mostly ones that are small in general (not that many decimal places, only 4th or 5th roots, not a billion for the base) it’s better. But it’s hard to have confidence in this one. Maybe it is worth trying to improve - depending on how other stuff goes.

1 Like