keep-starknet-strange / alexandria

Community maintained Cairo libraries and set of well maintained, optimised and secure components.

MIT License

231 stars 100 forks source link

feat: Implement fast interpolation using binary search closest element #285

Closed tekkac closed 6 months ago

tekkac commented 6 months ago

Feature Request

Describe the Feature Request

implement a gas efficient implementation of interpolation
implement binary search for closest element in sorted array
fix interpolation error in the case of Interpolation::ConstantLeft
additional tests are provided

Describe Preferred Solution

Add a binary search version of interpolation instead of existing linear algorithm

Describe Alternatives

Replace the existing interpolation with the fast method. Not chosen for compatibility with existing contracts.

Related Code

https://github.com/keep-starknet-strange/alexandria/blob/c1a604eaba40b026c2b477a9b293e40244432e0a/src/numeric/src/interpolate.cairo#L58

Additional Context

PR is provided

If the feature request is approved, would you be willing to submit a PR? (Help can be provided if you need assistance submitting a PR)

[x] Yes
[ ] No