who ever performed bit logic on large negative integer?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

who ever performed bit logic on large negative integer?

Nicolas Cellier-3

SmallInteger < 0 are stored directly in two complement native format
(well, except the tag bits)

But LargeNegativeInteger are stored same as their absolute value.

This does simplify some algorithms. But this leads to quite tricky ones
when bit logic is to be performed based on two complement.
And whenever tricks are used, bugs frequency generally tends to
increase. I believe long life bugs are lying in such swamps.

That's why i'm very proud of finding accidentaly
http://bugs.squeak.org/view.php?id=6874 via
http://bugs.squeak.org/view.php?id=6873.

As usual, most of you won't ever care of it.
Yeah, one more useless bugfix i am specialized in since the probability
you bump into it must not exceed 1.0e-8 per hour of Smalltalking.

But who knows, it's a kind of insurance in case a silly engineer had the
idea to run nearest nuclear plant in Squeak!

And well, it's also for the beauty of mathematics!

Nicolas


Reply | Threaded
Open this post in threaded view
|

Re: who ever performed bit logic on large negative integer?

Tom Phoenix
On Jan 25, 2008 7:12 PM, nicolas cellier <[hidden email]> wrote:

> As usual, most of you won't ever care of it.

Not so! Just because you don't notice the bolts holding the bridge
together every time you drive across, that doesn't mean you don't
appreciate them.

Each nudge towards perfection is another brush-stroke on the endless canvas.

Neil Armstrong couldn't have walked on the moon if there hadn't been
somebody emptying the wastebaskets in mission control.

Every contribution counts.

Thanks!

--Tom Phoenix

Reply | Threaded
Open this post in threaded view
|

Re: who ever performed bit logic on large negative integer?

Stephan Rudlof
In reply to this post by Nicolas Cellier-3
There should be a comment somewhere (Integer class comment?) explicitly stating, that you cannot rely on two complement semantics for LargeNegativeIntegers regarding bit logic (bit logic restricted to positive Integers is correct).

I fear, changing the fundamental design decision to use magnitude representation for LargeNegativeIntegers - e.g. by introducing some kind of two complement representation - would imply a lot of work...


Regards,
Stephan


On 26.01.2008 04:12, nicolas cellier wrote:

>
> SmallInteger < 0 are stored directly in two complement native format
> (well, except the tag bits)
>
> But LargeNegativeInteger are stored same as their absolute value.
>
> This does simplify some algorithms. But this leads to quite tricky ones
> when bit logic is to be performed based on two complement.
> And whenever tricks are used, bugs frequency generally tends to
> increase. I believe long life bugs are lying in such swamps.
>
> That's why i'm very proud of finding accidentaly
> http://bugs.squeak.org/view.php?id=6874 via
> http://bugs.squeak.org/view.php?id=6873.
>
> As usual, most of you won't ever care of it.
> Yeah, one more useless bugfix i am specialized in since the probability
> you bump into it must not exceed 1.0e-8 per hour of Smalltalking.
>
> But who knows, it's a kind of insurance in case a silly engineer had the
> idea to run nearest nuclear plant in Squeak!
>
> And well, it's also for the beauty of mathematics!
>
> Nicolas
>
>
>

--
Stephan Rudlof ([hidden email])
   "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

Reply | Threaded
Open this post in threaded view
|

Re: who ever performed bit logic on large negative integer?

Paolo Bonzini-2
> There should be a comment somewhere (Integer class comment?) explicitly
> stating, that you cannot rely on two complement semantics for
> LargeNegativeIntegers regarding bit logic (bit logic restricted to
> positive Integers is correct).

That's absurd IMHO.

> I fear, changing the fundamental design decision to use magnitude
> representation for LargeNegativeIntegers - e.g. by introducing some kind
> of two complement representation - would imply a lot of work...

It is possible to work out bitwise ops on magnitude representation, by
computing the two's complement representation on the fly in the
primitives or in the fallback Smalltalk code.

Paolo

Reply | Threaded
Open this post in threaded view
|

PS: [Re: who ever performed bit logic on large negative integer?]

Stephan Rudlof
In reply to this post by Stephan Rudlof
PS: Furthermore you have to taken into account (amongst others printing the bit representation), that *mathematically* there are infinitely many leading ones for all (including ints represented as SmallIntegers) negative Integers.

On 26.01.2008 15:56, Stephan Rudlof wrote:

> There should be a comment somewhere (Integer class comment?) explicitly
> stating, that you cannot rely on two complement semantics for
> LargeNegativeIntegers regarding bit logic (bit logic restricted to
> positive Integers is correct).
>
> I fear, changing the fundamental design decision to use magnitude
> representation for LargeNegativeIntegers - e.g. by introducing some kind
> of two complement representation - would imply a lot of work...
>
>
> Regards,
> Stephan
>
>
> On 26.01.2008 04:12, nicolas cellier wrote:
>>
>> SmallInteger < 0 are stored directly in two complement native format
>> (well, except the tag bits)
>>
>> But LargeNegativeInteger are stored same as their absolute value.
>>
>> This does simplify some algorithms. But this leads to quite tricky
>> ones when bit logic is to be performed based on two complement.
>> And whenever tricks are used, bugs frequency generally tends to
>> increase. I believe long life bugs are lying in such swamps.
>>
>> That's why i'm very proud of finding accidentaly
>> http://bugs.squeak.org/view.php?id=6874 via
>> http://bugs.squeak.org/view.php?id=6873.
>>
>> As usual, most of you won't ever care of it.
>> Yeah, one more useless bugfix i am specialized in since the
>> probability you bump into it must not exceed 1.0e-8 per hour of
>> Smalltalking.
>>
>> But who knows, it's a kind of insurance in case a silly engineer had
>> the idea to run nearest nuclear plant in Squeak!
>>
>> And well, it's also for the beauty of mathematics!
>>
>> Nicolas
>>
>>
>>
>

