The Uniswap sqrt function makes sense to me. I can input 100 and it returns 10. Gnosis on the other hand has a gnarly 368 lines of code expressing the same function (I think) but the return value is very odd i.e., inputting 100 returns 21888242871839275222246405745257275088696311157297823662689037894645226208573.
What's happening under the hood with Gnosis?
Uniswap example:
/* Derived from UniSwapV2 code base */
/* https://github.com/Uniswap/v2-core/blob/v1.0.1/contracts/libraries/Math.sol */
function sqrtUniswap(uint y) public pure returns (uint256 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;
}
return z;
}
Gnosis example:
/* Derived from Gnosis code base */
/* https://github.com/gnosis/conditional-tokens-contracts/blob/master/contracts/CTHelpers.sol */
function sqrtGnosis(uint x) public pure returns (uint y) {
uint p = 21888242871839275222246405745257275088696311157297823662689037894645226208583;
// solium-disable-next-line security/no-inline-assembly
assembly {
// add chain generated via https://crypto.stackexchange.com/q/27179/71252
// and transformed to the following program:
// x=1; y=x+x; z=y+y; z=z+z; y=y+z; x=x+y; y=y+x; z=y+y; t=z+z; t=z+t; t=t+t;
// t=t+t; z=z+t; x=x+z; z=x+x; z=z+z; y=y+z; z=y+y; z=z+z; z=z+z; z=y+z; x=x+z;
// z=x+x; z=z+z; z=z+z; z=x+z; y=y+z; x=x+y; z=x+x; z=z+z; y=y+z; z=y+y; t=z+z;
// t=t+t; t=t+t; z=z+t; x=x+z; y=y+x; z=y+y; z=z+z; z=z+z; x=x+z; z=x+x; z=z+z;
// z=x+z; z=z+z; z=z+z; z=x+z; y=y+z; z=y+y; t=z+z; t=t+t; t=z+t; t=y+t; t=t+t;
// t=t+t; t=t+t; t=t+t; z=z+t; x=x+z; z=x+x; z=x+z; y=y+z; z=y+y; z=y+z; z=z+z;
// t=z+z; t=z+t; w=t+t; w=w+w; w=w+w; w=w+w; w=w+w; t=t+w; z=z+t; x=x+z; y=y+x;
// z=y+y; x=x+z; y=y+x; x=x+y; y=y+x; x=x+y; z=x+x; z=x+z; z=z+z; y=y+z; z=y+y;
// z=z+z; x=x+z; y=y+x; z=y+y; z=y+z; x=x+z; y=y+x; x=x+y; y=y+x; z=y+y; z=z+z;
// z=y+z; x=x+z; z=x+x; z=x+z; y=y+z; x=x+y; y=y+x; x=x+y; y=y+x; z=y+y; z=y+z;
// z=z+z; x=x+z; y=y+x; z=y+y; z=y+z; z=z+z; x=x+z; z=x+x; t=z+z; t=t+t; t=z+t;
// t=x+t; t=t+t; t=t+t; t=t+t; t=t+t; z=z+t; y=y+z; x=x+y; y=y+x; x=x+y; z=x+x;
// z=x+z; z=z+z; z=z+z; z=z+z; z=x+z; y=y+z; z=y+y; z=y+z; z=z+z; x=x+z; z=x+x;
// z=x+z; y=y+z; x=x+y; z=x+x; z=z+z; y=y+z; x=x+y; z=x+x; y=y+z; x=x+y; y=y+x;
// z=y+y; z=y+z; x=x+z; y=y+x; z=y+y; z=y+z; z=z+z; z=z+z; x=x+z; z=x+x; z=z+z;
// z=z+z; z=x+z; y=y+z; x=x+y; z=x+x; t=x+z; t=t+t; t=t+t; z=z+t; y=y+z; z=y+y;
// x=x+z; y=y+x; x=x+y; y=y+x; x=x+y; y=y+x; z=y+y; t=y+z; z=y+t; z=z+z; z=z+z;
// z=t+z; x=x+z; y=y+x; x=x+y; y=y+x; x=x+y; z=x+x; z=x+z; y=y+z; x=x+y; x=x+x;
// x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x;
// x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x;
// x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x;
// x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x;
// x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x;
// x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x;
// x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x;
// x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x;
// x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x;
// x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x;
// x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x; x=x+x;
// x=x+x; x=x+x; x=x+x; x=x+x; res=y+x
// res == (P + 1) // 4
y := mulmod(x, x, p)
{
let z := mulmod(y, y, p)
z := mulmod(z, z, p)
y := mulmod(y, z, p)
x := mulmod(x, y, p)
y := mulmod(y, x, p)
z := mulmod(y, y, p)
{
let t := mulmod(z, z, p)
t := mulmod(z, t, p)
t := mulmod(t, t, p)
t := mulmod(t, t, p)
z := mulmod(z, t, p)
x := mulmod(x, z, p)
z := mulmod(x, x, p)
z := mulmod(z, z, p)
y := mulmod(y, z, p)
z := mulmod(y, y, p)
z := mulmod(z, z, p)
z := mulmod(z, z, p)
z := mulmod(y, z, p)
x := mulmod(x, z, p)
z := mulmod(x, x, p)
z := mulmod(z, z, p)
z := mulmod(z, z, p)
z := mulmod(x, z, p)
y := mulmod(y, z, p)
x := mulmod(x, y, p)
z := mulmod(x, x, p)
z := mulmod(z, z, p)
y := mulmod(y, z, p)
z := mulmod(y, y, p)
t := mulmod(z, z, p)
t := mulmod(t, t, p)
t := mulmod(t, t, p)
z := mulmod(z, t, p)
x := mulmod(x, z, p)
y := mulmod(y, x, p)
z := mulmod(y, y, p)
z := mulmod(z, z, p)
z := mulmod(z, z, p)
x := mulmod(x, z, p)
z := mulmod(x, x, p)
z := mulmod(z, z, p)
z := mulmod(x, z, p)
z := mulmod(z, z, p)
z := mulmod(z, z, p)
z := mulmod(x, z, p)
y := mulmod(y, z, p)
z := mulmod(y, y, p)
t := mulmod(z, z, p)
t := mulmod(t, t, p)
t := mulmod(z, t, p)
t := mulmod(y, t, p)
t := mulmod(t, t, p)
t := mulmod(t, t, p)
t := mulmod(t, t, p)
t := mulmod(t, t, p)
z := mulmod(z, t, p)
x := mulmod(x, z, p)
z := mulmod(x, x, p)
z := mulmod(x, z, p)
y := mulmod(y, z, p)
z := mulmod(y, y, p)
z := mulmod(y, z, p)
z := mulmod(z, z, p)
t := mulmod(z, z, p)
t := mulmod(z, t, p)
{
let w := mulmod(t, t, p)
w := mulmod(w, w, p)
w := mulmod(w, w, p)
w := mulmod(w, w, p)
w := mulmod(w, w, p)
t := mulmod(t, w, p)
}
z := mulmod(z, t, p)
x := mulmod(x, z, p)
y := mulmod(y, x, p)
z := mulmod(y, y, p)
x := mulmod(x, z, p)
y := mulmod(y, x, p)
x := mulmod(x, y, p)
y := mulmod(y, x, p)
x := mulmod(x, y, p)
z := mulmod(x, x, p)
z := mulmod(x, z, p)
z := mulmod(z, z, p)
y := mulmod(y, z, p)
z := mulmod(y, y, p)
z := mulmod(z, z, p)
x := mulmod(x, z, p)
y := mulmod(y, x, p)
z := mulmod(y, y, p)
z := mulmod(y, z, p)
x := mulmod(x, z, p)
y := mulmod(y, x, p)
x := mulmod(x, y, p)
y := mulmod(y, x, p)
z := mulmod(y, y, p)
z := mulmod(z, z, p)
z := mulmod(y, z, p)
x := mulmod(x, z, p)
z := mulmod(x, x, p)
z := mulmod(x, z, p)
y := mulmod(y, z, p)
x := mulmod(x, y, p)
y := mulmod(y, x, p)
x := mulmod(x, y, p)
y := mulmod(y, x, p)
z := mulmod(y, y, p)
z := mulmod(y, z, p)
z := mulmod(z, z, p)
x := mulmod(x, z, p)
y := mulmod(y, x, p)
z := mulmod(y, y, p)
z := mulmod(y, z, p)
z := mulmod(z, z, p)
x := mulmod(x, z, p)
z := mulmod(x, x, p)
t := mulmod(z, z, p)
t := mulmod(t, t, p)
t := mulmod(z, t, p)
t := mulmod(x, t, p)
t := mulmod(t, t, p)
t := mulmod(t, t, p)
t := mulmod(t, t, p)
t := mulmod(t, t, p)
z := mulmod(z, t, p)
y := mulmod(y, z, p)
x := mulmod(x, y, p)
y := mulmod(y, x, p)
x := mulmod(x, y, p)
z := mulmod(x, x, p)
z := mulmod(x, z, p)
z := mulmod(z, z, p)
z := mulmod(z, z, p)
z := mulmod(z, z, p)
z := mulmod(x, z, p)
y := mulmod(y, z, p)
z := mulmod(y, y, p)
z := mulmod(y, z, p)
z := mulmod(z, z, p)
x := mulmod(x, z, p)
z := mulmod(x, x, p)
z := mulmod(x, z, p)
y := mulmod(y, z, p)
x := mulmod(x, y, p)
z := mulmod(x, x, p)
z := mulmod(z, z, p)
y := mulmod(y, z, p)
x := mulmod(x, y, p)
z := mulmod(x, x, p)
y := mulmod(y, z, p)
x := mulmod(x, y, p)
y := mulmod(y, x, p)
z := mulmod(y, y, p)
z := mulmod(y, z, p)
x := mulmod(x, z, p)
y := mulmod(y, x, p)
z := mulmod(y, y, p)
z := mulmod(y, z, p)
z := mulmod(z, z, p)
z := mulmod(z, z, p)
x := mulmod(x, z, p)
z := mulmod(x, x, p)
z := mulmod(z, z, p)
z := mulmod(z, z, p)
z := mulmod(x, z, p)
y := mulmod(y, z, p)
x := mulmod(x, y, p)
z := mulmod(x, x, p)
t := mulmod(x, z, p)
t := mulmod(t, t, p)
t := mulmod(t, t, p)
z := mulmod(z, t, p)
y := mulmod(y, z, p)
z := mulmod(y, y, p)
x := mulmod(x, z, p)
y := mulmod(y, x, p)
x := mulmod(x, y, p)
y := mulmod(y, x, p)
x := mulmod(x, y, p)
y := mulmod(y, x, p)
z := mulmod(y, y, p)
t := mulmod(y, z, p)
z := mulmod(y, t, p)
z := mulmod(z, z, p)
z := mulmod(z, z, p)
z := mulmod(t, z, p)
}
x := mulmod(x, z, p)
y := mulmod(y, x, p)
x := mulmod(x, y, p)
y := mulmod(y, x, p)
x := mulmod(x, y, p)
z := mulmod(x, x, p)
z := mulmod(x, z, p)
y := mulmod(y, z, p)
}
x := mulmod(x, y, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
x := mulmod(x, x, p)
y := mulmod(y, x, p)
}
}
