Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Further optimize the "pow" and "powu" functions #3

Open
PaulRBerg opened this issue Apr 7, 2021 · 0 comments
Open

Further optimize the "pow" and "powu" functions #3

PaulRBerg opened this issue Apr 7, 2021 · 0 comments
Labels
effort: high Large or difficult task. priority: 3 Nice-to-have. Willing to ship without this. type: perf Change that improves performance. work: complicated Sense-analyze-respond. The relationship between cause and effect requires analysis or expertise.

Comments

@PaulRBerg
Copy link
Owner

PaulRBerg commented Apr 7, 2021

A good ~350 gas can be saved in the powu function by implementing the optimizations in ABDKMath64x64. I haven't yet fully grokked how the optimizations work, but this is what I understand so far:

  • Use an intermediary 64.127-bit format for the absX var
  • Discriminate between the cases when x <= SCALE and x > SCALE, since in the former case overflows are not possible in the intermediary results
  • When x <= UNIT, batch the checks for 2^0, 2^1, 2^2 and 2^3 in the while block, then divide by 2^4
  • When x >= UNIT, progressively check if x is lower than 2^32, then 2^48, then 2^56, then 2^60, then 2^62 and finally 2^63, storing the findings in an absXShift var
@PaulRBerg PaulRBerg changed the title Further optimise the "pow" function Further optimise the "pow" and "powu" functions Jun 14, 2021
@PaulRBerg PaulRBerg changed the title Further optimise the "pow" and "powu" functions [prb-math] Further optimise the "pow" and "powu" functions Sep 29, 2021
@PaulRBerg PaulRBerg changed the title [prb-math] Further optimise the "pow" and "powu" functions Further optimize the "pow" and "powu" functions Oct 20, 2021
@PaulRBerg PaulRBerg added effort: high Large or difficult task. type: perf Change that improves performance. work: complicated Sense-analyze-respond. The relationship between cause and effect requires analysis or expertise. priority: 3 Nice-to-have. Willing to ship without this. and removed enhancement labels Jan 1, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
effort: high Large or difficult task. priority: 3 Nice-to-have. Willing to ship without this. type: perf Change that improves performance. work: complicated Sense-analyze-respond. The relationship between cause and effect requires analysis or expertise.
Projects
None yet
Development

No branches or pull requests

1 participant