[swift-evolution] [swift-evolution-announce] [Review] SE-0104: Protocol-oriented integers

Félix Cloutier felixcca at yahoo.ca
Thu Jun 23 22:47:18 CDT 2016


Thanks for answering my questions earlier. I like a lot of the changes.

Speaking of heterogeneous comparisons again, though, how are comparisons of negative signed integers with unsigned integers handled?

Félix

> Le 23 juin 2016 à 17:36:14, Max Moiseev via swift-evolution <swift-evolution at swift.org> a écrit :
> 
>> > For Integer, does the presence of signBit indicate an expectation that signed Integers will have a two's complement representation?
>> Yes. That is correct.
>> 
>> So would this require a BigInt implementation to be in two's complement also? Most BigInt implementations use a separate sign I think, not sure if that's for performance reasons or merely convenience though.
> 
> 
> This is a very valid concern. I think I have discovered a truly marvelous solution a way of addressing it:
> 
> `signBitIndex` is only used (I’m talking about the prototype now) to determine the absolute required minimum of bits needed to represent the current value of number when converting it to a different type.
> 
> So, instead of mentioning the sign bit, let’s call it what it is ‘minimumRequiredWidth’ or something along this line. This move will also allow the default implementation of `minimumRequiredWidth` to simply return `bitWidth` for unsigned numbers and and `bitWidth - 1` for positive signed, etc.
> 
> This way bignum implementations don’t have to have any specific underlying representation. They can either inherit the default implementation or implement their own version of `minimumRequiredWidth` in case the `bitWidth` has some extra unused space that is not absolutely required.
> 
> I still need to validate this idea, these are just the thoughts. Any comments are more than welcome.
> 
> Max
> 
> 
>> On Jun 23, 2016, at 3:19 PM, Patrick Pijnappel <patrickpijnappel at gmail.com <mailto:patrickpijnappel at gmail.com>> wrote:
>> 
>> - I remain unconvinced that defining an Arithmetic that includes both exact and floating-point numbers is a good idea. All of the arguments from Swift 1 and 2 about why we didn't include this still seem relevant. To phrase it in generic programming terms, what algorithm would be generic over Arithmetic?
>> 
>> E.g. generic point/size/rect types.
>> 
>> > For Integer, does the presence of signBit indicate an expectation that signed Integers will have a two's complement representation?
>> Yes. That is correct.
>> 
>> So would this require a BigInt implementation to be in two's complement also? Most BigInt implementations use a separate sign I think, not sure if that's for performance reasons or merely convenience though.
>> 
>> 
>> On Fri, Jun 24, 2016 at 7:40 AM, Jordan Rose via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>> Oh, one more comment: I suggest naming the primary protocol something other than "Integer", which IMHO is a little close to "Int" for a beginner. "Integral" is a bit too ambiguous, but maybe "IntegerArithmetic" or "ArithmeticInteger"? Or to go with the representation thing, "BinaryInteger"? (Some of the requirements are at odds with a decimal-based implementation.)
>> 
>> Jordan
>> 
>> 
>>> On Jun 23, 2016, at 13:50, Jordan Rose <jordan_rose at apple.com <mailto:jordan_rose at apple.com>> wrote:
>>> 
>>> Hey, standard library folks. Glad we're doing this one. :-)
>>> 
>>> - I remain unconvinced that defining an Arithmetic that includes both exact and floating-point numbers is a good idea. All of the arguments from Swift 1 and 2 about why we didn't include this still seem relevant. To phrase it in generic programming terms, what algorithm would be generic over Arithmetic?
>>> 
>>> 
>>> - What is Integer.init<T: FloatingPoint>(_:) supposed to do if the floating-point value is larger than the maximum representable integer? Smaller than the minimum? (As a special case, negative, when the integer type is unsigned?) Infinity? NaN?
>>> 
>>> - Integer.init<T: Integer>(_:) currently says "if it is representable". It should say something like "trapping if it is not representable".
>>> 
>>> - I find it odd that Integer.init(clamping:) privileges the bounds of fixed-width integers. I was going to suggest it should take a range to clamp to that defaults to the min and max, but that's not implementable for a BigInt.
>>> 
>>> - nthWord should count "from least-significant to most-significant" rather than "from the right".
>>> 
>>> - As mentioned before, it sounds like Integer requires a two's complement representation (if only so the result of nthWord can be interpreted correctly). That should probably be in the doc comment for the protocol.
>>> 
>>> - Why is bitWidth in bits but nthWord in words? (I know there's a good answer to this, but using them together seems like it will be common.)
>>> 
>>> - It's also probably worth calling out even more explicitly that bitWidth is a representation property, not a value property. That is, a BigInt with the value "1" could have a bitWidth of 1, 8, or 128.
>>> 
>>> - What does signBitIndex return if self is positive? I ask because it's just not in the doc comment, but thinking about the answer made it obvious that the correct return value for 0 is 0.
>>> 
>>> - For signed integers, does remainder(dividingBy:) have specified behavior for the sign of the result? See https://en.wikipedia.org/wiki/Modulo_operation <https://en.wikipedia.org/wiki/Modulo_operation>.
>>> 
>>> - I do think having Swift.abs(_:) and Integer.absoluteValue is confusing, but I don't know what to do about it.
>>> 
>>> 
>>> - Why are bitwise operations limited to fixed-width integers? I see "The only difference is that because shifting left truncates the high bits of fixed-width integers, it is hard to define what a left shift would mean to an arbitrary-precision integer" further down, but I would just assume it wouldn't truncate (i.e. it would be a pure multiplication by two).
>>> 
>>> - Is there a requirement about left-shifting into the sign bit, for '<<' and for '&<<'?
>>> 
>>> - What is the ArithmeticOverflow type?
>>> 
>>> - When does the remainder operation overflow? (I just can't remember.)
>>> 
>>> - I feel a little weird having "someValue.and(mask)". Maybe bitwiseAnd or bitwiseAND to be more explicit?
>>> 
>>> - maskingShiftLeft/Right seem underspecified in their doc comments. Why can't the protocol requirement just assume the shift amount has already been masked, instead of performing the masking themselves? Is it because we won't be able to optimize that away?
>>> 
>>> I think that's about it. Great work, all!
>>> Jordan
>> 
>> 
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
>> https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>
>> 
>> 
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160623/81005bb2/attachment.html>


More information about the swift-evolution mailing list