John Duncan wrote:
> 
> Wow... Here's something interesting:  the right shift for negative large
> integers appears to have the same semantics as the algebraic right shift as
> implemented on the PowerPC.  This this generalization correct?  If so,
> identical semantics could be found by generating the correct _asm
> instruction in the vm.
> 
> And, if this is desirable, then perhaps it's easier to make the small
> integer semantics emulate the large integer semantics on all platforms, i
> suppose by:
> 
> negating x
> shifting x
> negating x
> 
> which requires ugliness in the case of x=16r40000000.
> 
> I wonder whether it's possible to implement a two's complement shifting
> semantics efficiently on LargeNegativeIntegers.  Are they not implemented as
> polynomials?

Yes. As byte arrays where each byte is a digit of base 256.

For me it is *mainly* important to reach *consistency* in the semantics
here.


Semantics
---------

If I use a negative Integer>>rightShift: I want to have the *same*
semantics for *all* Integers, means for *both* SmallIntegers and
LargeIntegers.
This is just one of the advantages of ST against many other languages: I
don't need and I don't want to know *where* the border between
SmallIntegers and LargeIntegers is! (Principally this could be different
at different machines.)
Here we have a difference, but only for Integer>>rightShift: applied to
negative Integers.
This leads me to the following question:

*** Does anybody knows code which *depends* on a two-complement right
shift of *negative* Integers? ***

Outside the Integer classes, of course.

Most code which uses shift operations uses *positive* Integers, there
this is a non issue.

Note: >>rightShift: of negative Integers is *undefined* by the ANSI
standard (see below).


Efficency
---------

Efficiency for right-shifting negative Integers doesn't seem to be very
important, because it seems to me to be a rare (?, but I think so) case.
Encryption algorithms don't work with negative integers AFAIK, where
speed is definitely important.
But *answers* to my question could bring light into this.


Stephan

> 
> -John
> 
> > -----Original Message-----
> > From: sr at Klaus.priv [mailto:sr at Klaus.priv]On Behalf Of Stephan Rudlof
> > Sent: Tuesday, June 06, 2000 4:51 PM
> > To: squeak at cs.uiuc.edu; Ingalls, Dan; Raab, Andreas; Stefan Matthias
> > Aust; R. A. Harmon; John Maloney; Leandro Caniglia
> > Subject: [BUG][SEMANTIC] semantics of Integer bit ops, e.g. >>bitShift:
> > [was: Re: Large integers problem...]
> >
> >
> > 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
> >
> >

-- 
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