NEWTON

NEWTON

# Fixed Point pow operation error

8 months ago

80

views

0

I'm trying to make a FixedPoint cairo lib, but I'm having some trouble making a pow function.

It's inspired by this function

``````
function pow(
uint256 x,
uint256 y,
uint256 base
) internal pure returns (uint256 z) {
assembly {
switch x
case 0 {
switch y
case 0 {
// 0 ** 0 = 1
z := base
}
default {
// 0 ** y = 0
z := 0
}
}
default {
switch mod(y, 2)
case 0 {
// If y is even, store base in z for now.
z := base
}
default {
// If y is odd, store x in z for now.
z := x
}

// Shifting right by 1 is like dividing by 2.
let half := shr(1, base)

for {
// Shift y right by 1 before looping to halve it.
y := shr(1, y)
} y {
// Shift y right by 1 each iteration to halve it.
y := shr(1, y)
} {
// Revert immediately if x ** 2 would overflow.
// Equivalent to iszero(eq(div(xSquared, x), x)) here.
if shr(128, x) {
revert(0, 0)
}

// Store x squared.
let xSquared := mul(x, x)

// Round to the nearest number.

// Revert if xSquared + half overflowed.
if lt(xSquaredRound, xSquared) {
revert(0, 0)
}

// Set x to scaled xSquaredRound.
x := div(xSquaredRound, base)

// If n is even:
if mod(y, 2) {
// Compute z * x.
let zx := mul(z, x)

// If z * x overflowed:
if iszero(eq(div(zx, x), z)) {
// Revert if x is non-zero.
if iszero(iszero(x)) {
revert(0, 0)
}
}

// Round to the nearest number.

// Revert if zx + half overflowed.
if lt(zxRound, zx) {
revert(0, 0)
}

// Return properly scaled zxRound.
z := div(zxRound, base)
}
}
}
}
}``````

and I wrote this one in Cairo

``````    func pow{syscall_ptr: felt*, pedersen_ptr: HashBuiltin*, range_check_ptr: felt}(
x: Uint256,
n: Uint256,
baseUnit: Uint256
) -> (res: Uint256) {
alloc_locals;

let (xIsZero) = uint256_eq(x, Uint256(low=0, high=0));

if(xIsZero == TRUE) {
let (nIsZero) = uint256_eq(n, Uint256(low=0, high=0));
if(nIsZero == TRUE) {
// 0**0 = 1
return (res=Uint256(low=1, high=0));
}
// 0**n = 0
return (res=Uint256(low=0, high=0));
}

let (nHalf, nHalfRem) = uint256_unsigned_div_rem(n, Uint256(low=2, high=0));
let (nIsEven) = uint256_eq(nHalfRem, Uint256(low=0, high=0));
let (z) = _assignZIf(nIsEven, baseUnit, x);

let (baseUnitHalf, baseUnitHalfRem) = uint256_unsigned_div_rem(baseUnit, Uint256(low=2, high=0));

let (res) = pow_loop(x, nHalf, z, baseUnit, baseUnitHalf);

return (res=res);
}

func pow_loop{syscall_ptr: felt*, pedersen_ptr: HashBuiltin*, range_check_ptr: felt}(
x: Uint256,
n: Uint256,
z: Uint256,
baseUnit: Uint256,
baseUnitHalf: Uint256
) -> (res: Uint256) {
alloc_locals;

let (n_LteOne) = uint256_le(n, Uint256(low=1, high=0));

if(n_LteOne == TRUE) {
return (res=z);
}

let (xx, xxOverflow) = uint256_mul(x, x);
assert xxOverflow.low = 0;
assert xxOverflow.high = 0;

let (xxRound, xSquaredRoundCarry) = uint256_add(xx, baseUnitHalf);
let (roundingOverflowed) = uint256_lt(xxRound, xx);
assert roundingOverflowed = FALSE;

let (temp_x, temp_x_rem) = uint256_unsigned_div_rem(xxRound, baseUnit);

let (nHalf, nHalfRem) = uint256_unsigned_div_rem(n, Uint256(low=2, high=0));
let (nHalfIsEven) = uint256_eq(nHalfRem, Uint256(low=0, high=0));
if(nHalfIsEven ==  TRUE) {
let (zx, zxOverflow) = uint256_mul(z, x);
assert zxOverflow.low = 0;
assert zxOverflow.high = 0;

let (shouldBeZ, shouldBeZRem) = uint256_unsigned_div_rem(zx, x);
let (zxNotOverflowed) = uint256_eq(shouldBeZ, z);
assert zxNotOverflowed = TRUE;

let (zxRound, zxRoundCarry) = uint256_add(zx, baseUnitHalf);
let (zxRoundOverflowed) = uint256_lt(zxRound, zx);
assert zxRoundOverflowed = FALSE;

let (temp_z, temp_zRem) = uint256_unsigned_div_rem(zxRound, baseUnit);
return pow_loop(x=temp_x, n=nHalf, z=temp_z, baseUnit=baseUnit, baseUnitHalf=baseUnitHalf);
} else {
return pow_loop(x=temp_x, n=nHalf, z=z, baseUnit=baseUnit, baseUnitHalf=baseUnitHalf);
}
}

