https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb#L684
https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb#L750
on Wed Jun 29 2016, Brent Royal-Gordon <swift-evolution@swift.org> wrote:
We might even be able to take the existing string-to-integer
logic, which I believe is duplicated for each type through GYB, and
share it in an extension so no Integer needs to write its own
conversion. Is that something that should be added?
--
Dave
Hi Nicola,
For these reasons, I think it would make sense to explicitly request that
the remainder operation never traps, and remove the overflow variants.
It will still trap when you divide by 0. But in that case falling back to the same generic overflow logic is not the best idea.
I agree that remainder is special, let me see what I can do about it.
Thanks,
Max
On Jun 23, 2016, at 2:38 PM, Nicola Salmoria via swift-evolution <swift-evolution@swift.org> wrote:
Max Moiseev via swift-evolution <swift-evolution@...> writes:
For FixedWidthInteger#dividedWithOverflow/remainderWithOverflow, under
what situations would
you have an overflow? I could only come up with something like
Int.min.dividedWithOverflow(-1).
If you look at the prototype here:
https://github.com/apple/swift/blob/master/test/Prototypes
/Integers.swift.gyb#L789there is
exactly the check that you’ve mentioned, but for all signed integers.Besides, it is very convenient to
have all the arithmetic operations be implemented the same way, even if
there were no real overflows for division.
I agree with this for the four basic operations, but not for the remainder
operation.By definition, the remainder is always strictly smaller (in absolute value)
than the divisor, so even if the division itself overflows, the remainder
must be representable, so technically it never overflow.In the only actual case where the division overflow, that is Int.min / -1,
the remainder is simply 0.For these reasons, I think it would make sense to explicitly request that
the remainder operation never traps, and remove the overflow variants.Nicola
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution
Um. I get that there are useful algorithms generic over floating-point vectors, and also useful algorithms generic over integer vectors. I’m still not sure what algorithms are generic over floating-point values (of any arity) and integers (of any arity).
Jordan
On Jun 23, 2016, at 15:19, Patrick Pijnappel <patrickpijnappel@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.
…except when taking a remainder dividing by 0, right?
Jordan
On Jun 23, 2016, at 14:38, Nicola Salmoria via swift-evolution <swift-evolution@swift.org> wrote:
Max Moiseev via swift-evolution <swift-evolution@...> writes:
For FixedWidthInteger#dividedWithOverflow/remainderWithOverflow, under
what situations would
you have an overflow? I could only come up with something like
Int.min.dividedWithOverflow(-1).
If you look at the prototype here:
https://github.com/apple/swift/blob/master/test/Prototypes
/Integers.swift.gyb#L789there is
exactly the check that you’ve mentioned, but for all signed integers.Besides, it is very convenient to
have all the arithmetic operations be implemented the same way, even if
there were no real overflows for division.
I agree with this for the four basic operations, but not for the remainder
operation.By definition, the remainder is always strictly smaller (in absolute value)
than the divisor, so even if the division itself overflows, the remainder
must be representable, so technically it never overflow.In the only actual case where the division overflow, that is Int.min / -1,
the remainder is simply 0.For these reasons, I think it would make sense to explicitly request that
the remainder operation never traps, and remove the overflow variants.
> 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@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@swift.org <mailto:swift-evolution@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@apple.com <mailto:jordan_rose@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\.
- 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@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution
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@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@gmail.com <mailto:patrickpijnappel@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@swift.org <mailto:swift-evolution@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@apple.com <mailto:jordan_rose@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\.
- 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@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution
I can't speak for anyone else, but I'd check the sign bit, return the correct answer if it's negative, and if not do an unsafeBitCast to the same-width unsigned type and use that to return the results of the homogeneous comparison.
There's probably a quicker way using some arcane bit-fiddling wizardry, but I don't know it off the top of my head.
- Dave Sweeris
On Jun 23, 2016, at 22:47, Félix Cloutier via swift-evolution <swift-evolution@swift.org> wrote:
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
Hi Nicola,
> For these reasons, I think it would make sense to explicitly request that
> the remainder operation never traps, and remove the overflow variants.
It will still trap when you divide by 0. But in that case falling back to
the same generic overflow logic is not the best idea.
I agree that remainder is special, let me see what I can do about it.
LOL, yes of course, I forgot about the obvious trapping case.
However, division by 0 isn't an overflow: it's an undefined operation. I
find it somewhat surprising that dividedWithOverflow/remainderWithOverflow
allow attempting this operation.
To me, the intuitive semantics of the WithOverflow methods are "perform the
operation, and if the result doesn't fit in the given type, return a
truncated result and an overflow flag". This is not what happens when
dividing by 0, because the result simply doesn't exist.
I think I would prefer if rhs != 0 was documented as an explicit
precondition of the division and remainder operations, and
dividedWithOverflow/remainderWithOverflow trapped because of precondition
failure.
If it is desirable that the WithOverflow methods never trap, then I think
it would be better to add a `divisionByZero` case to the ArithmeticOverflow
enum and return that instead of the generic `overflow`.
Thanks,
Nicola
On Fri, Jun 24, 2016 at 12:12 AM, Max Moiseev <moiseev@apple.com> wrote:
Thanks,
Max> On Jun 23, 2016, at 2:38 PM, Nicola Salmoria via swift-evolution < > swift-evolution@swift.org> wrote:
>
> Max Moiseev via swift-evolution <swift-evolution@...> writes:
>
>>> For FixedWidthInteger#dividedWithOverflow/remainderWithOverflow, under
> what situations would
>> you have an overflow? I could only come up with something like
> Int.min.dividedWithOverflow(-1).
>> If you look at the prototype here:
>>
> https://github.com/apple/swift/blob/master/test/Prototypes
> /Integers.swift.gyb#L789
>> there is
>> exactly the check that you’ve mentioned, but for all signed integers.
> Besides, it is very convenient to
>> have all the arithmetic operations be implemented the same way, even if
> there were no real overflows for division.
>
> I agree with this for the four basic operations, but not for the
remainder
> operation.
>
> By definition, the remainder is always strictly smaller (in absolute
value)
> than the divisor, so even if the division itself overflows, the remainder
> must be representable, so technically it never overflow.
>
> In the only actual case where the division overflow, that is Int.min /
-1,
> the remainder is simply 0.
>
> For these reasons, I think it would make sense to explicitly request that
> the remainder operation never traps, and remove the overflow variants.
>
> Nicola
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
On Fri, Jun 24, 2016 at 12:12 AM, Max Moiseev <moiseev@apple.com> wrote:
Hi Nicola,
> For these reasons, I think it would make sense to explicitly request that
> the remainder operation never traps, and remove the overflow variants.
It will still trap when you divide by 0. But in that case falling back to
the same generic overflow logic is not the best idea.
I agree that remainder is special, let me see what I can do about it.Thanks,
Max> On Jun 23, 2016, at 2:38 PM, Nicola Salmoria via swift-evolution < > swift-evolution@swift.org> wrote:
>
> Max Moiseev via swift-evolution <swift-evolution@...> writes:
>
>>> For FixedWidthInteger#dividedWithOverflow/remainderWithOverflow, under
> what situations would
>> you have an overflow? I could only come up with something like
> Int.min.dividedWithOverflow(-1).
>> If you look at the prototype here:
>>
> https://github.com/apple/swift/blob/master/test/Prototypes
> /Integers.swift.gyb#L789
>> there is
>> exactly the check that you’ve mentioned, but for all signed integers.
> Besides, it is very convenient to
>> have all the arithmetic operations be implemented the same way, even if
> there were no real overflows for division.
>
> I agree with this for the four basic operations, but not for the
remainder
> operation.
>
> By definition, the remainder is always strictly smaller (in absolute
value)
> than the divisor, so even if the division itself overflows, the remainder
> must be representable, so technically it never overflow.
>
> In the only actual case where the division overflow, that is Int.min /
-1,
> the remainder is simply 0.
>
> For these reasons, I think it would make sense to explicitly request that
> the remainder operation never traps, and remove the overflow variants.
>
> Nicola
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
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?
It is in the prototype: https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb#L334
On Jun 23, 2016, at 8:47 PM, Félix Cloutier <felixcca@yahoo.ca> wrote:
Félix
Le 23 juin 2016 à 17:36:14, Max Moiseev via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@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@gmail.com <mailto:patrickpijnappel@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@swift.org <mailto:swift-evolution@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@apple.com <mailto:jordan_rose@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\.
- 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@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution
As someone who’ll likely make use of this protocol, I’m in favor of a “halfWidthDivide” (or whatever it’s called). As someone who’ll likely end up writing at least one type which will conform to `Integer`, I’m not looking forward to implementing 503 little functions & computed properties (although I’ll admit it’ll be worth it to get a nice integer protocol). Is there any chance the protocol be able to provide default implementations for any of the “metadata” kind of stuff?
Also, speaking of default implementations, “wouldn’t it be nice if...” we only had to define everything explicitly for `IntN`, `UIntN` and `DoubleWidth<T>`, and the compiler was smart enough to figure out that, say, `DoubleWidth<Int8>` was semantically identical to `Int16` and would automatically promote it to the native type whenever possible… That way we wouldn’t need the .gyb files to write the code for all the integer types, *and* we wouldn’t have to pay the speed penalty for having, say, "func *(Int, Int)->Int" be the same code path as "func *(DoubleWidth<DoubleWidth<DoubleWidth<Int8>>>, DoubleWidth<DoubleWidth<DoubleWidth<Int8>>>) -> DoubleWidth<DoubleWidth<DoubleWidth<Int8>>>”, *and* we’d get arbitrary-width ints for free (well, “arbitrary” in terms of powers of 2).
- Dave Sweeris
On Jun 24, 2016, at 2:01 PM, Károly Lőrentey via swift-evolution <swift-evolution@swift.org> wrote:
The operation I want is the inverse of doubleWidthMultiply, where you have a (high, low) word pair and you want to divide it by a single word, getting a quotient and remainder. This is an important building block for implementing arbitrary precision division. Intel’s DIV can do this in a single instruction, while doing it in code requires a lot of work:
https://github.com/lorentey/BigInt/blob/swift3/Sources/BigDigit.swift#L119-L176
On 2016-06-24, at 20:52, Haravikk <swift-evolution@haravikk.me> wrote:
On 24 Jun 2016, at 18:17, Károly Lőrentey via swift-evolution <swift-evolution@swift.org> wrote:
I’m especially stoked about `FixedWidthInteger.doubleWidthMultiply`, which will likely lead to a measurable speedup. Why is there no `doubleWidthQuotientAndRemainder` or `doubleWidthDivide`, though?Double-width isn't needed for these as it's impossible for an integer to become larger when dividing (the smallest value you can divide by and get a result is 2, which will halve the value), and the remainder can't be larger than the original value.
Anyway, I'm hugely in favour of this proposal, it's desperately needed!
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution
> We might even be able to take the existing string-to-integer
> logic, which I believe is duplicated for each type through GYB, and
> share it in an extension so no Integer needs to write its own
> conversion. Is that something that should be added?https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb#L684
https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb#L750
This should probably all go through one generic String.init(_:radix:)
method, and we probably also want to have a generic Integer.init?(_:radix:)
initializer. I could submit a PR for those – I actually already have a
prototype implementation for the latter. Should these changes be included
in this SE proposal?
On Sat, Jul 2, 2016 at 10:08 AM, Dave Abrahams via swift-evolution < swift-evolution@swift.org> wrote:
on Wed Jun 29 2016, Brent Royal-Gordon <swift-evolution@swift.org> wrote:
> We might even be able to take the existing string-to-integer
> logic, which I believe is duplicated for each type through GYB, and
> share it in an extension so no Integer needs to write its own
> conversion. Is that something that should be added?https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb#L684
https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb#L750
--
Dave_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution
IIUC, the WithOverflow flag is only for the INT_MIN / -1 case. (And IIUC, that doesn't affect remainder.)
Jordan
On Jun 23, 2016, at 23:06, Nicola Salmoria via swift-evolution <swift-evolution@swift.org> wrote:
On Fri, Jun 24, 2016 at 12:12 AM, Max Moiseev <moiseev@apple.com <mailto:moiseev@apple.com>> wrote:
Hi Nicola,> For these reasons, I think it would make sense to explicitly request that
> the remainder operation never traps, and remove the overflow variants.
It will still trap when you divide by 0. But in that case falling back to the same generic overflow logic is not the best idea.
I agree that remainder is special, let me see what I can do about it.LOL, yes of course, I forgot about the obvious trapping case.
However, division by 0 isn't an overflow: it's an undefined operation. I find it somewhat surprising that dividedWithOverflow/remainderWithOverflow allow attempting this operation.
To me, the intuitive semantics of the WithOverflow methods are "perform the operation, and if the result doesn't fit in the given type, return a truncated result and an overflow flag". This is not what happens when dividing by 0, because the result simply doesn't exist.
I think I would prefer if rhs != 0 was documented as an explicit precondition of the division and remainder operations, and dividedWithOverflow/remainderWithOverflow trapped because of precondition failure.
If it is desirable that the WithOverflow methods never trap, then I think it would be better to add a `divisionByZero` case to the ArithmeticOverflow enum and return that instead of the generic `overflow`.
However, division by 0 isn't an overflow: it's an undefined operation. I find it somewhat surprising that dividedWithOverflow/remainderWithOverflow allow attempting this operation.
I tried to say that in my previous email. I agree that division by zero is NOT the overflow and should probably be handled differently if only for a better error message.
To me, the intuitive semantics of the WithOverflow methods are "perform the operation, and if the result doesn't fit in the given type, return a truncated result and an overflow flag". This is not what happens when dividing by 0, because the result simply doesn't exist.
I think I would prefer if rhs != 0 was documented as an explicit precondition of the division and remainder operations, and dividedWithOverflow/remainderWithOverflow trapped because of precondition failure.
That’s exactly how it is implemented in the prototype now.
If it is desirable that the WithOverflow methods never trap, then I think it would be better to add a `divisionByZero` case to the ArithmeticOverflow enum and return that instead of the generic `overflow`.
Nice idea, but I don’t think it is really required that WithOverflow methods should never fail. The main idea behind these methods is to allow for 2 versions of arithmetic operations: one that traps on overflow and an unsafe one, that simply discards the overflow flag returning the partial result. Both of these however should, in my opinion, trap in a truly exceptional case of division by 0.
Thanks for your comments, Nicola!
Max
On Jun 23, 2016, at 11:06 PM, Nicola Salmoria <nicola.salmoria@gmail.com> wrote:
On Fri, Jun 24, 2016 at 12:12 AM, Max Moiseev <moiseev@apple.com <mailto:moiseev@apple.com>> wrote:
Hi Nicola,> For these reasons, I think it would make sense to explicitly request that
> the remainder operation never traps, and remove the overflow variants.
It will still trap when you divide by 0. But in that case falling back to the same generic overflow logic is not the best idea.
I agree that remainder is special, let me see what I can do about it.LOL, yes of course, I forgot about the obvious trapping case.
However, division by 0 isn't an overflow: it's an undefined operation. I find it somewhat surprising that dividedWithOverflow/remainderWithOverflow allow attempting this operation.
To me, the intuitive semantics of the WithOverflow methods are "perform the operation, and if the result doesn't fit in the given type, return a truncated result and an overflow flag". This is not what happens when dividing by 0, because the result simply doesn't exist.
I think I would prefer if rhs != 0 was documented as an explicit precondition of the division and remainder operations, and dividedWithOverflow/remainderWithOverflow trapped because of precondition failure.
If it is desirable that the WithOverflow methods never trap, then I think it would be better to add a `divisionByZero` case to the ArithmeticOverflow enum and return that instead of the generic `overflow`.
Thanks,
NicolaThanks,
Max> On Jun 23, 2016, at 2:38 PM, Nicola Salmoria via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
>
> Max Moiseev via swift-evolution <swift-evolution@...> writes:
>
>>> For FixedWidthInteger#dividedWithOverflow/remainderWithOverflow, under
> what situations would
>> you have an overflow? I could only come up with something like
> Int.min.dividedWithOverflow(-1).
>> If you look at the prototype here:
>>
> https://github.com/apple/swift/blob/master/test/Prototypes
> /Integers.swift.gyb#L789
>> there is
>> exactly the check that you’ve mentioned, but for all signed integers.
> Besides, it is very convenient to
>> have all the arithmetic operations be implemented the same way, even if
> there were no real overflows for division.
>
> I agree with this for the four basic operations, but not for the remainder
> operation.
>
> By definition, the remainder is always strictly smaller (in absolute value)
> than the divisor, so even if the division itself overflows, the remainder
> must be representable, so technically it never overflow.
>
> In the only actual case where the division overflow, that is Int.min / -1,
> the remainder is simply 0.
>
> For these reasons, I think it would make sense to explicitly request that
> the remainder operation never traps, and remove the overflow variants.
>
> Nicola
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org <mailto:swift-evolution@swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolutionOn Fri, Jun 24, 2016 at 12:12 AM, Max Moiseev <moiseev@apple.com <mailto:moiseev@apple.com>> wrote:
Hi Nicola,> For these reasons, I think it would make sense to explicitly request that
> the remainder operation never traps, and remove the overflow variants.
It will still trap when you divide by 0. But in that case falling back to the same generic overflow logic is not the best idea.
I agree that remainder is special, let me see what I can do about it.Thanks,
Max> On Jun 23, 2016, at 2:38 PM, Nicola Salmoria via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
>
> Max Moiseev via swift-evolution <swift-evolution@...> writes:
>
>>> For FixedWidthInteger#dividedWithOverflow/remainderWithOverflow, under
> what situations would
>> you have an overflow? I could only come up with something like
> Int.min.dividedWithOverflow(-1).
>> If you look at the prototype here:
>>
> https://github.com/apple/swift/blob/master/test/Prototypes
> /Integers.swift.gyb#L789
>> there is
>> exactly the check that you’ve mentioned, but for all signed integers.
> Besides, it is very convenient to
>> have all the arithmetic operations be implemented the same way, even if
> there were no real overflows for division.
>
> I agree with this for the four basic operations, but not for the remainder
> operation.
>
> By definition, the remainder is always strictly smaller (in absolute value)
> than the divisor, so even if the division itself overflows, the remainder
> must be representable, so technically it never overflow.
>
> In the only actual case where the division overflow, that is Int.min / -1,
> the remainder is simply 0.
>
> For these reasons, I think it would make sense to explicitly request that
> the remainder operation never traps, and remove the overflow variants.
>
> Nicola
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org <mailto:swift-evolution@swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolution
Okay, well, I'm +1 on this. I like that we got rid of conversions from/to U/IntMax in favor of more general initializers and the bitshift enhancements. I think that most generic algorithms on integers will get simpler.
I'm not overly concerned/competent with floating-point numbers, but I'm sure that the people here will nitpick every last wrinkle that there could be.
Félix
Le 24 juin 2016 à 14:34:37, Max Moiseev <moiseev@apple.com> a écrit :
On Jun 23, 2016, at 8:47 PM, Félix Cloutier <felixcca@yahoo.ca <mailto:felixcca@yahoo.ca>> wrote:
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?
It is in the prototype: https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb#L334
Félix
Le 23 juin 2016 à 17:36:14, Max Moiseev via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@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@gmail.com <mailto:patrickpijnappel@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@swift.org <mailto:swift-evolution@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@apple.com <mailto:jordan_rose@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\.
- 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@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution
> We might even be able to take the existing string-to-integer
> logic, which I believe is duplicated for each type through GYB, and
> share it in an extension so no Integer needs to write its own
> conversion. Is that something that should be added?
https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb#L684
https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb#L750This should probably all go through one generic String.init(_:radix:) method, and we probably also want to have a generic Integer.init?(_:radix:) initializer. I could submit a PR for those – I actually already have a prototype implementation for the latter. Should these changes be included in this SE proposal?
Sounds like it to me
On Jul 1, 2016, at 9:18 PM, Patrick Pijnappel <patrickpijnappel@gmail.com> wrote:
On Sat, Jul 2, 2016 at 10:08 AM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:
on Wed Jun 29 2016, Brent Royal-Gordon <swift-evolution@swift.org> wrote:
> We might even be able to take the existing string-to-integer
> logic, which I believe is duplicated for each type through GYB, and
> share it in an extension so no Integer needs to write its own
> conversion. Is that something that should be added?https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb#L684
https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb#L750--
Dave_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution
Sent from my moss-covered three-handled family gradunza
However, division by 0 isn't an overflow: it's an undefined operation. I
find it somewhat surprising that dividedWithOverflow/remainderWithOverflow
allow attempting this operation.I tried to say that in my previous email. I agree that division by zero is
NOT the overflow and should probably be handled differently if only for a
better error message.To me, the intuitive semantics of the WithOverflow methods are "perform
the operation, and if the result doesn't fit in the given type, return a
truncated result and an overflow flag". This is not what happens when
dividing by 0, because the result simply doesn't exist.I think I would prefer if rhs != 0 was documented as an explicit
precondition of the division and remainder operations, and
dividedWithOverflow/remainderWithOverflow trapped because of precondition
failure.That’s exactly how it is implemented in the prototype now.
Now I'm confused. Isn't this line of the gyb returning .overflow when the
divisor is 0?
https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb#L793
Also, the current version of Swift doesn't trap either:
let z = 0
print(Int.divideWithOverflow(1, z)) // (0, true)
print(Int.remainderWithOverflow(1, z)) // (0, true)
interestingly, you need to put 0 in a variable otherwise the compiler
rejects the lines.
If it is desirable that the WithOverflow methods never trap, then I think
it would be better to add a `divisionByZero` case to the ArithmeticOverflow
enum and return that instead of the generic `overflow`.Nice idea, but I don’t think it is really required that WithOverflow
methods should never fail. The main idea behind these methods is to allow
for 2 versions of arithmetic operations: one that traps on overflow and an
unsafe one, that simply discards the overflow flag returning the partial
result. Both of these however should, in my opinion, trap in a truly
exceptional case of division by 0.
That would be my preference too. Thanks!
Nicola
On Fri, Jun 24, 2016 at 11:45 PM, Max Moiseev <moiseev@apple.com> wrote:
Thanks for your comments, Nicola!
Max
On Jun 23, 2016, at 11:06 PM, Nicola Salmoria <nicola.salmoria@gmail.com> > wrote:
On Fri, Jun 24, 2016 at 12:12 AM, Max Moiseev <moiseev@apple.com> wrote:
Hi Nicola,
> For these reasons, I think it would make sense to explicitly request
that
> the remainder operation never traps, and remove the overflow variants.
It will still trap when you divide by 0. But in that case falling back to
the same generic overflow logic is not the best idea.
I agree that remainder is special, let me see what I can do about it.LOL, yes of course, I forgot about the obvious trapping case.
However, division by 0 isn't an overflow: it's an undefined operation. I
find it somewhat surprising that dividedWithOverflow/remainderWithOverflow
allow attempting this operation.To me, the intuitive semantics of the WithOverflow methods are "perform
the operation, and if the result doesn't fit in the given type, return a
truncated result and an overflow flag". This is not what happens when
dividing by 0, because the result simply doesn't exist.I think I would prefer if rhs != 0 was documented as an explicit
precondition of the division and remainder operations, and
dividedWithOverflow/remainderWithOverflow trapped because of precondition
failure.If it is desirable that the WithOverflow methods never trap, then I think
it would be better to add a `divisionByZero` case to the ArithmeticOverflow
enum and return that instead of the generic `overflow`.Thanks,
NicolaThanks,
Max> On Jun 23, 2016, at 2:38 PM, Nicola Salmoria via swift-evolution < >> swift-evolution@swift.org> wrote:
>
> Max Moiseev via swift-evolution <swift-evolution@...> writes:
>
>>> For FixedWidthInteger#dividedWithOverflow/remainderWithOverflow, under
> what situations would
>> you have an overflow? I could only come up with something like
> Int.min.dividedWithOverflow(-1).
>> If you look at the prototype here:
>>
> https://github.com/apple/swift/blob/master/test/Prototypes
> /Integers.swift.gyb#L789
>> there is
>> exactly the check that you’ve mentioned, but for all signed integers.
> Besides, it is very convenient to
>> have all the arithmetic operations be implemented the same way, even if
> there were no real overflows for division.
>
> I agree with this for the four basic operations, but not for the
remainder
> operation.
>
> By definition, the remainder is always strictly smaller (in absolute
value)
> than the divisor, so even if the division itself overflows, the
remainder
> must be representable, so technically it never overflow.
>
> In the only actual case where the division overflow, that is Int.min /
-1,
> the remainder is simply 0.
>
> For these reasons, I think it would make sense to explicitly request
that
> the remainder operation never traps, and remove the overflow variants.
>
> Nicola
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolutionOn Fri, Jun 24, 2016 at 12:12 AM, Max Moiseev <moiseev@apple.com> wrote:
Hi Nicola,
> For these reasons, I think it would make sense to explicitly request
that
> the remainder operation never traps, and remove the overflow variants.
It will still trap when you divide by 0. But in that case falling back to
the same generic overflow logic is not the best idea.
I agree that remainder is special, let me see what I can do about it.Thanks,
Max> On Jun 23, 2016, at 2:38 PM, Nicola Salmoria via swift-evolution < >> swift-evolution@swift.org> wrote:
>
> Max Moiseev via swift-evolution <swift-evolution@...> writes:
>
>>> For FixedWidthInteger#dividedWithOverflow/remainderWithOverflow, under
> what situations would
>> you have an overflow? I could only come up with something like
> Int.min.dividedWithOverflow(-1).
>> If you look at the prototype here:
>>
> https://github.com/apple/swift/blob/master/test/Prototypes
> /Integers.swift.gyb#L789
>> there is
>> exactly the check that you’ve mentioned, but for all signed integers.
> Besides, it is very convenient to
>> have all the arithmetic operations be implemented the same way, even if
> there were no real overflows for division.
>
> I agree with this for the four basic operations, but not for the
remainder
> operation.
>
> By definition, the remainder is always strictly smaller (in absolute
value)
> than the divisor, so even if the division itself overflows, the
remainder
> must be representable, so technically it never overflow.
>
> In the only actual case where the division overflow, that is Int.min /
-1,
> the remainder is simply 0.
>
> For these reasons, I think it would make sense to explicitly request
that
> the remainder operation never traps, and remove the overflow variants.
>
> Nicola
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
Huh. My bad for not checking. Yeah, I don't think dividing by zero and dividing INT_MIN by -1 are the same kind of overflow.
Jordan
On Jun 24, 2016, at 15:03, Nicola Salmoria via swift-evolution <swift-evolution@swift.org> wrote:
On Fri, Jun 24, 2016 at 11:45 PM, Max Moiseev <moiseev@apple.com <mailto:moiseev@apple.com>> wrote:
However, division by 0 isn't an overflow: it's an undefined operation. I find it somewhat surprising that dividedWithOverflow/remainderWithOverflow allow attempting this operation.
I tried to say that in my previous email. I agree that division by zero is NOT the overflow and should probably be handled differently if only for a better error message.
To me, the intuitive semantics of the WithOverflow methods are "perform the operation, and if the result doesn't fit in the given type, return a truncated result and an overflow flag". This is not what happens when dividing by 0, because the result simply doesn't exist.
I think I would prefer if rhs != 0 was documented as an explicit precondition of the division and remainder operations, and dividedWithOverflow/remainderWithOverflow trapped because of precondition failure.
That’s exactly how it is implemented in the prototype now.
Now I'm confused. Isn't this line of the gyb returning .overflow when the divisor is 0?
https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb#L793Also, the current version of Swift doesn't trap either:
let z = 0
print(Int.divideWithOverflow(1, z)) // (0, true)
print(Int.remainderWithOverflow(1, z)) // (0, true)interestingly, you need to put 0 in a variable otherwise the compiler rejects the lines.
Now I'm confused. Isn't this line of the gyb returning .overflow when the divisor is 0?
https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb#L793
Sorry. What I meant was “this is how it’s documented”. Not dividing by zero is a precondition.
Also, the current version of Swift doesn't trap either:
let z = 0
print(Int.divideWithOverflow(1, z)) // (0, true)
print(Int.remainderWithOverflow(1, z)) // (0, true)
https://github.com/apple/swift/blob/master/stdlib/public/core/FixedPoint.swift.gyb#L399
Well, then we’ll be fixing it :-)
interestingly, you need to put 0 in a variable otherwise the compiler rejects the lines.
FWIW: Works in the Swift 3 compiler.
On Jun 24, 2016, at 3:03 PM, Nicola Salmoria <nicola.salmoria@gmail.com> wrote:
On Fri, Jun 24, 2016 at 11:45 PM, Max Moiseev <moiseev@apple.com <mailto:moiseev@apple.com>> wrote:
However, division by 0 isn't an overflow: it's an undefined operation. I find it somewhat surprising that dividedWithOverflow/remainderWithOverflow allow attempting this operation.
I tried to say that in my previous email. I agree that division by zero is NOT the overflow and should probably be handled differently if only for a better error message.
To me, the intuitive semantics of the WithOverflow methods are "perform the operation, and if the result doesn't fit in the given type, return a truncated result and an overflow flag". This is not what happens when dividing by 0, because the result simply doesn't exist.
I think I would prefer if rhs != 0 was documented as an explicit precondition of the division and remainder operations, and dividedWithOverflow/remainderWithOverflow trapped because of precondition failure.
That’s exactly how it is implemented in the prototype now.
Now I'm confused. Isn't this line of the gyb returning .overflow when the divisor is 0?
https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb#L793Also, the current version of Swift doesn't trap either:
let z = 0
print(Int.divideWithOverflow(1, z)) // (0, true)
print(Int.remainderWithOverflow(1, z)) // (0, true)interestingly, you need to put 0 in a variable otherwise the compiler rejects the lines.
If it is desirable that the WithOverflow methods never trap, then I think it would be better to add a `divisionByZero` case to the ArithmeticOverflow enum and return that instead of the generic `overflow`.
Nice idea, but I don’t think it is really required that WithOverflow methods should never fail. The main idea behind these methods is to allow for 2 versions of arithmetic operations: one that traps on overflow and an unsafe one, that simply discards the overflow flag returning the partial result. Both of these however should, in my opinion, trap in a truly exceptional case of division by 0.
That would be my preference too. Thanks!
Nicola
Thanks for your comments, Nicola!
Max
On Jun 23, 2016, at 11:06 PM, Nicola Salmoria <nicola.salmoria@gmail.com <mailto:nicola.salmoria@gmail.com>> wrote:
On Fri, Jun 24, 2016 at 12:12 AM, Max Moiseev <moiseev@apple.com <mailto:moiseev@apple.com>> wrote:
Hi Nicola,> For these reasons, I think it would make sense to explicitly request that
> the remainder operation never traps, and remove the overflow variants.
It will still trap when you divide by 0. But in that case falling back to the same generic overflow logic is not the best idea.
I agree that remainder is special, let me see what I can do about it.LOL, yes of course, I forgot about the obvious trapping case.
However, division by 0 isn't an overflow: it's an undefined operation. I find it somewhat surprising that dividedWithOverflow/remainderWithOverflow allow attempting this operation.
To me, the intuitive semantics of the WithOverflow methods are "perform the operation, and if the result doesn't fit in the given type, return a truncated result and an overflow flag". This is not what happens when dividing by 0, because the result simply doesn't exist.
I think I would prefer if rhs != 0 was documented as an explicit precondition of the division and remainder operations, and dividedWithOverflow/remainderWithOverflow trapped because of precondition failure.
If it is desirable that the WithOverflow methods never trap, then I think it would be better to add a `divisionByZero` case to the ArithmeticOverflow enum and return that instead of the generic `overflow`.
Thanks,
NicolaThanks,
Max> On Jun 23, 2016, at 2:38 PM, Nicola Salmoria via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
>
> Max Moiseev via swift-evolution <swift-evolution@...> writes:
>
>>> For FixedWidthInteger#dividedWithOverflow/remainderWithOverflow, under
> what situations would
>> you have an overflow? I could only come up with something like
> Int.min.dividedWithOverflow(-1).
>> If you look at the prototype here:
>>
> https://github.com/apple/swift/blob/master/test/Prototypes
> /Integers.swift.gyb#L789
>> there is
>> exactly the check that you’ve mentioned, but for all signed integers.
> Besides, it is very convenient to
>> have all the arithmetic operations be implemented the same way, even if
> there were no real overflows for division.
>
> I agree with this for the four basic operations, but not for the remainder
> operation.
>
> By definition, the remainder is always strictly smaller (in absolute value)
> than the divisor, so even if the division itself overflows, the remainder
> must be representable, so technically it never overflow.
>
> In the only actual case where the division overflow, that is Int.min / -1,
> the remainder is simply 0.
>
> For these reasons, I think it would make sense to explicitly request that
> the remainder operation never traps, and remove the overflow variants.
>
> Nicola
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org <mailto:swift-evolution@swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolutionOn Fri, Jun 24, 2016 at 12:12 AM, Max Moiseev <moiseev@apple.com <mailto:moiseev@apple.com>> wrote:
Hi Nicola,> For these reasons, I think it would make sense to explicitly request that
> the remainder operation never traps, and remove the overflow variants.
It will still trap when you divide by 0. But in that case falling back to the same generic overflow logic is not the best idea.
I agree that remainder is special, let me see what I can do about it.Thanks,
Max> On Jun 23, 2016, at 2:38 PM, Nicola Salmoria via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
>
> Max Moiseev via swift-evolution <swift-evolution@...> writes:
>
>>> For FixedWidthInteger#dividedWithOverflow/remainderWithOverflow, under
> what situations would
>> you have an overflow? I could only come up with something like
> Int.min.dividedWithOverflow(-1).
>> If you look at the prototype here:
>>
> https://github.com/apple/swift/blob/master/test/Prototypes
> /Integers.swift.gyb#L789
>> there is
>> exactly the check that you’ve mentioned, but for all signed integers.
> Besides, it is very convenient to
>> have all the arithmetic operations be implemented the same way, even if
> there were no real overflows for division.
>
> I agree with this for the four basic operations, but not for the remainder
> operation.
>
> By definition, the remainder is always strictly smaller (in absolute value)
> than the divisor, so even if the division itself overflows, the remainder
> must be representable, so technically it never overflow.
>
> In the only actual case where the division overflow, that is Int.min / -1,
> the remainder is simply 0.
>
> For these reasons, I think it would make sense to explicitly request that
> the remainder operation never traps, and remove the overflow variants.
>
> Nicola
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org <mailto:swift-evolution@swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolution