On Sun, Jul 13, 2014 at 12:47 PM, David Feuer wrote:

ShiftRArithmetic x c = if (isSigned x) then shiftR x c else (-1 `shiftR` c) .|. (x `shiftR` c)

hmm... that isn't quite it because it will always add in the ones on the left when you only want to do it when the high bit is set, plus it assumes a specific representation for -1. John -- John Meacham - http://notanumber.net/

On Sun, Jul 13, 2014 at 1:33 PM, David Feuer wrote:

No, you're right about that. I'm not too clear on what a right shift of a negative number not represented with 2's complement is supposed to mean (or what any of these shifts should mean for a non-binary representation). And you're right that I missed a key test. One possibility is just to test the high order bit directly and test with that, and use the complement of 0 instead of -1.

Yeah, complement of zero would be better as removing dependencies on the 'Num' superclass is ideal. but 'high order bit' is tough to define, for instance 'Integer' is a member of bits, which is okay because it is specified to be treated as if it is sign extended to infinity for the purpose of bit ops, But any default refering to 'highest bit' wouldn't work. of course, bitSize already returns an error for Integer so perhaps this isn't making anything worse. (which also bugs me, bitSize should have returned a Maybe Int) John -- John Meacham - http://notanumber.net/

On Sun, Jul 13, 2014 at 2:23 PM, David Feuer wrote:

Well, bitSize is deprecated in favor of two safe alternatives, including finiteBitSize. It is unfortunate that the signed stuff in my default creates a Num dependency--that may be enough to kill it. The case of Integer is pretty peculiar. What do people use that instance for?

Infinite bit sets I guess, I don't think it is that unreasonable to exist, were it not for that pesky bitSize. FiniteBits and that deprecation are GHC specific. Though, it would make sense to port to jhc, it's fairly annoying for portable code to rely on ad-hoc changes like this. Looks like some work went into removing the Num superclass in ghc's base. Hmm... I think type class aliases are needed to actually make it backwards compatible though. Since bit is a primitive, you can get zero from the somewhat awkward 'clearBit 0 (bit 0)' and one from 'bit 1' and -1 from complement zero so the defaults that were dropped can be added back in using those. John -- John Meacham - http://notanumber.net/

Am 13.07.2014 23:50, schrieb David Feuer:

the specific thing that I was looking at just now was a Java implementation of isSquare that maaartinus wrote on StackOverflow that uses a masked shift to index into a (logical) bitvector by the six low-order bits of a (logical) integer to see if those bits can be the low-order bits of a perfect square.

Taking the six least-significant bits means modulo 64. There are 12 remainders of squares modulo 64: [0,1,4,9,16,17,25,33,36,41,49,57] I have run some tests in order to see whether there are divisors with especially small set of square remainders. A test based on this would require a full division but you can considerably increase the ratio of non-square remainders to square-remainders. Prelude> let sqrRems n = Data.Set.fromList $ map (\x -> mod (x*x) n) $ take n [0..] Prelude> Data.List.Key.maximum (uncurry (Data.Ratio.%)) $ map (\n -> (n, Data.Set.size $ sqrRems n)) [1..64] (48,8) Prelude> Data.List.Key.maximum (uncurry (Data.Ratio.%)) $ map (\n -> (n, Data.Set.size $ sqrRems n)) [1..1024] (1008,64) Prelude> Data.List.Key.maximum (uncurry (Data.Ratio.%)) $ map (\n -> (n, Data.Set.size $ sqrRems n)) [1..8192] (7920,288) That is, if you compute modulo 64, every 5th number will have a square remainder. In contrast to that, with modulo 7920 only every 27th number will have a remainder of a square. (Assuming the remainder of the tested numbers is equally distributed.)

On Sun, Jul 13, 2014 at 12:47 PM, David Feuer wrote:

They don't call error when given large counts; they give zero or -1. This is a pleasant property that we probably want to offer; it's just not (apparently) what CPUs tend to offer, and isn't always desirable.

Ah, excellent. I was thinking of an older implementation that errored out. John -- John Meacham - http://notanumber.net/

FWIW- this is actually the behavior for shiftL. It should just 'do the right thing' for over-shifting, in that it just keeps shifting, resulting in For shiftR we work that way, but there is apparently a cut and paste error in the haddocks that makes shiftR have the warning from unsafeShiftR that its behavior on overflow is undefined.

...

...

unsafeShiftR 1 1000000 :: Int

1 This stays put because 1000000 `mod` 64 = 0, while

...

...

shiftR 1 1000000 :: Int

0 saturates as you'd expect from:

...

...

unsafeShiftL 1 1000000 :: Int

1

...

...