func _assignZIf{syscall_ptr: felt*, pedersen_ptr: HashBuiltin*, range_check_ptr: felt}(
nIsEven: felt,
baseUnit: Uint256,
x: Uint256
) -> (res: Uint256) {
if(nIsEven == TRUE) {
return (res=baseUnit);
}
return (res=x);
}``````

The thing is that I don't get the same results.

Here are some example of my results compared to the solidity function

• pow(1, 3, 10^18): Cairo = 1 / Solidity = 0

• pow(10^18, 5, 10^18): Cairo = 4000000000000000000 (4x10^18) / Solidity = 32000000000000000000 (32x10^18)

• pow(10^19, 5, 10^18): Cairo = 100000000000000000000 (10^20) / Solidity = 100000000000000000000000 (10^23)

I can't see what I'm doing wrong in my code

cairomathfixed pointsolidity

0x0800...F0606a

8 months ago

0

I'm not sure what you meant with the first solidity comment but for the second, yes this check wasn't correct, it was `n > 0`.

Meanwhile, the solidity commented code was missleading as well on the very last `if` statement, saying `// if n is even` while in fact the real condition was `if n is not even`.

I've been able to have consistent results after correcting the conditions

``````    func fpow{syscall_ptr: felt*, pedersen_ptr: HashBuiltin*, range_check_ptr: felt}(
x: Uint256,
n: Uint256,
baseUnit: Uint256
) -> (res: Uint256) {
alloc_locals;

let (xIsZero) = uint256_eq(x, Uint256(low=0, high=0));

if(xIsZero == TRUE) {
let (nIsZero) = uint256_eq(n, Uint256(low=0, high=0));
if(nIsZero == TRUE) {
// 0**0 = 1
return (res=Uint256(low=1, high=0));
}
// 0**n = 0
return (res=Uint256(low=0, high=0));
}

let (nHalf, nHalfRem) = uint256_unsigned_div_rem(n, Uint256(low=2, high=0));
let (nIsEven) = uint256_eq(nHalfRem, Uint256(low=0, high=0));
let (z) = FixedPointMathLib._assignZIf(nIsEven, baseUnit, x);

let (baseUnitHalf, baseUnitHalfRem) = uint256_unsigned_div_rem(baseUnit, Uint256(low=2, high=0));

let (res) = fpow_loop(x, nHalf, z, baseUnit, baseUnitHalf);

return (res=res);
}

func fpow_loop{syscall_ptr: felt*, pedersen_ptr: HashBuiltin*, range_check_ptr: felt}(
x: Uint256,
n: Uint256,
z: Uint256,
baseUnit: Uint256,
baseUnitHalf: Uint256
) -> (res: Uint256) {
alloc_locals;

let (n_LteZero) = uint256_le(n, Uint256(low=0, high=0));
if(n_LteZero == TRUE) {
return (res=z);
}

let (xx, xxOverflow) = uint256_mul(x, x);
assert xxOverflow.low = 0;
assert xxOverflow.high = 0;

let (xxRound, xSquaredRoundCarry) = uint256_add(xx, baseUnitHalf);
let (roundingOverflowed) = uint256_lt(xxRound, xx);
assert roundingOverflowed = FALSE;

let (temp_x, temp_x_rem) = uint256_unsigned_div_rem(xxRound, baseUnit);

let (nHalf, nHalfRem) = uint256_unsigned_div_rem(n, Uint256(low=2, high=0));
let (nHalfIsEven) = uint256_eq(nHalfRem, Uint256(low=0, high=0));
if(nHalfIsEven == TRUE) {
return fpow_loop(x=temp_x, n=nHalf, z=z, baseUnit=baseUnit, baseUnitHalf=baseUnitHalf);
}

let (zx, zxOverflow) = uint256_mul(z, temp_x);
assert zxOverflow.low = 0;
assert zxOverflow.high = 0;

let (shouldBeZ, shouldBeZRem) = uint256_unsigned_div_rem(zx, temp_x);
let (zxNotOverflowed) = uint256_eq(shouldBeZ, z);
assert zxNotOverflowed = TRUE;

let (zxRound, zxRoundCarry) = uint256_add(zx, baseUnitHalf);
let (zxRoundOverflowed) = uint256_lt(zxRound, zx);
assert zxRoundOverflowed = FALSE;

let (temp_z, temp_zRem) = uint256_unsigned_div_rem(zxRound, baseUnit);

return fpow_loop(x=temp_x, n=nHalf, z=temp_z, baseUnit=baseUnit, baseUnitHalf=baseUnitHalf);
}``````

0x0800...F0606a

8 months ago

0

Algorithms are just different and you check unit overflow on different stages of the check.

In solidity, you have a mistake `pow(1, 3, *) == 0`:

``````let zx := mul(z, x) // x is zero; zx is also zero
...
z := div(zxRound, base) //zxRound = 0 + half; base = half // 2, means z = 0
``````

in the second example straight after the first iteration

``````let (n_LteOne) = uint256_le(n, Uint256(low=1, high=0));

if(n_LteOne == TRUE) {
return (res=z);
}
``````

returns `res=1`