Incorrect hardcoded value of 0x8 in sqrt function (should be 0x4)

[nonergodic]

Incorrect hardcoded value of 0x8 in sqrt function (should be 0x4)

[PaulRBerg]

I cannot thank you enough for taking the time to report and explain this!

I created an issue to track the fix for the comment: #103

The issue wasn't just for these values though, but also for all their left shifted variants.

Oh, but of course.

The (likely) reason why this issue didn't pop up during testing (and is of little consequence to users) is that it doesn't matter for small values because Heron's iteration is run 7x times anyway and so even a bad initial guess will converge to the right result.

Makes sense.

[PaulRBerg]

Hi @nonergodic, thanks for opening this issue.

Would you mind explaining why we should use 0x4 instead of 0x8?

Re solc - as far as I remember, hardcoding the operations like I did was faster than using a for loop. But that was with the compiler that was available in 2021. It might be different now, I'm not sure.

[nonergodic]

Would you mind explaining why we should use 0x4 instead of 0x8?

Because your own comment says:
// Set the initial guess to the least power of two that is greater than or equal to sqrt(x).
But if x is 4,5,6, or 7, the code will have result = 1 as the initial guess, which is less than sqrt(x) for those values.

(Unrelated tangent: You're also using >= comparison, which might also be unnecessarily gas inefficient (there are only GT and EQ opcodes) depending on what optimizations solc is capable of... after all a >= hardocdedConstant is the same as A > hardcodedConstanst-1)

there are other libraries that make the same mistake:
https://github.com/abdk-consulting/abdk-libraries-solidity/blob/d8817cb600381319992d7caa038bf4faceb1097f/ABDKMath64x64.sol#L727 (I opened an issue with them too)

notably, OpenZeppelin gets it right (though likely still somewhat gas inefficient):
https://github.com/OpenZeppelin/openzeppelin-contracts/blob/74738721dc9cfa820687f6b700d2583b16a21c0d/contracts/utils/math/Math.sol#L196

[PaulRBerg]

Thanks for explaining! Makes sense. It looks like @Amxx's PR addresses this issue.

I think that the reason I haven't caught this in the tests is that I did not pass 4, 5, 6 or 7 as an input in the tests I've written for the sqrt function.

The good news is that {4,5,6,7} in the number format used by PRBMath are tiny values, i.e. {4e-18, 5e-18, 6e-18, 7e-18}. The results were prone to have precision errors nonetheless, and they shouldn't have been a concern for most users.

Re >= vs > tangent - thanks for your suggestion, I opened issue for it: https://github.com/paulrberg/prb-math/issues/99.

[nonergodic]

A couple of additional remarks:

Looking at the code more closely, the comment is also (and still) wrong:

// Set the initial guess to the least power of two that is greater than or equal to sqrt(x).

What it should say is:
Set the initial guess to the largest power of two that is smaller than or equal to sqrt(x). (again, compare with OpenZeppelin)

The good news is that {4,5,6,7} in the number format used by PRBMath are tiny values.

The issue wasn't just for these values though, but also for all their left shifted variants. i.e. if you were to start out with e.g. 6 left shifted by 4 (i.e. 96 = 0x60), you'd compare with 0x10, find that 0x60 is larger, hence right shift xAux by 4 to 0x06 and left shift result by 2 from 1 to 4.
And then you'd be back to the original situation where 6 is being compared to 0x08, and hence you'd end up with an initial guess of 4.

Notice thought that even after the fix, you'll only end up with an initial guess of 8 and sqrt(96) > 9, so 8 is still not a power of 2 that is greater than or equal to sqrt(x).

The (likely) reason why this issue didn't pop up during testing (and is of little consequence to users) is that it doesn't matter for small values because Heron's iteration is run 7x times anyway and so even a bad initial guess will converge to the right result.
So incorrect results can only arise for large numbers (i.e. close to the upper range of uint256) and in that case a bad initial guess might give you less precision in the lower digits after 7 iterations and it's highly unlikely that anyone will care about the last couple of digits in a number that covers ~36 orders of magnitude:

From here:

Let's go to the largest size there is: the visible universe. The radius of the universe is about 46 billion light years. Now let me ask a different question: How many digits of pi would we need to calculate the circumference of a circle with a radius of 46 billion light years to an accuracy equal to the diameter of a hydrogen atom (the simplest atom)? The answer is that you would need 39 or 40 decimal places.