shiftL 1 1000000 :: Int

0 The fact that we work modulo the integer size for unsafeShiftL/unsafeShiftR is very much platform specific though and its left deliberately unspecified, as the current unsafeShiftL and unsafeShiftR are intended for use in scenarios where the cost of the branch would be prohibitive, so over-constraining their implementation would be quite bad. The intention of the current specification should be that shiftR and shiftL just shift and keep on shifting even if you give a number that is too big, while unsafeShiftR and unsafeShiftL do undefined platform specific stuff when you give them a number out of range, usually this will be the modular shift that you get from the native instruction. This way you can use unsafeShiftL and unsafeShiftR when you know the argument is in range. We should definitely fix the documentation for shiftR though. That it claims to be undefined on over-shifting is just wrong. -Edward On Sun, Jul 13, 2014 at 3:50 PM, David Feuer wrote:

That may be reasonable. I think it likely makes more sense than making the type of shift depend on the type of number, anyway. On Jul 13, 2014 3:43 PM, "Henning Thielemann" < schlepptop@henning-thielemann.de> wrote:

...

Am 13.07.2014 20:36, schrieb David Feuer:

3. I would like to add explicit arithmetic and logical shifts to

...

Data.Bits. When fiddling bits, it's often easier to think about that distinction explicitly, rather than in terms of whether the type is signed or unsigned, and more convenient to have an explicit operation rather than casting around.

What kind of data do you have in mind, where both signed and unsigned shifts make sense?

So far, I'd say, that calling "asr" on Word and "lsr" on Int should be a type error.

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

On Sun, Jul 13, 2014 at 12:42 PM, Henning Thielemann wrote:

So far, I'd say, that calling "asr" on Word and "lsr" on Int should be a type error.

No, that would completely ruin the point of having them, the whole idea is being able to perform specifically an arithmetic or logical shift independent of the signedness of the underlying type. Signedness is a convention of how bit patterns are used, the underlying bit primitives actually implemented are independent of the language level conventions. It would make no more sense to call a type error on them than calling a type error on .&. and .|. on Word or Int. arithmetic shift may have the useful property that negative numbers are preserved when the bit patterns are interpreted as 2s complement numbers, but that is just a useful property, not a condition of use. Shifts are not numeric operations, they are bit operations like .&. and .|., they just happen to be able to be used to implement numeric operations in specific circumstances. John -- John Meacham - http://notanumber.net/

Without a type generic way to translate between 'IntN', 'CardN', and 'BitSetN' then that will be quite awkward to work with. Being able to perform logical shifts on unsigned numbers and arithmetic shifts on signed numbers is just extremely useful. The compiler is smart enough to transform div and mod power of two operations into bit operations so in general when you are explicitly using shiftR it is for their bit manipulation properties, not their correspondence to mod/div/mul. IntN/WordN are already specified to be 2s complement representations so these operations are well defined. In C you have to do awkward things like 'sign = -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));' to force the correct type of shift you want for a given arch. (right shift behavior is arch specific in C). John On Sun, Jul 13, 2014 at 1:55 PM, Henning Thielemann wrote:

Am 13.07.2014 22:42, schrieb John Meacham:

...

On Sun, Jul 13, 2014 at 12:42 PM, Henning Thielemann wrote:

...

So far, I'd say, that calling "asr" on Word and "lsr" on Int should be a type error.

No, that would completely ruin the point of having them, the whole idea is being able to perform specifically an arithmetic or logical shift independent of the signedness of the underlying type.

I'd prefer to distinguish between IntN, CardN (aka WordN) and BitSetN. IntN are signed integers, CardN are unsigned integers and BitSetN is a bit pattern without a numeric interpretation (flags, graphical patterns ...). IntN and CardN would be in a sub-class of Num that supports multiplication, division and modulo with powers of two, which can be efficiently implemented by shifts and bitwise Ands. BitSetN would support all kinds of logical and arithmetical shifts, shifts-through-carry, rotations, bit counts, bitwise logic and what know I.

Bit manipulation of numbers as provided by the Bits class was certainly not a good idea and will not become better by extending in that direction.

-- John Meacham - http://notanumber.net/

Am 13.07.2014 21:49, schrieb Eric Mertens:

I think defining the behavior of shifts to work modulo the bitSize is no better than leaving those ranges undefined. If we were going to define what it means to shift outside that range I'd rather it was somehow consistent with math multiplying and dividing by powers of two than randomly rolling over to a world where shifting a Word32 by 33 somehow corresponds to shifting by 1.

What he actually wants, is (x `testBit` mod n 64). I guess "rotate" is the better than "shift" here because "rotate" is naturally modular.