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

Negative number support for big_int bit manipulations #5017

Closed
vicuna opened this issue Apr 6, 2010 · 1 comment
Closed

Negative number support for big_int bit manipulations #5017

vicuna opened this issue Apr 6, 2010 · 1 comment
Assignees

Comments

@vicuna
Copy link

vicuna commented Apr 6, 2010

Original bug ID: 5017
Reporter: yoiwa
Assigned to: @xavierleroy
Status: closed (set by @xavierleroy on 2012-03-24T14:01:03Z)
Resolution: fixed
Priority: normal
Severity: feature
Fixed in version: 3.12.0+dev
Category: ~DO NOT USE (was: OCaml general)
Monitored by: yoiwa

Bug description

The issue #4641 has added a basic bit manipulation functions to big_int library; very nice.
However, I have a concern about handling of the negative number on those, especially for shift operations.

I feel that the current behavior of the shift operations for negative numbers are confusing; it seems to be better consistent with x * (2 ** y) and
x / (2 ** y), or two's complement.
I wish to have those implemented those in consistent with two's complement
(or at least reject them).

Also, other bit manipulation functions for negative numbers can also be
implemented in 2's complement.

Additional information

I have an implementation using public interfaces of Nat and Big_int;
it is available at < http://www.oiwa.jp/~yutaka/temp/big_int2.ml >.
It may better be revised using internal functions
(which will reduce copying of Nat's);
If required, I will implement/submit a revision.

@vicuna
Copy link
Author

vicuna commented Apr 29, 2010

Comment author: @xavierleroy

After thinking about it, I agree that it is better for right shifts on negative numbers to behave like Euclidean division by 2^n, i.e. round towards minus infinity. Adjusted the behavior of shift_right_big_int accordingly. The old behavior is available as function shift_right_towards_zero_big_int. All this will be in release 3.12.0.

Concerning and, or and xor on negative numbers, an efficient implementation that minimizes allocation of temporary nats is quite complex indeed, so I'd rather not do it immediately. I'll keep this in mind for later.

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

2 participants