Your Fibonacci neighbor Competition: Showcasing the Winning Solutions

From January 24th - Feb. 7th, AgorApp heald the Fibonacci Neighbor competition. The challenge you were be given an integer and you needed to find the closest Fibonacci number to it.

The goal of the competition was to see who could optimize their solution with the least amount of gas.

The top winners were…

Top 3 solutions

1st Place: rskek9254

Gas: 21635

pragma solidity 0.8.10;

contract FibonacciNeighbor {
    function run(uint80 _arg) external pure returns(uint256) {
        assembly {
            if lt(2178308, _arg) {
                mstore(returndatasize(), 3524578)
                return(returndatasize(), msize())
            }

            if iszero(_arg) {
                return(returndatasize(), 0x20)
            }

            let a := 1
            let b := a
            let t := add(a, b)

            a := b
            b := t
            t := add(a, b)



            if lt(_arg, t) {
                if eq(b, _arg) {
                    // a 21
                    // b 34
                    // t 55
                    // arg 34
                    if lt(sub(t, _arg), sub(_arg, a)) {
                        mstore(returndatasize(), t)
                        return(returndatasize(), msize())
                    }

                    mstore(returndatasize(), a)
                    return(returndatasize(), msize())
                }

                // a 13
                // b 21
                // t 34
                // arg 33

                if lt(sub(t, _arg), sub(_arg, b)) {
                    mstore(returndatasize(), t)
                    return(returndatasize(), msize())
                }

                mstore(returndatasize(), b)
                return(returndatasize(), msize())
            }

            // -------// -------// -------// -------// -------// -------// -------// -------// -------// -------// -------// -------// -------// -------// -------// -------// -------// -------// -------// -------// -------// -------// -------// -------

            a := b
            b := t
            t := add(a, b)

            if lt(_arg, t) {
                if eq(b, _arg) {
                    // a 21
                    // b 34
                    // t 55
                    // arg 34
                    if lt(sub(t, _arg), sub(_arg, a)) {
                        mstore(returndatasize(), t)
                        return(returndatasize(), msize())
                    }

                    mstore(returndatasize(), a)
                    return(returndatasize(), msize())
                }

                // a 13
                // b 21
                // t 34
                // arg 33

                if lt(sub(t, _arg), sub(_arg, b)) {
                    mstore(returndatasize(), t)
                    return(returndatasize(), msize())
                }

                mstore(returndatasize(), b)
                return(returndatasize(), msize())
            }
            a := b
            b := t
            t := add(a, b)


... (1,421 lines left)

2nd Place: LStan

Gas: 21644

pragma solidity 0.8.10;

contract FibonacciNeighbor {
  // You can add more state variables here

  function run(uint256 _arg) external pure returns(uint256) {
    assembly {

      if gt(_arg, 2851443) {
        mstore(0, 3524578)
        return(0, 0x20)
      }

      if gt(_arg, 103209) {
        mstore(0, 121393)
        return(0, 0x20)
      }

      if gt(_arg, 8855) {
        mstore(0, 10946)
        return(0, 0x20)
      }

      if gt(_arg, 17) {
        mstore(0, 21)
        return(0, 0x20)
      }

      mstore(0x00, mul(iszero(iszero(_arg)), 13))
      return(returndatasize(), 0x20)
    }
  }

  // You can add more functions here
}

3rd Place: Zac369

Gas: 21700

pragma solidity 0.8.10;

contract FibonacciNeighbor {
  // You can add more state variables here

  function run(uint256 _arg) external pure returns(uint256) {
    assembly {
      if iszero(sub(_arg, 17)) {
        mstore(returndatasize(), 13)
        return(returndatasize(), 0x20)
      }

      if iszero(sub(_arg, 34)) {
        mstore(returndatasize(), 21)
        return(returndatasize(), 0x20)
      }

      if iszero(sub(_arg, 4000000)) {
        mstore(returndatasize(), 3524578)
        return(returndatasize(), 0x20)
      }

      mstore(returndatasize(), mul(iszero(iszero(_arg)), 121393))
      return(returndatasize(), 0x20)
    }
  }

  // You can add more functions here
}

Thanks for all who participated in the challenge!

Lessons Learned

It turns out that this particular exercise is highly susceptible to being solved by hardcoding a solution via a bunch of if branches that return the expected number.

The reason for this is that there are surprisingly few numbers in the Fibonacci sequence. We are testing numbers up to 4 million, so how many Fibonacci numbers are there between 0 and 4 million? It turns out there are only 33. Therefore, to pass our tests, it’s enough to provide 33 if branches that return the expected answer.

Enjoy your prizes. Next time, it won't be this easy 🙂

Want to learn more? Follow our progress!

For the latest news and developments, including course & challenge launches, stay tuned. Join the AgorApp Discord and communicate with the team or follow us on Telegram, Twitter or Linkedin.