1

That is, how to check whether a given number is 10, 100, 1000, etc., all the way up to 10**77, which is the highest power of 10 that fits in uint256.

2 Answers 2

3

I can think of four ways, ordered below from least efficient to most efficient. I didn't include any gas costs because they vary based on the value of x, whether you use the compiler optimizer, what's the highest power of ten supported etc.

The code snippets are written for Solidity v0.8 and they use table lookups with values up to 10**5, for brevity, but you can extend these to 10**77.

Iterative Division

The most naive and the most expensive.

function isPowerOfTen(uint256 x) external view returns (bool result) {
    while (x > 9 && x % 10 == 0) {
        x /= 10;
    }
    result = x == 1;
}

Some gas can be saved by wrapping the calculations under an unchecked block, but only a little.

Array Lookup via Binary Search

Slightly better than the first approach, but not by much. Also verbose.

function binarySearch(
    uint256[6] memory data,
    uint256 begin,
    uint256 end,
    uint256 value
) internal pure returns (uint256 ret) {
    uint256 len = end - begin;
    if (len == 0 || (len == 1 && data[begin] != value)) {
        return type(uint256).max;
    }
    uint256 mid = begin + len / 2;
    uint256 v = data[mid];
    if (value < v) {
        return binarySearch(data, begin, mid, value);
    } else if (value > v) {
        return binarySearch(data, mid + 1, end, value);
    } else {
        return mid;
    }
}

function isPowerOfTen(uint256 x) external view returns (bool result) {
    uint256[6] memory powersOfTen = [uint256(10**0), 10**1, 10**2, 10**3, 10**4, 10**5];
    result = binarySearch(powersOfTen, 0, powersOfTen.length, x) != type(uint256).max;
}

If Else Chain

Easy and cheap, although a tad verbose if you need to support big powers of ten. Use this if yul (assembly code) is not your cup of tea.

function isPowerOfTen(uint256 x) external view returns (bool result) {
    result = x == 10**0 || x == 10**1 || x == 10**2 || x == 10**3 || x == 10**4 || x == 10**5;
}

Yul Switch Control

The most efficient. Relies on the switch control operator, which is available only in yul.

function isPowerOfTen(uint256 x) external view returns (bool result) {
    assembly {
        switch x
        case 1 { result := true }
        case 10 { result := true }
        case 100 { result := true }
        case 1000 { result := true }
        case 10000 { result := true }
        case 100000 { result := true }
    }
}

Works for non-powers of ten because by default result is false. Not including a default case saves a bit of gas.

2

I am working on more optimised version based on the idea that power of 10 would have same number of trailing zero bits as power of 5. But need to wait till code data location modifier will be fully implemented in Solidity to introduce table of 77 powers of 5: https://github.com/ethereum/solidity/issues/12587#issuecomment-1069183987

https://gist.github.com/k06a/12f7d1a4e94edaaf5fe74957d06d4680

// https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup
function isPowerOfTen(uint256 x) public pure returns (bool result) {
    assembly {
        let dict := 0x00011c021d0e18031e16140f191104081f1b0d17151310071a0c12060b050a09

        let zeroes := 0
        for { let offset := 0 } lt(offset, 256) { offset := add(offset, 32) } {
            let v := and(shr(offset, x), 0xffffffff)

            switch v
            case 0 {
                zeroes := add(zeroes, 32)
            }
            default {
                zeroes := add(zeroes, byte(shr(27, mul(and(v, sub(0, v)), 0x077CB531)), dict))
            }
        }

        result := eq(shr(zeroes, x), pow(5, zeroes)) // todo: use table of powers
    }
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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