--
Stephan Rudlof ([hidden email])
   "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

Reply | Threaded
Open this post in threaded view
|

Re: who ever performed bit logic on large negative integer?

Stephan Rudlof
In reply to this post by Paolo Bonzini-2
On 26.01.2008 16:07, Paolo Bonzini wrote:
>> There should be a comment somewhere (Integer class comment?)
>> explicitly stating, that you cannot rely on two complement semantics
>> for LargeNegativeIntegers regarding bit logic (bit logic restricted to
>> positive Integers is correct).
>
> That's absurd IMHO.

It's just warning of the current limitations.

>
>> I fear, changing the fundamental design decision to use magnitude
>> representation for LargeNegativeIntegers - e.g. by introducing some
>> kind of two complement representation - would imply a lot of work...
>

> It is possible to work out bitwise ops on magnitude representation, by
> computing the two's complement representation on the fly in the
> primitives or in the fallback Smalltalk code.

OK, another - better - way to go: should be much less work than changing the representation.

Stephan

>
> Paolo
>
>

--
Stephan Rudlof ([hidden email])
   "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

Reply | Threaded
Open this post in threaded view
|

Re: who ever performed bit logic on large negative integer?

Paolo Bonzini-2

>> It is possible to work out bitwise ops on magnitude representation, by
>> computing the two's complement representation on the fly in the
>> primitives or in the fallback Smalltalk code.
>
> OK, another - better - way to go: should be much less work than changing
> the representation.

That's exactly what nicolas's patch in mantis does.

Paolo

Reply | Threaded
Open this post in threaded view
|

Re: who ever performed bit logic on large negative integer?

Stephan Rudlof
On 26.01.2008 16:54, Paolo Bonzini wrote:
>
>>> It is possible to work out bitwise ops on magnitude representation,
>>> by computing the two's complement representation on the fly in the
>>> primitives or in the fallback Smalltalk code.
>>
>> OK, another - better - way to go: should be much less work than
>> changing the representation.
>

> That's exactly what nicolas's patch in mantis does.

Thanks for the clearification!

Stephan

>
> Paolo
>
>

--
Stephan Rudlof ([hidden email])
   "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

Reply | Threaded
Open this post in threaded view
|

Re: who ever performed bit logic on large negative integer?

Stephan Rudlof
In reply to this post by Nicolas Cellier-3
It's nice that LargeIntegersPlugin has *not* to be fixed (just checked), since its bit logic prims only cover bit logic for LargePositiveIntegers (both receiver and arg) and they fail for LargeNegativeIntegers (so the smalltalk fall back methods are used).

Stephan

On 26.01.2008 04:12, nicolas cellier wrote:

>
> SmallInteger < 0 are stored directly in two complement native format
> (well, except the tag bits)
>
> But LargeNegativeInteger are stored same as their absolute value.
>
> This does simplify some algorithms. But this leads to quite tricky ones
> when bit logic is to be performed based on two complement.
> And whenever tricks are used, bugs frequency generally tends to
> increase. I believe long life bugs are lying in such swamps.
>
> That's why i'm very proud of finding accidentaly
> http://bugs.squeak.org/view.php?id=6874 via
> http://bugs.squeak.org/view.php?id=6873.
>
> As usual, most of you won't ever care of it.
> Yeah, one more useless bugfix i am specialized in since the probability
> you bump into it must not exceed 1.0e-8 per hour of Smalltalking.
>
> But who knows, it's a kind of insurance in case a silly engineer had the
> idea to run nearest nuclear plant in Squeak!
>
> And well, it's also for the beauty of mathematics!
>
> Nicolas
>
>
>

--
Stephan Rudlof ([hidden email])
   "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

Reply | Threaded
Open this post in threaded view
|

Re: who ever performed bit logic on large negative integer?

Nicolas Cellier-3
In reply to this post by Paolo Bonzini-2
Paolo Bonzini a écrit :

>
>>> It is possible to work out bitwise ops on magnitude representation,
>>> by computing the two's complement representation on the fly in the
>>> primitives or in the fallback Smalltalk code.
>>
>> OK, another - better - way to go: should be much less work than
>> changing the representation.
>
> That's exactly what nicolas's patch in mantis does.
>
> Paolo
>
>

Oh, I did not that much!
All this arithmetic stuff simulating two complement was already there
for a long time in Squeak, bit logic was handled correctly in most cases.

My contribution is limited to finding a flaw in implementation in some
very rare conditions.

Thread title was a little provocation, because i think the feature is
rarely used, except accidentally. It was to eventually get an echo
proving me wrong.

In fact it is used very often via hash, since -3 hash = -3, and a lot of
bit logic is performed on hash codes, but:
1) a bug leading to a different hash would not matter
    (as long as it does not lead systematically to a single hash code)
2) most hash should involve SmallInteger, not large ones.

Anyway, we cannot blame squeak for taking the hard path.
Some smalltalk dialects have costless solutions, kind of:
        self error: 'cannot perform bit logic on negative integers'

Nicolas


Reply | Threaded
Open this post in threaded view
|

Re: who ever performed bit logic on large negative integer?

David Mitchell-10
In reply to this post by Tom Phoenix
> Neil Armstrong couldn't have walked on the moon if there hadn't been
> somebody emptying the wastebaskets in mission control.

That reminds me, I need to go delete some spam on the announcements list. ;-)