Even and Odd Integers

Evolution Pitches
83

I've put together a draft proposal for adding isEven, isOdd, and isDivisible to the BinaryInteger protocol. Feedback is always welcome. I'm sure I've absorbed many ideas and examples from the pitch thread by osmosis, so if you feel like you'd like to be included as an author please send me a message and I'll add you.

https://github.com/robmaceachern/swift-evolution/blob/binaryinteger-iseven-isodd/proposals/nnnn-binaryinteger-iseven-isodd-isdivisible.md

After re-reading some of the replies in the pitch thread I decided to include isDivisible in the proposal. There are still some aspects to it that should be discussed:

Signature: How does this look to everyone?

func isDivisible(by denominator: Self) -> Bool

Zeros: What should 12.isDivisible(by: 0) do: trap or return false? Clearly division by zero is undefined, but is divisibility by zero undefined too? I suppose it depends on the precise definition of divisibility.

The Wolfram web console reports an error when the second argument to Divisible[n,m] is zero.

Is 0.isDivisible(by: 0) a special case?

Implementation: Is there a better BinaryInteger implementation than this? (assuming trapping on zero is acceptable)

func isDivisible(by denominator: Self) -> Bool {
    return self % denominator == 0
}
7 Likes
84

Nit: should be isDivisible(by divisor: Self). A denominator is the bottom of a fraction, divisor is the thing you divide by. These are closely related, but different, and divisor is consistently used in the stdlib.

Otherwise this seems like a good start.

3 Likes
85

Thanks Steve. I originally had it divisor but it seems to be a bit of an overloaded term in the context of division and divisibility.

Wikipedia's definition of divisor (related to divisibility): "In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n."

86

If we wanted to be really explicit and avoid ambiguity, I would use something like trialDivisor or candidateDivisor. Ultimately it doesn't matter too much, since the actual label is by:.

2 Likes
87

I believe it should return false based on the common definition of divisibility (whether there exists an integer such that multiplying it by your divisor equals your number). It is a question of existence (in this case it does not exist) as opposed to value.

88

All right, x.isDivisible(by: 0) is false.

And 0.isDivisible(by: x) is true: zero itself is the integer such that multiplying it by the divisor x equals zero.

And now we don't quite know what to do with 0.isDivisible(by: 0), which should be both true and false according to our two general rules.

On such limit points, it can be useful to conventionally choosing one value instead of deciding that the value is undefined. I'd prefer 0.isDivisible(by: 0) to return true: that is because 0 as a divisor looks like a code smell, and because I don't want it to trap. I thus prefer to apply the "0.isDivisible(by: x) is true" rule.

If mathematicians agree, or at least don't roll their eyes, it's even safer to use this convention.

89

There is no conflict. 0.isDivisible(by:0) is true because there exists an integer k, such that k*0 = 0.

Zero is the only value which is divisible by zero because there isn't a k such that k*0 = x when x≠0.

1 Like
90

Glad we come to the same conclusion by two different ways. Yours is certainly shorter :-)

91

Division is commonly understood to refer to the inverse of multiplication. Therefore, technically m / n should be a valid operation if and only if m is divisible by n. In the case of most programming languages, this is not true because / is defined as truncating division on integers, but that's not consistent with the mathematical point of view.

92

The usual formal mathematics definition of "divisible" is:

If a and b are integers with a≠0, then we say a divides b if there exists an integer k such that b = ka.

So formally one could argue that anything.isDivisible(by: 0) should be a precondition failure. I would also be OK with returning false, however, especially if there's a pragmatic argument where it makes some real code easier to write.

1 Like
93

There's definitely different conventions here, some authors would allow for divisibility by zero to be defined: [1], [2], but see also [3], [4].

It's very common in mathematics that trivial and uninteresting cases are not given special consideration or treated differently by different authors (mathematicians can't even agree whether 0 is a natural number, so...).

