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

Surprising behavior when right-shifting a negative BigInt #1

Closed
cuviper opened this issue Dec 19, 2017 · 4 comments
Closed

Surprising behavior when right-shifting a negative BigInt #1

cuviper opened this issue Dec 19, 2017 · 4 comments

Comments

@cuviper
Copy link
Member

cuviper commented Dec 19, 2017

From @mhogrefe on December 9, 2017 19:25

Right-shifting an primitive integer in Rust (and most other languages AFAIK) is equivalent to dividing by a power of 2 and rounding towards -∞. But right-shifting a BigInt rounds towards 0 instead.

You can see the difference by pasting the following into https://play.rust-lang.org/:

extern crate num;

fn main() {
    println!("-1 >> 1 == {} (primitive)", -1 >> 1);
    println!("-1 >> 1 == {} (BigInt)", num::BigInt::from(-1) >> 1);
}

This prints

-1 >> 1 == -1 (primitive)
-1 >> 1 == 0 (BigInt)

If this behavior is intentional it should probably be documented and unit-tested.

Copied from original issue: rust-num/num#347

@cuviper
Copy link
Member Author

cuviper commented Dec 19, 2017

That's interesting. This behavior is neither an arithmetic nor logical right shift, but sort of a weird hybrid. I don't think this was intentional, just a casual side effect of shifting the internal BigUint while preserving the sign.

I worry slightly that changing this would be a breaking change, but I think we can call it just a bug fix. The current behavior is unprecedented in other languages AFAIK, and matching the primitive behavior would be much more useful.

@cuviper
Copy link
Member Author

cuviper commented Dec 19, 2017

From @mhogrefe on December 9, 2017 23:0

The current behavior is equivalent to GMP's mpz_tdiv_q_2exp, so there is presumably some demand for this behavior (The more common behavior corresponds to mpz_fdiv_q_2exp). Is there a reliable way to search Github and see if there'd be any breakages?

@cuviper
Copy link
Member Author

cuviper commented Dec 19, 2017

Well sure, GMP implements every conceivable variation. :)

I don't know a way to search for this. @rust-lang has a "crater" tool that compiles every published crate and some more on GitHub, but this isn't generally available for use. I suppose we could just poll the users forum and /r/rust.

Generally speaking though, I think we want to match primitive operators in all aspects (except overflow). That's applying the principle of least surprise, and we could implement alternate forms as other methods if we want to generalize choices.

@cuviper
Copy link
Member Author

cuviper commented Dec 19, 2017

From @tspiteri on December 12, 2017 12:28

GMP does have a definition #define mpz_div_2exp mpz_fdiv_q_2exp in gmp.h. It is undocumented and I think it's only there for some compatibility with GMP 1, back when that was the only available variation.

@cuviper cuviper added this to the num-bigint-0.2 milestone Dec 19, 2017
@cuviper cuviper added the bug label Dec 19, 2017
bors bot added a commit that referenced this issue Feb 24, 2018
8: Make Shr for negative BigInt round down, like primitives do r=cuviper a=cuviper

Primitive integers always round down when shifting right, but `BigInt`
was effectively rounding toward zero, because it just kept its sign and
used the `BigUint` magnitude rounded down (always toward zero).

Now we adjust the result of shifting negative values, and explicitly
test that it matches the result for primitive integers.

Fixes #1.
@bors bors bot closed this as completed in #8 Feb 24, 2018
Kayryu pushed a commit to sgx-test/num-bigint-sgx that referenced this issue Dec 3, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant