NEWTON

NEWTON


Popular tags

    Fixed Point pow operation error

    Asked

    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. 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

      cairomathfixed pointsolidity

    0x0800...F0606a

    asked

    8 months ago


    2 answers

    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

    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

    Your answer

    Related

    NEWTON

    NEWTON