From a pragmatic point of view, I wouldn't want a stdlib function to trap without very good reason; so returning false (edit: except 0.isDivisible(by: 0)) would seem preferable.

1 Like
94

With an exception for 0.isDivisible(by: 0), right?

95

yes of course, sorry

96

Is throwing an option here? It seems like throwing a divisionByZero error allows the library to be clear and for people do do as they would like.

97

The problem with this is that now every single call to int.isDivisble(by: num) would require a try when there is only a single instance where it could throw and I wouldn't be surprised if most code that checks divisibility is already checking that the divisor != 0. So there would probably end up being a lot of code that just checks if the divisor is zero first, then uses try! instead.

I think that returning false (except for 0.isDivisible(by: 0)) is acceptable behavior.

5 Likes
98

That… seems like throwing would combine the two things in a not so terrible way.

99

You do have a point, though behavior in the stdlib is not to just throw during math operations, but trap with fatalError on division by zero.

Which is why I believe that the only options discussed were whether or not to trap. This is basically just sugar for the % operator and then testing if the result == 0. If we made this throw, then why not make % or / throwing operations as well?

It is an option that we could probably debate, but IMO returning false is accurate enough to be my preferred choice since it doesn't require the try keyword.

100

If most code would check anyway, and there's no good use case to be argued for which not trapping would be convenient, then isDivisible(by:) should trap on attempted division by zero just like any other attempt to divide an integer by zero, in my view.

1 Like
101

Is it obvious, though, that a method called isDivisible(by:) actually performs division? If the method returned false instead, it would allow writing code such as

if x.isDivisible(by: y) { ... }

without having to also check that y != 0.

I don't think this would be incorrect at all, as obviously a non-zero X is not divisible by zero, even if the reason is different than for other integer values.

2 Likes
102

[Theory part:]
So the issue here is that there exists a theorem:

If a, k, m, n are integers, k != 0 and a = km, a = kn, then m and n are equal.

This is obviously false if k = 0, e.g. 0 = 0 * 3, 0 = 0 * 4. And the relations a = km, a = kn can be rephrased as "a is divisible by k". This leads to the following theorem:

If a, k are integers, k != 0 and k divides a, there exists a unique integer m = a/k that solves the equation a = km.

This actually is what allows us to define division on integers: it's an operation that always has either no solution or a single solution, unless the divisor is zero. The reason why some authors will disallow that 0 divides 0 is that then this second theorem could be restated without the condition k != 0; so it's a pure technicality.

[Practical part:]
What this means in practical terms though is that if somebody were to write:

if x.isDivisible(by: y) { return x / y } else { return nil }

(which looks totally reasonable at first sight), then this code will trap if x and y are both 0, if we define isDivisible the way I previously suggested. The issue is here that the person writing this code implicitly used a theorem (see above) without checking for an additional condition, namely that y != 0. The correct code would be:

if y != 0, x.isDivisible(by: y) { return x / y } else { return nil }

This leads to the following options for the implementation of isDivisible:

  1. define the method such that it always returns a Bool. The burden of not using mathematical theorems without checking all the conditions would lie on the code author's side.
  2. trap when encountering y = 0. But, at least for this situation, this has zero benefits over trapping in the user code. Additionally, while division by zero must trap (because it's directly handled by the CPU), divisibility, when implemented in library code, has no such technical requirement; therefore this option makes little sense to me
  3. don't trap, but still keep the function partial. whether this is done by returning Bool? or by using throws can be debated on a basis of ergonomics, but has the same implications semantically. this has the advantage of forcing the user to explicitly handle the zero divisor case (therefore the above code couldn't trap), but it also makes a function, which is supposedly basic, awkward to use (I think it's kind of hard to explain why isDivisible(by:) should return an optional or throw).

Since I would rule out 2, this leaves options 1 and 3. I'm more partial towards 1 (it makes the definition of the function neater), but one could argue for option 3 too in the interest of safety.

1 Like