[BUG] in digit logic
Locked
 
|
Hi guys,
Try this code and tell me what you think: (1 to: 80) reject: [:n | ((2 raisedTo: n) negated bitAnd: (2 raisedTo: n) negated - 1) = (2 raisedTo: n + 1) negated]. Answer is at http://bugs.squeak.org/view.php?id=6874 I'm a bit surprised to encounter this one in VW7.7... But hey, it must be a very old bug ! Nicolas _______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc |
|
|
nicolas cellier <nicolas.cellier.aka.nice <at> gmail.com> writes:
> > Hi guys, > Try this code and tell me what you think: > > (1 to: 80) reject: [:n | > ((2 raisedTo: n) negated bitAnd: (2 raisedTo: n) negated - 1) > = (2 raisedTo: n + 1) negated]. > > Answer is at http://bugs.squeak.org/view.php?id=6874 > I'm a bit surprised to encounter this one in VW7.7... > But hey, it must be a very old bug ! > > Nicolas > By the way, this bug is also written in VM stone at primitive 34. So that makes at least to methods to be changed for a temporary workaround. Nicolas _______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc |
|
|
In reply to this post by Nicolas Cellier
I am not sure what to think about it. Try this C code:
#include <stdio.h> int main() { printf("%lx & %lx is %lx.\n", -(1L << 31), -(1L << 31) - 1, -(1L << 31) & (-(1L << 31) - 1)); printf("%i & %i is %i.\n", -(1 << 31), -(1 << 31) - 1, -(1 << 31) & (-(1 << 31) - 1)); return; } The first line does your calculation with 64 bit signed ints and outputs the result in hex (the compiler is on a 64 bit platform). The second line does your calculations with 32 bit signed ints, and outputs the results in decimal. The resulting program produces the following: ffffffff80000000 & ffffffff7fffffff is ffffffff00000000. -2147483648 & 2147483647 is 0. Smalltalk matches the second line with 32 bit integers. Now, your example involves large negative integers 4 bytes long. Note that large negative integers are stored as large integers plus a sign bit. This implies large negative integers in Smalltalk are meant to be just as large as necessary. Otherwise, they would have to be infinitely large because there is no limit to the size of a large negative integer. In other words, all the "leading Fs" are removed because large negative integers do not have a fixed size. In the C program above, using 64 bit ints resulted in 8 leading Fs. How many leading Fs should negative large integers assume? Are you still thinking this is a bug? Andres. -----Original Message----- From: [hidden email] [mailto:[hidden email]] On Behalf Of nicolas cellier Sent: Wednesday, April 14, 2010 12:48 PM To: [hidden email] Subject: [vwnc] [BUG] in digit logic Hi guys, Try this code and tell me what you think: (1 to: 80) reject: [:n | ((2 raisedTo: n) negated bitAnd: (2 raisedTo: n) negated - 1) = (2 raisedTo: n + 1) negated]. Answer is at http://bugs.squeak.org/view.php?id=6874 I'm a bit surprised to encounter this one in VW7.7... But hey, it must be a very old bug ! Nicolas _______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc _______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc |
|
|
On Wed, Apr 14, 2010 at 5:33 PM, Valloud, Andres <[hidden email]> wrote: I am not sure what to think about it. Try this C code: -1 is an infinite string of 1's (*). Hence (-1 bitAnd: anyInteger) = anyInteger. Hence negative something bitAnd: negative some other thing is negative something else. The issue is only how many bytes negative something else requires and whether this fits in a SmallInteger or a LargeNegativeInteger of suitable size.
(*) note that the infinite string of 1's has a compact representation, namely SmallInteger -1. But that does /not/ imply that (-1 bitAt: i) = 0 for i > 0 ever. HTH
Eliot
_______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc |
|
|
On Wed, Apr 14, 2010 at 6:12 PM, Eliot Miranda <[hidden email]> wrote:
and since C doesn't implement infinite precision arithmetic, whatever C has to say on the matter is deeply suspect when not outright wrong.
best Eliot P.S. I will not hit Send before I have read and understood my post, and verified it is complete. I will not hit Send before I have read and understood my post, and verified it is complete.
I will not hit Send before I have read and understood my post, and verified it is complete. I will not hit Send before I have read and understood my post, and verified it is complete....
(to the opening music of The Simpsons)
_______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc |
|
|
> and since C doesn't implement infinite precision
arithmetic, whatever C has to say on the matter is deeply suspect when not
outright wrong.
I think it's illustrative to see what happens with 64
bit integers as opposed to 32 bit integers. So, as you say, if you
consider the infinite precision large negative integers, and then see
them as an extreme case of increasing the integer size in C, you'd be
forced into an endless tail of leading 0xF nibbles. So we don't do it, and
then bitAnd: behaves "strange".
Also, note that Nicolas' test case was not something
bitAnd: -1 exactly, hence the C test program.
Andres.
From: Eliot Miranda [mailto:[hidden email]] Sent: Wednesday, April 14, 2010 6:16 PM To: Valloud, Andres Cc: vwnc NC Subject: Re: [vwnc] [BUG] in digit logic On Wed, Apr 14, 2010 at 6:12 PM, Eliot Miranda <[hidden email]>
wrote:
and since C doesn't implement infinite precision arithmetic, whatever C has
to say on the matter is deeply suspect when not outright wrong.
best
Eliot
P.S. I will not hit Send before I have read and understood my post,
and verified it is complete.
I will not hit Send before I have
read and understood my post, and verified it is complete.
I will not hit Send before I have read
and understood my post, and verified it is complete.
I will not hit Send before I have read and understood my post, and
verified it is complete.
...
(to the opening music of The Simpsons)
_______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc |
|
|
Valloud, Andres <avalloud <at> cincom.com> writes:
> > > > and since C doesn't implement infinite precision > arithmetic, whatever C has to say on the matter is deeply suspect when not > outright wrong. > > > I think it's illustrative to see what happens with 64 > bit integers as opposed to 32 bit integers. So, as you say, if you > consider the infinite precision large negative integers, and then see > them as an extreme case of increasing the integer size in C, you'd be > forced into an endless tail of leading 0xF nibbles. So we don't do it, and > then bitAnd: behaves "strange". > > > Also, note that Nicolas' test case was not something > bitAnd: -1 exactly, hence the C test program. > > > > Andres. Yes, the C code was usefull ! It illustrates exactly the same bug as VW: 64 bits code works ok 32 bit groke the carry. In Smalltalk, internal representation is not two-complement, but absolute value. So problem of infinite serie of leading 1 does not exist (it's virtual). And we can extend the precision one byte further if we need a carry. The modification is minor, here it is if you want to try: digitLogic: arg op: op length: len "Perform the indicated bit-wise operation between the reciever and arg. This implementation depends on the fact that new Integers are initialized to be all zeros" | result neg1 neg2 rneg z1 z2 rz b1 b2 b rdigits | neg1 := self negative. neg2 := arg negative. rneg := ((neg1 ifTrue: [-1] ifFalse: [0]) perform: op with: (neg2 ifTrue: [-1] ifFalse: [0])) < 0. result := Integer new: len neg: rneg. rz := z1 := z2 := true. rdigits := 1. 1 to: result digitLength do: [:i | b1 := self digitAt: i. neg1 ifTrue: [b1 := z1 ifTrue: [b1 = 0 ifTrue: [0] ifFalse: [z1 := false. 256 - b1]] ifFalse: [255 - b1]]. b2 := arg digitAt: i. neg2 ifTrue: [b2 := z2 ifTrue: [b2 = 0 ifTrue: [0] ifFalse: [z2 := false. 256 - b2]] ifFalse: [255 - b2]]. b := b1 perform: op with: b2. b = 0 ifFalse: [rdigits := i]. result digitAt: i put: (rneg ifTrue: [rz ifTrue: [b = 0 ifTrue: [0] ifFalse: [rz := false. 256 - b]] ifFalse: [255 - b]] ifFalse: [b])]. (rneg and: [result compressed = 0]) ifTrue: [ ^(result growBy: 1) digitAt: len + 1 put: 1; compressed]. rdigits < len ifTrue: [^(result growTo: rdigits) compressed]. ^result compressed _______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc |
|
|
In reply to this post by Nicolas Cellier
nicolas cellier wrote:
> Hi guys, > Try this code and tell me what you think: > > (1 to: 80) reject: [:n | > ((2 raisedTo: n) negated bitAnd: (2 raisedTo: n) negated - 1) > = (2 raisedTo: n + 1) negated]. > > Answer is at http://bugs.squeak.org/view.php?id=6874 > I'm a bit surprised to encounter this one in VW7.7... > But hey, it must be a very old bug ! > > Nicolas > > _______________________________________________ > vwnc mailing list > [hidden email] > http://lists.cs.uiuc.edu/mailman/listinfo/vwnc > > Created AR59901 for this. The problem is that there are negative numbers that can be represented as an n-bit LargeNegativeInteger, but cannot be represented as n-bit Integers with a twos-complement notation. Easiest fix is to simply always use the next bigger size for the computation of the result. In prLarge.c, in the largeBitLogic macro, replace if (!newInteger(max(arg1.size,arg2.size), rneg, &result)) \ with if (!newInteger(max(arg1.size,arg2.size)+1, rneg, &result)) \ Ralf -- Ralf Propach, [hidden email] Tel: +49 231 975 99 38 Fax: +49 231 975 99 20 Georg Heeg eK (Dortmund) Handelsregister: Amtsgericht Dortmund A 12812 _______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc |
|
|
Nice try with the Smalltalk side fix. However, bitXor: shouldn't cause
negative results to grow... -----Original Message----- From: [hidden email] [mailto:[hidden email]] On Behalf Of Ralf Propach Sent: Thursday, April 15, 2010 4:03 AM To: nicolas cellier; [hidden email] Subject: Re: [vwnc] [BUG] in digit logic nicolas cellier wrote: > Hi guys, > Try this code and tell me what you think: > > (1 to: 80) reject: [:n | > ((2 raisedTo: n) negated bitAnd: (2 raisedTo: n) negated - 1) > = (2 raisedTo: n + 1) negated]. > > Answer is at http://bugs.squeak.org/view.php?id=6874 > I'm a bit surprised to encounter this one in VW7.7... > But hey, it must be a very old bug ! > > Nicolas > > _______________________________________________ > vwnc mailing list > [hidden email] > http://lists.cs.uiuc.edu/mailman/listinfo/vwnc > > Created AR59901 for this. The problem is that there are negative numbers that can be represented as an n-bit LargeNegativeInteger, but cannot be represented as n-bit Integers with a twos-complement notation. Easiest fix is to simply always use the next bigger size for the computation of the result. In prLarge.c, in the largeBitLogic macro, replace if (!newInteger(max(arg1.size,arg2.size), rneg, &result)) \ with if (!newInteger(max(arg1.size,arg2.size)+1, rneg, &result)) \ Ralf -- Ralf Propach, [hidden email] Tel: +49 231 975 99 38 Fax: +49 231 975 99 20 Georg Heeg eK (Dortmund) Handelsregister: Amtsgericht Dortmund A 12812 _______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc _______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc |
|
|
... this is trickier than it seems :).
-----Original Message----- From: [hidden email] [mailto:[hidden email]] On Behalf Of Valloud, Andres Sent: Thursday, May 27, 2010 11:39 PM To: [hidden email] Subject: Re: [vwnc] [BUG] in digit logic Nice try with the Smalltalk side fix. However, bitXor: shouldn't cause negative results to grow... -----Original Message----- From: [hidden email] [mailto:[hidden email]] On Behalf Of Ralf Propach Sent: Thursday, April 15, 2010 4:03 AM To: nicolas cellier; [hidden email] Subject: Re: [vwnc] [BUG] in digit logic nicolas cellier wrote: > Hi guys, > Try this code and tell me what you think: > > (1 to: 80) reject: [:n | > ((2 raisedTo: n) negated bitAnd: (2 raisedTo: n) negated - 1) > = (2 raisedTo: n + 1) negated]. > > Answer is at http://bugs.squeak.org/view.php?id=6874 > I'm a bit surprised to encounter this one in VW7.7... > But hey, it must be a very old bug ! > > Nicolas > > _______________________________________________ > vwnc mailing list > [hidden email] > http://lists.cs.uiuc.edu/mailman/listinfo/vwnc > > Created AR59901 for this. The problem is that there are negative numbers that can be represented as an n-bit LargeNegativeInteger, but cannot be represented as n-bit Integers with a twos-complement notation. Easiest fix is to simply always use the next bigger size for the computation of the result. In prLarge.c, in the largeBitLogic macro, replace if (!newInteger(max(arg1.size,arg2.size), rneg, &result)) \ with if (!newInteger(max(arg1.size,arg2.size)+1, rneg, &result)) \ Ralf -- Ralf Propach, [hidden email] Tel: +49 231 975 99 38 Fax: +49 231 975 99 20 Georg Heeg eK (Dortmund) Handelsregister: Amtsgericht Dortmund A 12812 _______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc _______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc _______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc |
|
|
In reply to this post by Nicolas Cellier
Watch out... the below section
b = 0 ifFalse: [rdigits := i]. result digitAt: i put: (rneg ifTrue: [rz ifTrue: [b = 0 ifTrue: [0] ifFalse: [rz := false. 256 - b]] ifFalse: [255 - b]] ifFalse: [b])]. should be written like newDigit := (rneg ifTrue: [...] ifFalse: [...]). newDigit = 0 ifFalse: [rdigits := i]. result digitAt: i put: newDigit because otherwise expressions like -65515 digitLogic: -65515 op: #bitAnd: length: 2 fail to produce the correct result. Andres. -----Original Message----- From: [hidden email] [mailto:[hidden email]] On Behalf Of nicolas cellier Sent: Thursday, April 15, 2010 4:01 AM To: [hidden email] Subject: Re: [vwnc] [BUG] in digit logic Valloud, Andres <avalloud <at> cincom.com> writes: > > > > and since C doesn't implement infinite precision > arithmetic, whatever C has to say on the matter is deeply suspect when > not outright wrong. > > > I think it's illustrative to see what happens with 64 bit integers as > opposed to 32 bit integers. So, as you say, if you consider the > infinite precision large negative integers, and then see them as an > extreme case of increasing the integer size in C, you'd be forced into > an endless tail of leading 0xF nibbles. So we don't do it, and then > bitAnd: behaves "strange". > > > Also, note that Nicolas' test case was not something > bitAnd: -1 exactly, hence the C test program. > > > > Andres. Yes, the C code was usefull ! It illustrates exactly the same bug as VW: 64 bits code works ok 32 bit groke the carry. In Smalltalk, internal representation is not two-complement, but absolute value. So problem of infinite serie of leading 1 does not exist (it's virtual). And we can extend the precision one byte further if we need a carry. The modification is minor, here it is if you want to try: digitLogic: arg op: op length: len "Perform the indicated bit-wise operation between the reciever and arg. This implementation depends on the fact that new Integers are initialized to be all zeros" | result neg1 neg2 rneg z1 z2 rz b1 b2 b rdigits | neg1 := self negative. neg2 := arg negative. rneg := ((neg1 ifTrue: [-1] ifFalse: [0]) perform: op with: (neg2 ifTrue: [-1] ifFalse: [0])) < 0. result := Integer new: len neg: rneg. rz := z1 := z2 := true. rdigits := 1. 1 to: result digitLength do: [:i | b1 := self digitAt: i. neg1 ifTrue: [b1 := z1 ifTrue: [b1 = 0 ifTrue: [0] ifFalse: [z1 := false. 256 - b1]] ifFalse: [255 - b1]]. b2 := arg digitAt: i. neg2 ifTrue: [b2 := z2 ifTrue: [b2 = 0 ifTrue: [0] ifFalse: [z2 := false. 256 - b2]] ifFalse: [255 - b2]]. b := b1 perform: op with: b2. b = 0 ifFalse: [rdigits := i]. result digitAt: i put: (rneg ifTrue: [rz ifTrue: [b = 0 ifTrue: [0] ifFalse: [rz := false. 256 - b]] ifFalse: [255 - b]] ifFalse: [b])]. (rneg and: [result compressed = 0]) ifTrue: [ ^(result growBy: 1) digitAt: len + 1 put: 1; compressed]. rdigits < len ifTrue: [^(result growTo: rdigits) compressed]. ^result compressed _______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc _______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc |
|
|
Valloud, Andres <avalloud <at> cincom.com> writes:
> > snip... > > because otherwise expressions like > > -65515 digitLogic: -65515 op: #bitAnd: length: 2 > > fail to produce the correct result. > > Andres. > Hi Andres, above expression works in Squeak. Nicolas _______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc |
|
|
I took a quick look last night, and I *think* (I could be wrong!) the
code used by Squeak is not exactly the same as the code that was in the original message here. I thought I'd post about what I found with the code in this mailing list. I am glad the code in Squeak is not broken further :). -----Original Message----- From: [hidden email] [mailto:[hidden email]] On Behalf Of nicolas cellier Sent: Friday, May 28, 2010 11:13 AM To: [hidden email] Subject: Re: [vwnc] [BUG] in digit logic Valloud, Andres <avalloud <at> cincom.com> writes: > > snip... > > because otherwise expressions like > > -65515 digitLogic: -65515 op: #bitAnd: length: 2 > > fail to produce the correct result. > > Andres. > Hi Andres, above expression works in Squeak. Nicolas _______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc _______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc |
|
|
Valloud, Andres <avalloud <at> cincom.com> writes:
> > I took a quick look last night, and I *think* (I could be wrong!) the > code used by Squeak is not exactly the same as the code that was in the > original message here. I thought I'd post about what I found with the > code in this mailing list. I am glad the code in Squeak is not broken > further :). > > -----Original Message----- > From: vwnc-bounces <at> cs.uiuc.edu [mailto:vwnc-bounces <at> cs.uiuc.edu] On > Behalf Of nicolas cellier > Sent: Friday, May 28, 2010 11:13 AM > To: vwnc <at> cs.uiuc.edu > Subject: Re: [vwnc] [BUG] in digit logic > > Valloud, Andres <avalloud <at> cincom.com> writes: > > > > > snip... > > > > because otherwise expressions like > > > > -65515 digitLogic: -65515 op: #bitAnd: length: 2 > > > > fail to produce the correct result. > > > > Andres. > > > > Hi Andres, > > above expression works in Squeak. > > Nicolas > > _______________________________________________ > vwnc mailing list > vwnc <at> cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/vwnc > You are perfectly right... This one should be ok. digitLogic: arg op: op length: len "Perform the indicated bit-wise operation between the reciever and arg. This implementation depends on the fact that new Integers are initialized to be all zeros" | result neg1 neg2 rneg z1 z2 rz b1 b2 b rdigits | neg1 := self negative. neg2 := arg negative. rneg := ((neg1 ifTrue: [-1] ifFalse: [0]) perform: op with: (neg2 ifTrue: [-1] ifFalse: [0])) < 0. result := Integer new: len neg: rneg. rz := z1 := z2 := true. rdigits := 1. 1 to: result digitLength do: [:i | b1 := self digitAt: i. neg1 ifTrue: [b1 := z1 ifTrue: [b1 = 0 ifTrue: [0] ifFalse: [z1 := false. 256 - b1]] ifFalse: [255 - b1]]. b2 := arg digitAt: i. neg2 ifTrue: [b2 := z2 ifTrue: [b2 = 0 ifTrue: [0] ifFalse: [z2 := false. 256 - b2]] ifFalse: [255 - b2]]. b := b1 perform: op with: b2. rneg ifTrue: [b := rz ifTrue: [b = 0 ifTrue: [0] ifFalse: [rz := false. 256 - b]] ifFalse: [255 - b]]. b = 0 ifFalse: [rdigits := i]. result digitAt: i put: b]. (rneg and: [result compressed = 0]) ifTrue: [ ^(result growBy: 1) digitAt: len + 1 put: 1; compressed]. rdigits < len ifTrue: [^(result growTo: rdigits) compressed]. ^result compressed _______________________________________________ vwnc mailing list [hidden email] http://lists.cs.uiuc.edu/mailman/listinfo/vwnc |
«
Return to VisualWorks
|
1 view|%1 views
| Free forum by Nabble | Edit this page |