NEWTON
Asked
3 months ago
68
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. let xSquaredRound := add(xSquared, half) // 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. let zxRound := add(zx, half) // 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
0x0800...F0606a
asked
3 months ago
0
Accepted answer
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
answered
3 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
vargastartup
answered
3 months ago
Cairo: How to reassign Uint256 in a conditional
Cairo error "Expected expression of type 'starkware.cairo.common.uint256.Uint256' to have an address."
Cairo Error: 'range_check_ptr' cannot be used as an implicit return value. Consider using a 'with' statement.
How do you optimize gas in Cairo with Uint256/felt?
Is uint256 math operators like uint256_le safe? Why do I need to use uint256_check?
How can I send a Uint256 amount of ERC20 tokens from L1 to starknet? And how should I build my payload for "sendMessageToL2" to match the Uint256 format of Cairo?
What is the inefficiency in this cairo code using alloc_locals
Is there anything wrong with the testnet?
How to generate a proof for a Cairo program and verify it?[StackOverflow]
What are the projects on starknet that plan to do the domain .stark?
How long does starkgate bridge process?
Cairo: Cannot unpack error
Infinite Recursion Error on Cairo Compile
How to convert tokens on starknet? Any DEXs AMMs?