Add Average trait with integer average computation#20
Add Average trait with integer average computation#20althonos wants to merge 4 commits intorust-num:masterfrom althonos:master
Conversation
|
bors retry |
|
🔒 Permission denied Existing reviewers: click here to make althonos a reviewer |
cuviper
left a comment
There was a problem hiding this comment.
Hi, sorry for the late review. This is a really neat trick!
Is there a reason you chose to make it a new trait, rather than adding to Integer? Especially since you provide a blanket implementation -- you can add the same on Integer, just with specific where clauses added to those new methods. That also makes it possible for someone to override with an even better version for their own type.
A few more tests would be nice to increase the floor/ceil coverage, like averaging a small negative with a big positive, and vice versa.
|
Hi !
The blanket implementation needs I'll fix the other remarks this week. |
|
Closing in favour of #31. |
31: Add Average trait with integer average computation r=cuviper a=althonos *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. Co-authored-by: Martin Larralde <martin.larralde@ens-paris-saclay.fr> Co-authored-by: Josh Stone <cuviper@gmail.com>
Hi there !
This PR adds a new trait
Averagewith two methodsAverage.average_ceilandAverage.average_floorthat 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:
It comes with a blanket implementation for all
Integerimplementors that are closed under the-+|&^>>operators; in particular, this blanket implementation works for theBigIntandBigUintstructs.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
stdprimitives, please do tell me if anything else needs to be changed.