|
Joined: Jan 2004
Posts: 2,127
Hoopy frood
|
OP
Hoopy frood
Joined: Jan 2004
Posts: 2,127 |
An aspect of bitwise that I hadn't tested yet, dealing with negative terms, and I'm hoping Talon chips in on this.
It appears that the .bf mode for $xor and $and are not doing it right when exactly 1 of the terms is negative.
In doubles mode, a negative term is cast to positive by adding +2^32 and then the normal XOR or AND operation takes place, so that's making the next pair identical to each other:
//echo -a %null.bx same $and($calc(-2 + 00*2^32) ,255) = 254 //echo -a %null.bx same $and($calc(-2 + 01*2^32) ,255) = 254
//echo -a %null.bx same $xor($calc(-2 + 00*2^32) ,255) = 4294967041 //echo -a %null.bx same $xor($calc(-2 + 01*2^32) ,255) = 4294967041
However, it appears that in .bf mode that $xor(-N1,+N2) is the same as $xor(+N1,+N2), and the same goes for $and.
//echo -a %null.bf same $and($calc(-2 + 00*2^32) ,255) = 2 //echo -a %null.bf same $and($calc(+2 + 00*2^32) ,255) = 2 //echo -a %null.bf same $xor($calc(-2 + 00*2^32) ,255) = 253 //echo -a %null.bf same $xor($calc(+2 + 00*2^32) ,255) = 253
I'm not saying that it's wrong for the .bf mode answer to be different than the doubles mode result when 1 term is negative, but that the result shouldn't be based on $abs(negative number)
* *
I'm thinking the solution for when exactly 1 of the $xor $or $and terms is negative:
(A) Negative needs to have 1 << $numbits(positive term) added to it (B) Optional 3rd parm indicating the 1<<N value to add to the negative term, but which would be ignored except when exactly 1 of the 1st 2 terms is negative (C) Both (A) and (B)
For these examples, I took a pair of 64 bit numbers and xor'ed them together, and this shows that -A1 is being cast to A2 as $abs(A1) instead of as (-A1 + 1<<N), making c1==c2
//bigfloat on | var -s %a1 -11479905046016372873 , %a2 0 - %a1 , %b 16680346320774688079 , %c1 $xor(%a1,%b) , %c2 $xor(%a2,%b) , %bb + $+ $base(%b,10,2,64) | echo 3 -a a1 $base(%a1,10,2,64) | echo 5 -a ^b %bb | echo 4 -a c1 + $+ $base(%c1,10,2,64) | echo 2 -a a2 + $+ $base(%a2,10,2,64) | echo 5 -a ^b %bb | echo 4 -a c2 + $+ $base(%c2,10,2,64)
a1 -1001111101010000110100001101000011110011000001010011000010001001 ^b +1110011101111100011111101001101000111100010001001110110101001111 c1 +0111100000101100101011100100101011001111010000011101110111000110 a2 +1001111101010000110100001101000011110011000001010011000010001001 ^b +1110011101111100011111101001101000111100010001001110110101001111 c2 +0111100000101100101011100100101011001111010000011101110111000110
* *
Same thing is happening for $and() where -A1 is cast as $abs(A1), and the fix should be the same as for $xor, whether (A) (B) (C)
//bigfloat on | var -s %a1 -11479905046016372873 , %a2 0 - %a1 , %b 16680346320774688079 , %c1 $and(%a1,%b) , %c2 $and(%a2,%b) , %bb + $+ $base(%b,10,2,64) | echo 3 -a a1 $base(%a1,10,2,64) | echo 5 -a ^b %bb | echo 4 -a c1 + $+ $base(%c1,10,2,64) | echo 2 -a a2 + $+ $base(%a2,10,2,64) | echo 5 -a ^b %bb | echo 4 -a c2 + $+ $base(%c2,10,2,64)
* *
Same thing is happening for $or in .bf mode where $or(-N1,+N2) is the same as $or(+N1,+N2), and the solution should be whatever it is for $xor and $and
//bigfloat on | var -s %a1 -11479905046016372873 , %a2 0 - %a1 , %b 16680346320774688079 , %c1 $or(%a1,%b) , %c2 $or(%a2,%b) , %bb + $+ $base(%b,10,2,64) | echo 3 -a a1 $base(%a1,10,2,64) | echo 5 -a ^b %bb | echo 4 -a c1 + $+ $base(%c1,10,2,64) | echo 2 -a a2 + $+ $base(%a2,10,2,64) | echo 5 -a ^b %bb | echo 4 -a c2 + $+ $base(%c2,10,2,64)
* *
It seems that a variant of option (C) above has already been implemented for $not without being documented in /help
From a hasty typo due to renaming $xor to $not, I accidentally discovered that at least back to v6.35 that $not ignored a 2nd parm instead of rejecting as invalid syntax, and still ignores it in doubles mode.
However in .bf mode it appears that $not behaves differently than in doubles mode where $not(N) behaves like $xor(N,2^32-1), but instead returns different results within the < 2^32 range similar to the (C) solution above except as applied to $not, and also does not ignore the 2nd parm.
In .bf mode, $not uses the bit length of $abs(N1) to determine the not-mask, but if N2 is present it uses that instead as an override. So some mention in /help $not about the different results from $not in .bf mode seems appropriate, as well as mention of the N2 parm, because I was really confused at first to find that $not(10) was returning '5' because i happened to be in .bf mode, and then when $not(10,5) returned 21 it seemed really confusing. But now what I see where the result comes from, it makes sense
//.bigfloat off | var %i 0 | while (%i isnum 0-32) { echo -a %i : ~ %i vs ~ %i ,6 doubles: $not(%i) $not(%i,5) %.bf bf: $not(%i) $not(%i,5) | inc %i }
* *
Another bitwise having issues with negatives is the undocumented $numbits. This identifier is useful because it benchmarks twice as fast as the prior workaround as $len($base(N,10,2)). Plus, it's not limited to getting the bit length of a $maxlenl length outbase=2 string.
Even though $numbits and $base both benchmark much slower than $log2, the known issues for the precision of $log(2) means that you can't use $round or $ceil accurately for very large N, where the example below shows the number well above 2^4096 returning a log as if it's below it.
//var %t $ticksqpc, %a.bf $calc(2^4096 + 2^4051) | var -s %res1 $numbits(%a.bf) , %time1 $ticksqpc - %t , %t $ticksqpc , %res2 $len($base(%a.bf,10,2)) , %time2 $ticksqpc - %t , %t $ticksqpc , %res3 $log2(%a.bf) + 1 , %time3 $ticksqpc - %t
* *
However, when I test using the negative numbers, I'm finding results that don't look correct, so I'm appealing to Talon on this one too.
//echo -a $numbits(-1) %.bf $numbits(-1) result: 32 1
At first I was thinking doubles mode returned 32 for for all negative numbers, but that's not the case. If N is in the range [-1,-2^31] then yes $numbits always returns 32. But if it's in the range [-2^31,-(2^32-1)], it instead has different behavior where, if you strip all the leading 1's from $base($abs(N),10,2), that length is used as the bit length.
However if you're in .bf mode, results for negatives always seem to be $numbits($abs(N))
//bigfloat on | :label | var %i 1 , %bitlen 32 | while (%i isnum 1- %bitlen) { var %zeroes %i , %ones $calc(%bitlen - %zeroes -1) , %a - $+ $base($str(1,%ones) $+ $str(0,%zeroes) $+ 1 ,2,10) | echo -a numbits: $numbits(%a) base2 $base(%a,10,2) base10 %a $bigfloat | inc %i } | if ($bigfloat) { bigfloat off | goto label }
Well, except if (2^32 -N) is a power of 2, in which case it's off-by-1
//var %i 11111 , %c 0 | while (%i) { var %a $calc(2^32- %i ) , %base2 $base(%a,10,2) , %string2 $regsubex(%base2,^(1*),) | if ( $len(%string2) != $numbits(- $+ %a)) { inc %c | echo -a %a : $v1 vs $v2 %base2 $calc(2^32 - %a) } | dec %i } | echo -a fail %c
4294967040 : 8 vs 9 11111111111111111111111100000000 256 4294967168 : 7 vs 8 11111111111111111111111110000000 128 4294967232 : 6 vs 7 11111111111111111111111111000000 64 4294967264 : 5 vs 6 11111111111111111111111111100000 32 4294967280 : 4 vs 5 11111111111111111111111111110000 16 4294967288 : 3 vs 4 11111111111111111111111111111000 8 4294967292 : 2 vs 3 11111111111111111111111111111100 4 4294967294 : 1 vs 2 11111111111111111111111111111110 2 4294967295 : 0 vs 1 11111111111111111111111111111111 1
It seems logical that the correct behavior for negative N for doubles mode should mimic the $numbits($abs(-N)) from .bf mode, and I guess it's consistent behavior with the other bitwise operators for doubles mode to return $numbits(-N) = 1 and $numbits(N) = 32 when $abs(N) >= 2^32
|
|
|
|
Joined: Dec 2002
Posts: 5,490
Hoopy frood
|
Hoopy frood
Joined: Dec 2002
Posts: 5,490 |
I'm not saying that it's wrong for the .bf mode answer to be different than the doubles mode result when 1 term is negative, but that the result shouldn't be based on $abs(negative number) The bitwise bigfloat mode is most definitely different from non-bigfloat mode, eg. non-bigfloat is fixed at 32bit unsigned longs, whereas bigfloat is not fixed. I am pretty sure this was discussed. It also only handles positive values. If you use a negative value, it is $abs()'d. This is intentional. The non-bigfloat mode has always converted doubles to 32bit unsigned longs before applying standard bitwise operators, which can lead to overflows, etc. However, when I test using the negative numbers, I'm finding results that don't look correct, so I'm appealing to Talon on this one too. //echo -a $numbits(-1) %.bf $numbits(-1) result: 32 1 That looks fine and is how I wanted it to work. In the first case, -1 as an unsigned long is 32bits. In the second case, big float with no 'n' specified for the number of bits is one bit since it is $abs(-1). There are no plans to change how the bitwise operators in bigfloat mode work. If someone decides to add bitwise operators to the MAPM library natively, I may look into the above again, although by then the behaviour will be established so it may not make any sense to change it.
|
|
|
|
Joined: Jan 2004
Posts: 2,127
Hoopy frood
|
OP
Hoopy frood
Joined: Jan 2004
Posts: 2,127 |
Hrm, I don't remember discussing that bitwise should use $abs for $xor $and $or. There's a big difference between using -2 (make something be an even number) vs +2 (make something be 2 or 0), and I can't see any scripts finding the $not($abs(N1)) behavior useful.
//echo -a $and(255,-2) vs %null.bf $and(255,-2) $and(255,+2)
Rather than return an obviously wrong answer, I'm wondering if it's better to either require the 3rd 'bits' parameter be present when 1 term is negative for $and $or $xor (and when both terms are negative for $and $or), or to treat $xor(-N1,+N2) as invalid syntax in .bf mode.
Likewise, I'm not so sure that $not should have an implied bitmask that's based on the bit length of $abs(-N), since that assumes N always has the appropriate bit length.
//echo -a doubles $not(-9) $not(-17) vs $not(-9,8) $not(-17,8) bf %null.bf $not(-9) $not(-17) vs $not(-9,8) $not(-17,8)
In fact, the parm2 used by .bf mode looks like a useful feature for doubles mode instead of defaulting as $not(number,32)
|
|
|
|
Joined: Dec 2002
Posts: 5,490
Hoopy frood
|
Hoopy frood
Joined: Dec 2002
Posts: 5,490 |
//echo -a doubles $not(-9) $not(-17) vs $not(-9,8) $not(-17,8) This was already discussed :-] A second parameter was added to $not() for bigfloat because there is no way to know what the bit size is otherwise. If you don't specify the bit size, it is extrapolated from the number. You cannot use a second parameter in $not() for non-bigfloat. It doesn't do anything. The non-bigfloat bitwise operators all assume a 32bit unsigned long and wrap around negatives/overflows/etc. using strtoul() to perform the conversion. When we originally discussed this, it was decided that we only needed to add a bit size parameter to bigfloat $not(). None of the other bitwise identifiers know what the bit size is and extrapolate from the number, which is an arbitrary size bigfloat. In retrospect, the bigfloat bitwise operators should work in the same way as non-bigfloat when the bit size parameter is not specified, for backward compatibility. If a bit size is specified, they need to wrap negatives to unsigned (to match the long-established non-bigfloat behaviour) using the specified bit size, etc. These changes will be in the next beta.
|
|
|
|
|