[BUG][SEMANTIC] semantics of Integer bit ops, e.g. >>bitShift: [was: Re: Large integers problem...]

Stephan Rudlof sr at evolgo.de
Tue Jun 6 20:51:09 UTC 2000


Dear Squeakers,

the LargeIntegers problem is mainly an Integer semantics problem and
goes much deeper. The LargeIntegers module just implements the current
semantic for LargeIntegers.

'Numerical' Squeakers: Please take some time and read this straining
mail, because the problem lays in the fundaments of Squeak!


While thinking about defining >>highBit for negative Integers, too -
e.g. by returning #infinite - I've found a nasty semantic problem.


The semantics of Integer>>bitShift: (used for LargeIntegers) differs
from the one of SmallInteger>>bitShift: :

For left shifts the semantics are the same

((Integer new: 1 neg: true) at: 1 put: 5; yourself) bitShift: 1. -10
"LargeNegativeInteger"
-5 bitShift: 1. -10

*but* for right shifts *not*:

((Integer new: 1 neg: true) at: 1 put: 5; yourself) bitShift: -1. -2
-5 bitShift: -1. -3

Another example (because you could argue, the above is unsafe since not
#normalize'd LargeIntegers):

(2 << 32) negated bitShift: -1 -4294967296	"large"
(2 << 32 + 1) negated bitShift: -1  -4294967296
(2 << 16) negated bitShift: -1 -65536		"small"
(2 << 16 + 1) negated bitShift: -1 -65537	"!"

The reasons are:
- LargeNegativeIntegers: they are treated always as positive values and
the sign is applied to the result;
- negative SmallIntegers
	- left shift: same as for LargeNegativeIntegers,
	- right shift: realized by shifting the 2-complement and transforming
it back (2 >>bitInvert's)!

The LargeNegativeIntegers treatment is wrong here.

Let's take a look onto the bits:
0 bitShift: -1 0
-1 bitShift: -1 -1 "..1 -> ..1"
-2 bitShift: -1 -1 "..10 -> ..1"
-3 bitShift: -1 -2 "..101 -> ..10"
-4 bitShift: -1 -2  "..100 -> ..10"
-5 bitShift: -1 -3  "..1011 -> ..101"
-6 bitShift: -1 -3  "..1010 -> ..101"

A right shift of negative Integers takes one-bits from the left, if we
take the 2-complement representation with an infinite number of ones to
the left.

So

SmallInteger>>
bitShift: arg 
	"Primitive. Answer an Integer whose value is the receiver's value 
	shifted left by the number of bits indicated by the argument. Negative 
	arguments shift right. The receiver is interpreted as having 
	2's-complement representation. 
	Essential.  See Object documentation whatIsAPrimitive."
	<primitive: 17>
	self >= 0 ifTrue: [^ super bitShift: arg].
	^ arg >= 0
		ifTrue: [(self negated bitShift: arg) negated]
		ifFalse: [(self bitInvert bitShift: arg) bitInvert]

does it right, but not

Integer>>
bitShift: shiftCount 
	"Answer an Integer whose value (in twos-complement representation) is  
	 the receiver's value (in twos-complement representation) shifted left 
	by  
	 the number of bits indicated by the argument. Negative arguments   
	shift right. Zeros are shifted in from the right in left shifts."
	| rShift |
	shiftCount >= 0 ifTrue: [^ self digitLshift: shiftCount]. "OK."
	rShift _ 0 - shiftCount.
	^ (self						
		digitRshift: (rShift bitAnd: 7)
		bytes: (rShift bitShift: -3)
		lookfirst: self digitLength) normalize

, which calls >>digitRshift:bytes:lookfirst, but this - private - method
works only 2-complement correct for positive Integers!

So the right shift variant here is wrong!

The ANSI standard
	NCITS J20 DRAFT December, 1997 of ANSI Smalltalk Standard revision 1.9
avoids this problem by just stating that the result is undefined for
negative Integers:

---

5.6.5.8 Message: bitShift: shift
Synopsis

NCITS J20 DRAFT December, 1997 141
of ANSI Smalltalk Standard revision 1.9
Answer the result of logically bit-wise shifting the binary
representation of the receiver by shift
bits.
Definition: <integer>
If shift is positive, the receiver is shifted left and zeros (0) are
shifted in on the right. If shift is
negative, the receiver is shifted right and low order bits are
discarded.
The result is undefined if either the receiver is negative.
Parameters
shift <integer> uncaptured
Return Values
<integer>unspecified
Errors
none

---
('either' seems to be a typos here.)

For other bit operations ANSI says the same.


So I see two solutions of the problems:

- to go after ANSI and kicking off shift and possibly other bit ops for
negative Integers, or
- to give the Integer shift operation methods the same semantics as the
SmallInteger ones, means consequently 2-complement semantics.

In both cases it has taken care of the arithmetic methods which rely on
shift operations, because negative Integers come into play here.

Currently I don't have an opinion about what's best, but I think a
refactoring *is* needed!

Comments?


Greetings,

Stephan


PS: Some good news:
	- >>bitInvert: works as expected,
	- digit logic operations should work correctly (at least for the
LargeIntegersPlugin, because it is only defined for *positive* Integers,
otherwise standard ST methods are used...)

Stephan Rudlof wrote:
> 
> Andreas,
> 
> "Raab, Andreas" wrote:
> >
> > Folks,
> >
> > I just run into an interesting problem. When I attempted to compute
> >
> >         -585148196 / -1442692966
> >
> > (not by typing in these numbers of course ;-) I got an error saying "highBit
> > is not defined for negative numbers".
> 
> I cannot repeat this error, by evaluating into a workspace I get:
> 
> -585148196 / -1442692966  -> (58/143)
> -585148196 // -1442692966 -> 0
> 
> another example to get a result >0:
> 
> -5851481960 / -1442692966 -> (580/143)
> -5851481960 // -1442692966 -> 4
> 
> with 2.8alpha#2242 with LargeIntegers module.
> 
> But just I've seen that I *can* confirm this error, if I *comment* *out*
> the call of the LargeIntegers module!
> Interesting!
> 
> Seems to be a case where the LargeInteger module computes better than
> the standard ST methods.
> 
> Explanation:
> 
> - semantics: the error message is correct at this point in the ST
> method: a negative integer in 2-complements arithmetics with
> [infinite/not fixed] length hasn't a high bit! Theoretically there is an
> infinite number of leading one bits.
> - methods: LargePositiveInteger>>highBit can always be used for
> LargeNegativeInteger, but >>highBit for negative SmallIntegers isn't
> defined!
> 
> - LargeIntegers: After taking a look into the LargeIntegersPlugin and
> into the callers Integer>>/, >>quo:, LargePositiveInteger>>\\\ and the
> DSA ones of Integer>>digitDiv:neg:, I would say, that all is correct
> here. The here called
>         LargeIntegersPlugin>>primDigitDiv: secondInteger negative: neg
> method converts the int args to LargeIntegers and treats them as
> positive ones while dividing them. The sign is computed by and given as
> arg from the callers of Integer>>digitDiv:neg:.
> Some further computation confirms *same* semantics for
> SmallInteger/SmallInteger versus SmallInteger/LargeInteger arithmetics
> (in the latter case the SmallInteger will be transformed to a non
> normalized LargeInteger):
> 
> -12 // -32 0 "SmallInteger/SmallInteger"
> -12 \\ -32 -12
> -585148196 // -1442692966 0 "SmallInteger/LargeInteger"
> -585148196 \\ -1442692966 -585148196
> 12 // -32 -1
> 12 \\ -32 -20
> 585148196 // -1442692966 -1
> 585148196 \\ -1442692966 -857544770
>         -1442692966 - -857544770 -585148196
> -12 // 32  -1
> -12 \\ 32  20
> -585148196 // 1442692966  -1
> -585148196 \\ 1442692966  857544770
> 
> and
> 
> -32 // -12 2
> -32 \\ -12 -8
> -1442692966 // -585148196 2
> -1442692966 \\ -585148196 -272396574
> 
> -32 // 12  -3
> -32 \\ 12  4
> -1442692966 // 585148196  -3
> -1442692966 \\ 585148196 312751622
> 
> 32 // -12  -3
> 32 \\ -12  -4
> 1442692966 // -585148196  -3
> 1442692966 \\ -585148196 -312751622
> 
> So the bug is in the old ST method >>digitDiv:neg: or in the callers of
> it:
> - e.g. (!, there is/are other(s) (at least Integer>>/ (these are the
> 'official' ones...)))
> Integer
> >>quo: aNumber
>         "Refer to the comment in Number quo:"
>         | ng quo |
>         aNumber isInteger
>                 ifTrue:
>                         [ng _ self negative == aNumber negative == false.
>                         quo _ (self digitDiv: (aNumber class == SmallInteger
>                                                         ifTrue: [aNumber abs]
>                                                         ifFalse: [aNumber])
>                                                 neg: ng)
>                                                 at: 1.
>                         ^ quo normalize].
>         ^ aNumber adaptToInteger: self andSend: #quo:
> 
> , works well for positive/negative LargeIntegers/SmallInteger *args* and
> for positive/negative LargeInteger receivers as for positive
> SmallInteger receivers,
> but *not* for *negative* SmallInteger receivers! That's the point.
> 
> With the LargeIntegers module this works, because it converts all
> SmallIntegers to LargeIntegers.
> 
> > It seems something is broken in the
> > logic for large negative integers here. The interesting thing is that the
> > LargeIntegersPlugin actually computes the correct result (I was originally
> > working in a somewhat outdated image and switched to the latest one for
> > seeing if the problem has been solved). However, when commenting out the
> > primitive in #digitDiv:neg: the same error occurs.
> 
> Your LargeIntegers module probably wasn't installed correctly!
> Check 1000 factorial... ;-)
> 
> >
> > Can somebody shed a bit light on this?! I hate it when Integer's don't work
> > ;-)
> 
> Me, too.
> 
> >
> >   - Andreas
> 
> Greetings,
> 
> Stephan
> --
> Stephan Rudlof (sr at evolgo.de)
>    "Genius doesn't work on an assembly line basis.
>     You can't simply say, 'Today I will be brilliant.'"
>     -- Kirk, "The Ultimate Computer", stardate 4731.3

-- 
Stephan Rudlof (sr at evolgo.de)
   "Genius doesn't work on an assembly line basis.
    You can't simply say, 'Today I will be brilliant.'"
    -- Kirk, "The Ultimate Computer", stardate 4731.3





More information about the Squeak-dev mailing list