Even and Odd Integers

The good, bad, and ugly of Swift Evolution. (;

1 Like

I honestly wish nil was falsey like other languages. Python treats None as falsey, ruby treats nil, etc.

But this is a discussion for a separate time, which has probably already been had...

Perhaps, but not for the purpose of evaluating whether a number is odd or even. Use modulo when you need to split a table or get remainders; that's what it's useful for.
Asking whether a number is even is quite different from asking whether a number modulus 2 is equal to zero — or whether that number and 1 is equal to zero. Just as isEmpty is usually equal to testing the count of a collection but isn't as succinct and introduces possible side-effects that the compiler must step in and optimise away.

4 Likes

isEmpty and count is not directly analogous to isEven and %. The reason isEmpty exists is because not all collections are random-access, so their count property is O(n). It is therefore a major performance error with types like String to use count to detect emptiness. This isn't something the compiler can optimize away – it's a fundamental characteristic of non-random-access collections. isEmpty is implemented to compare startIndex to endIndex, which can happen in constant time on all collections (though it's occasionally micro-optimized to do something different when it might be faster – for example, it's hard-coded to false on closed ranges). But the method exists primarily to help people not fall into the performance trap. If all collections were random access, the justification would be purely on readability grounds (and fairly thin, given the readability of the count == 0 idiom is pretty good).

There is an analogy to be made between isEmpty and isDivisible(by:), for the case of non-trivial number types like a BigNum. But not for isEven specifically.

7 Likes

But not everybody knows that. It's not surprising that people develop alternative rationales for the count/isEmpty couple. Those alternative rationales may not be firmly grounded as yours. But they may be internally consistent as well, don't you think? This is the organic side of the language. It speaks an interesting language as well, don't you think?

1 Like

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

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

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."

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

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.

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.

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

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

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.

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

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

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

yes of course, sorry

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.

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