Integer bitAt: should be faster

> Hi Nicolas,
>
>     I think you can do better for LargeNegativeInteger.  A
> LargeNegativeInteger is stored as its absolute value (have a look at
> e.g. LargeNegativeInteger negated).  So for LargeNegativeInteger>>bitAt:
> you could write e.g.:
> LargeNegativeInteger>>bitAt: i
>     "this is optimized because super is slow"
>     | byteIndex bitIndex bs msb |
>     i <= 0 ifTrue: [^0].
>     byteIndex := (i - 1) // 8 + 1.
>     bitIndex := (i - 1) \\ 8 + 1.
>     byteIndex >= (bs := self basicSize) "Check implementation of
> digitLength" ifTrue:
>        [byteIndex > bs ifTrue: [^0].
>         ^bitIndex > (msb := self digitAt: byteIndex) highBit ifTrue: [1]
> ifFalse: [msb bitAt: i]].
>     ^(self digitAt: byteIndex) bitAt: bitIndex
>
> Shame to penalise negative large integers...
>
> On 2/1/07, *nicolas cellier* < [hidden email]
> <mailto:[hidden email]>> wrote:
>
>     Hello,
>     Integer>>bitAt: is based on bitShift: and bitAnd: operations.
>     This is generic but a little slow in LargeInteger arithmetic (creates
>     useless intermediary LargeIntegers)
>
>     Faster implementation is quite trivial
>
>     LargePositiveInteger>>bitAt: i
>          "this is optimized because super is slow"
>
>          (i <= 0 or: [i > (self digitLength * 8)]) ifTrue: [^0].
>          ^(self digitAt: (i - 1) // 8 + 1) bitAt: (i - 1) \\ 8 + 1
>
>
>     For LargeNegativeInteger, result is different only in higher bits...
>
>     LargeNegativeInteger>>bitAt: i
>          | abs |
>          abs := self abs.
>          ^i > abs highBit
>              ifTrue: [1]
>              ifFalse: [abs bitAt: i]
>
>     This is in public store SYSMOD-LargeIntegerFastUp
>
>     Note that SmallInteger can also be slow.
>
>     | x |
>     x := 1.
>     Time millisecondsToRun: [10000 timesRepeat: [x bitAt: 8000]]
>
>     | x |
>     x := 1 bitShift: 10000.
>     Time millisecondsToRun: [10000 timesRepeat: [x bitAt: 8000]]
>
>     For the second case, without patch i am around 150ms, with patch around
>     3 ms. That's worth a change.
>
>     Nicolas
>
>

> Hello,
> Integer>>bitAt: is based on bitShift: and bitAnd: operations.
> This is generic but a little slow in LargeInteger arithmetic (creates
> useless intermediary LargeIntegers)
>
> Faster implementation is quite trivial
>
> LargePositiveInteger>>bitAt: i
>     "this is optimized because super is slow"
>
>     (i <= 0 or: [i > (self digitLength * 8)]) ifTrue: [^0].
>     ^(self digitAt: (i - 1) // 8 + 1) bitAt: (i - 1) \\ 8 + 1
>
>
> For LargeNegativeInteger, result is different only in higher bits...
>
> LargeNegativeInteger>>bitAt: i
>     | abs |
>     abs := self abs.
>     ^i > abs highBit
>         ifTrue: [1]
>         ifFalse: [abs bitAt: i]
>
> This is in public store SYSMOD-LargeIntegerFastUp
>

> nicolas cellier wrote:
>> Hello,
>> Integer>>bitAt: is based on bitShift: and bitAnd: operations.
>> This is generic but a little slow in LargeInteger arithmetic (creates
>> useless intermediary LargeIntegers)
>>
>> Faster implementation is quite trivial
>>
>> LargePositiveInteger>>bitAt: i
>>     "this is optimized because super is slow"
>>
>>     (i <= 0 or: [i > (self digitLength * 8)]) ifTrue: [^0].
>>     ^(self digitAt: (i - 1) // 8 + 1) bitAt: (i - 1) \\ 8 + 1
>>
>>
>> For LargeNegativeInteger, result is different only in higher bits...
>>
>> LargeNegativeInteger>>bitAt: i
>>     | abs |
>>     abs := self abs.
>>     ^i > abs highBit
>>         ifTrue: [1]
>>         ifFalse: [abs bitAt: i]
>>
>> This is in public store SYSMOD-LargeIntegerFastUp
>>
>
> This is great for the LargePositiveInteger case, but I'm afraid that it
> gives incorrect answers for LargeNegativeIntegers. At least, it gives
> very different answers than Integer>>bitAt:.
>
> To give one example, I implemented the method above as
> LargeNegativeInteger>>nicolasBitAt: so I could have both implementations
> to compare, and ran:
>
>   | testNum orig nicolas |
>   testNum := ((2**50) + 1) negated.
>   orig := (1 to: 100) collect: [:i | testNum bitAt: i].
>   nicolas := (1 to: 100) collect: [:i | testNum nicolasBitAt: i].
>   ^orig = nicolas
>
> This answers false. If you look at the bits answered by each algorithm,
> you'll see that they're quite different. The test number was not hard to
> find, I think this will answer false for any negative large integer that
> isn't a power of two.
>
> I didn't run Eliot's code, but it looks like it has the same problem.
>
> VW stores large negative integers as sign-magnitude, with the sign
> implied by the class. However, #bitAt: answers the bit in twos
> complement. For positive numbers, this is the same. For negative
> numbers, you have to convert one to the other. And you can't convert
> without iterating through some number of the digits, in the worst case
> all of the digits.
>
> I've looked for a way to convert LargeNegativeIntegers to twos
> complement quickly, and I don't think there's a way to do it in
> Smalltalk. You may be able to improve on the current #bitAt: a little,
> but in my efforts I've always ended up with something that is much
> faster for positive numbers than for negative ones.
>
> Regards,
>
> -Martin
>
> (For the curious --
> The reason I have experience in this area is that I work on the
> interface between GemStone and VW or VA. GemStone and VW both have
> sign-magnitude large integers (though the digit lengths are different)
> but VA uses twos complement large integers. I've recently rewritten the
> code that converts between the binary forms.)
>
>