Add Average trait with integer average computation #31
Merged
bors[bot] merged 8 commits intorust-num:masterfrom Mar 7, 2020
althonos:master
Merged
Add Average trait with integer average computation #31bors[bot] merged 8 commits intorust-num:masterfrom althonos:master
bors[bot] merged 8 commits intorust-num:masterfrom
althonos:master
Conversation
Contributor
Author
|
cc @cuviper, I had to reopen a PR, but in the meantime I fixed the review comments from the previous one. |
Member
|
Hi @althonos, this does look nice, thank you! More tests are always appreciated, if you're still planning to do that. The benchmarks might want to do a validation step of their expected results too, like the roots benches do -- the CI script runs |
Contributor
Author
|
Hi @cuviper, I added a validation test for the benchmarks (at least for the methods that should be exact) plus proper unit tests, hopefully this is enough for now. |
Member
|
Looks great! I just added a few more boundary cases to the doc examples. bors r+ |
Contributor
Build succeeded |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
This is actually a copy of #20, I had to reopen a PR to address the fixes as I deleted the repository in between
Hi there !
This PR adds a new trait Average with two methods Average.average_ceil and Average.average_floor that uses bitwise operations to compute the average of two integers without overflowing. Reference is here, but this is probably known to people thanks to the Hacker's Delight.
Basically:
⌊(x+y)/2⌋ = (x&y) + ((x^y) >> 1)
⌈(x+y)/2⌉ = (x|y) - ((x^y) >> 1)
It comes with a blanket implementation for all Integer implementors that are closed under the -+|&^>> operators; in particular, this blanket implementation works for the BigInt and BigUint structs.
In terms of performance, this implementation is about 1.5 times faster than a naive implementation that checks for overflow, and as fast as an implementation that doesn't (i.e. (x+y)/2).
I'll add more tests for the std primitives, please do tell me if anything else needs to be changed.