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

[augustin-v]

Pull Request type

Please check the type of change your PR introduces:

• [ ] Bugfix
• [ ] Feature
• [ ] Code style update (formatting, renaming)
• [ ] Refactoring (no functional changes, no API changes)
• [ ] Build-related changes
• [ ] Documentation content changes
• [✅ ] Other (please describe): dev

What is the current behavior?

The bit shifting operations in the existing implementation are not optimized, leading to potential inefficiencies.

Resolves: #905

What is the new behavior?

• Introduced a new implementation for bit shifting using a lookup table for powers of two.
• Enhanced efficiency by minimizing multiplications and leveraging early returns for large shift values.

Does this introduce a breaking change?

• [ ] Yes
• [✅ ] No

---

This change is 

[enitrat]

The easiest way would be to use python to generate cairo code, like so:

def generate_powers_of_two():
    print("pub const POW_2_256: [")
    print("    u256")
    print("    ; 256] = [")

    for i in range(256):
        value = 2 ** i
        hex_value = f"0x{value:x}"
        print(f"    {hex_value},")

    print("];")

if __name__ == "__main__":
    generate_powers_of_two()

[augustin-v]

Thank you for the review, I'll add a new constant as instructed and try profiling as well!

[enitrat]

hi @augustin-v it seems that the changes brought in scope of these PR highlight a memory-management related issue in Cairo Native which crashes our CI runner, thus I will have to keep it open until it is fixed

[augustin-v]

Hi @enitrat, understood. Thank you for the update, and please let me know if there's anything I can do to assist with resolving the issue

[enitrat]

hey @augustin-v i ran some profiling on test_execute_from_outside_eip1559 - which is just an empty execution, so it only performs validation steps:

Before:

After:

It's nearly 10x better :)

[augustin-v]

@enitrat wow it improved much more than I thought it would, bitshift operations looking good