0005017: Negative number support for big_int bit manipulations

View Issue Details [ Jump to Notes ]

[ Issue History ] [ Print ]

Project

Category

View Status

Date Submitted

Last Update

0005017

OCaml

OCaml general

public

2010-04-06 04:24

2012-03-24 15:01

Reporter

yoiwa

Assigned To

xleroy

Priority

normal

Severity

feature

Reproducibility

always

Status

closed

Resolution

fixed

Platform

OS Version

Product Version

Target Version

Fixed in Version

3.12.0+dev

Summary

0005017: Negative number support for big_int bit manipulations

Description

The issue 0004641 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.

Tags

No tags attached.

Attached Files

Relationships

Notes
(0005413) xleroy (administrator) 2010-04-29 16:03	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.

Issue History
Date Modified	Username	Field	Change
2010-04-06 04:24	yoiwa	New Issue
2010-04-29 16:03	xleroy	Note Added: 0005413
2010-04-29 16:03	xleroy	Status	new => resolved
2010-04-29 16:03	xleroy	Resolution	open => fixed
2010-04-29 16:03	xleroy	Fixed in Version	=> 3.12.0+dev
2010-04-29 17:11	xleroy	Assigned To	=> xleroy
2012-03-24 15:01	xleroy	Status	resolved => closed