dev: optimize bitshifts by using a lookup table for powers of two

[enitrat]

for the powers of two up to 256, we can define a lookup table and use that lookup table to execute bitshift operations, instead of calling the expensive cairo function pow.

• If p <=255, use the lookup table POW_2
• if p>255, fallback on using pow.

Hint: In a generic context, you can get the value 255 of type T by doing BitSize::<u256>::bits() - One::<T>::one() - make sure you're using the right types for that.

https://github.com/kkrt-labs/kakarot-ssj/blob/b1f7f8c13be38edc081f0738c188561240c098b4/crates/utils/src/math.cairo#L195-L212

https://github.com/kkrt-labs/kakarot-ssj/blob/b1f7f8c13be38edc081f0738c188561240c098b4/crates/utils/src/math.cairo#L242-L255

[manlikeHB]

I am applying to this issue via OnlyDust platform.

My background and how it can be leveraged

Hi, I am Cairo dev with lots of experience contributing to Cairo projects, my OD profile is a witness to this. This feat is right within my comfort zone.

I have had experience working on projects were bitshift operations were implemented I can use those as a reference for implementing this.

How I plan on tackling this issue

After implementing this, I will write a robust unit test and ensure all test case are covered and the feat behaves as expected.

[MPSxDev]

I am applying to this issue via OnlyDust platform.

My background and how it can be leveraged

Hello, I am Manuel, a process engineer and web3 developer. I have participated in Starknet Bootcamps, ETHGlobal and am an Elite winner of Speedrunstark. I have a high capacity to solve problems. I am a member of the DojoCoding community. I hope this issue is assigned to me. I am available to work immediately to achieve what is required in the shortest time possible.

How I plan on tackling this issue

To address the requirements of the issue, I will:

1. Create a lookup table POW_2 containing powers of two up to 256.
2. Implement logic to check if the exponent p is less than or equal to 255:
   • If p <= 255, use the corresponding value from the POW_2 lookup table for optimization.
   • If p > 255, fallback to using the pow function.
3. Ensure that the implementation utilizes the correct types by calculating the value 255 with BitSize::<u256>::bits() - One::<T>::one().
4. Test the new implementation to verify correctness and performance improvements.

[guha-rahul]

I am applying to this issue via OnlyDust platform.

My background and how it can be leveraged

I have been a rust and zk dev before and i have implemented lookup tables for zk cryptography . I think that will help me in this issue

How I plan on tackling this issue

1. Read the codebase 2.implement the lookup table
2. replace the expensive cairo math with these tables
3. Ask questions if i am stuck anywhere

[augustin-v]

I am applying to this issue via OnlyDust platform.

My background and how it can be leveraged

I am a newcomer in the blockchain dev world, and I'd really like to be given a chance to complete my first OnlyDust contribution. I have experience with Node Guardians's brainfvck VM in Cairo, where I used bitshift operations a lot, as well as the cairo-profiler. Thank you

How I plan on tackling this issue

I would create a look up cable to store powers of two from w~0 to 2~255 in an array pow_2. Then check the value of p. And of course communicate if I encounter any problem

[saimeunt]

I am applying to this issue via OnlyDust platform.

My background and how it can be leveraged

I have some experience in Cairo, mostly porting Solidity ERCs to Cairo: https://github.com/carbonable-labs/cairo-erc-7496 https://github.com/carbonable-labs/cairo-erc-7498

How I plan on tackling this issue

I will carefully implement the required optimization by leveraging a lookup table for powers of 2 <= 255. I will make sure to follow the hint given to generically obtain the value 255 from any type using bitsize introspection.

[onlydustapp[bot]]

The maintainer enitrat has assigned augustin-v to this issue via OnlyDust Platform. Good luck!