feat: Lookup tables and type-specific optimizations

[Th0rgal]

• [x] resolves #268
• [x] follows contribution guide
• [x] code change includes tests

This PR addresses the optimization tasks outlined in issue #[268]. The goal is to reduce computational steps in raito through the use of lookup tables and type-specific optimizations.

Changes implemented:

1. Fast pow2 using lookup table
2. Fast shr for u128 (Note: This was first implemented for u128 but we actually only needed u64)
3. Optimize bits_to_target with shr_u64 and early returns
4. Simplify pow2 for u64 and optimize next_power_of_two

Performance improvements:

For the next_power_of_two function:

• Before: test utils::numeric::tests::test_u64_next_power_of_two ... ok (gas usage est.: 1984226)
• After: test utils::numeric::tests::test_u64_next_power_of_two ... ok (gas usage est.: 417386)

This represents a significant reduction in gas usage of approximately 80% for next_power_of_two, it also improves the computation of the target from bits (tricks explained in comments) which should speedup validate_bits and thus the whole validation pipeline.

[vercel[bot]]

The latest updates on your projects. Learn more about Vercel for Git ↗︎

Name	Status	Preview	Comments	Updated (UTC)
raito	✅ Ready (Inspect)	Visit Preview	💬 Add feedback	Oct 17, 2024 7:45am

[m-kus]

Thank you! We can probably remove shr/shl/fast_pow since they are no longer in use, wdyt @maciejka ?

[maciejka]

Thank you! We can probably remove shr/shl/fast_pow since they are no longer in use, wdyt @maciejka ?

Agree.

[Th0rgal]

Thank you! We can probably remove shr/shl/fast_pow since they are no longer in use, wdyt @maciejka ?

Agree.

Will do for shr. For shl I didn't update it yet (I need to think about the best way to do it because it is used to compute the target). I will probably make another pr specifically for bits_to_target (I already have a few ideas to optimize it), and remove shl and fast_pow if possible.