Even and Odd Integers

[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

This is in no way forced. It's a choice.

3 Likes

The definition I always used didn't have the a≠0, but mathematicians have lots of little edge cases that they don't agree on.

Since Swift is a pragmatic language, I can see the argument that 0.isDivisible(by: 0) should be false. Technically (by my definition anyway), 0/0 is defined (aka it is divisible), but is also indeterminate... so it isn't actually useful (and it would crash in swiftland anyway).

I now think always returning false for x.isDivisible(by: 0) makes the most sense.

I can't imagine why you would want to trap. That would stop this code from working:

if x.isDivisible(by: y) { return x/y }
1 Like

Well, I'm no compiler author, but I assume that standard arithmetic operations are handled by the machine directly for efficiency reasons, I could be wrong though. There are certainly languages where this isn't the case (e.g. in Isabelle, 0 / 0 = 0)

Different CPU architectures handle division by zero differently. x86 happens to trap, but some other archictectures have made other choices, and some don’t have instructions for divide at all (so software defines the behavior of division by zero).

The standard library wants to be efficient, but it also wants to smooth over some of these differences so that users can write portable code. We can choose to handle these situations in ways other than “whatever the hardware does.”

The tradeoff is that heavier-weight choices require correspondingly greater benefit to the user.

3 Likes

Silly question based on one of the examples in one copy of the proposal.

_sanityCheck(bytes > 0 && bytes.isDivisible(by: 4), "capacity must be multiple of 4 bytes"

Is the name isDivisible(by:) derived from its implementation or its usage? Not sure if I'm alone in this position but when using the implementation of isDivisible(by:), I'm mainly looking for multiples of a specific number.

So would it better to use isMultiple(of:)?

15 Likes

Ha ha, this is brilliant, I love it :-) "Multiple of" and "divisible by" are mostly synonym, but "multiple" does not involve any concept of division: this is an elegant solution to the problem of zero as a factor:

// No shadow of a doubt
12.isMultiple(of: 0) // false, obviously
0.isMultiple(of: 0)  // true, obviously
5 Likes

Wow, that’s a really elegant solution! This does not infer the expectation that a can be divided by b without further checking that b is 0.
Nice! :slight_smile:

This is great, and I agree that it makes the behavior of the 0-cases entirely obvious. Definite +1 from me for the isMultiple(of:) spelling.

If we ask WolframAlpha though:

is 0 a multiple of 3?

it says:

Input:
is 0 divisible by 3?

Result:
True


Also for practical purposes, eg coloring even rows differently than odd rows, checking with rowIndex.isMultiple(of: 2) or rowIndex.isDivisible(by: 2), I'd like it to return true for

... -6 -4 -2  0  2  4  6  ...

and not for:

... -6 -4 -2     2  4  6 ...

Sure, @Jens. isMultiple(of:2) returns true for all odd values, including 0.

Here is what I envision for x.isMultiple(of: y):

 y | -4 -3 -2 -1  0  1  2  3  4
x  |
---|---------------------------
-4 |  x     x  x     x  x     x
-3 |     x     x     x     x
-2 |        x  x     x  x
-1 |           x     x
 0 |  x  x  x  x  x  x  x  x  x
 1 |           x     x
 2 |        x  x     x  x
 3 |     x     x     x     x
 4 |  x     x  x     x  x     x

Particularly:

  • x.isMultiple(of: x) is always true
  • x.isMultiple(of: -x) is always true
  • x.isMultiple(of: 1) is always true
  • x.isMultiple(of: -1) is always true
  • 0.isMultiple(of: x) is always true
  • 0 is the only multiple of 0
7 Likes

Typo: @gwendal.roue means "for all even values" here.

4 Likes

Oops, thanks, Steve ;-)

Ah, sorry, i misread your earlier post (flipped x and y).

why didn’t any of us think of this sooner honestly

3 Likes

I like isMultiple(of:).

(Should it be available for both integer and floating point types btw?)

If it's added to the std lib, then perhaps we would also want

isPower(of:)

And, as it says in this Wikipedia article:

it is common in computing to need to round a number to a whole power of 2

So we might also want

rounded(.up/.down/…, toNearesMultipleOf:)

and

rounded(.up/.down/…, toNearestPowerOf:)

etc


Sorry for getting a bit off-topic, but would it make sense to treat a set of related methods like these (for multiples and powers) together as a single proposal?

Because it's not standard terminology, for whatever reason. But I agree that "is multiple of" is neither technically wrong in any way, nor confusing, nor ambiguous, so I'm all for it.

edit: Also, "divisible by" is linguistically a bit more flexible, you can talk about the "divisibility relation" and you can invert the relationship by saying "a divides b" instead of "b is divided by a".

I don't think this makes sense for floating point types; any real number is a multiple of any other real number (except 0), therefore defining the function for floating point type would be totally useless... unless you want to implicitly to convert to integers, somehow, but then what would e.g. the result of 12.1237676.isMultiple(of: 0.01) be?

isMultiple(of:) can be computed in constant time. I'm not sure if this is also true for isPower(of:). Wikipedia says that x86 can take logarithms of doubles in constant time, so you probably could... but then you could get into issues with rounding errors, etc. In any case, the problem seems decidedly less trivial to me than determining divisibility.

a.isMultiple(of: b) is constant time only for fixed-width types. If a is an m-bit number and b is an n-bit number, then the complexity bound is O(M(m,n)), where M(m,n) is the complexity of multiplication. In the simple common case where a is a bignum and b is fixed-size, the complexity is O(m). Using a naive bignum implementation the general case is O(mn).

The naive algorithm for isPower(of:) (repeated trial division), would have complexity something like O(m^2) (assuming that I've summed the series correctly in my head).

1 Like

true, but aren't all integer types in the stdlib fixed-width? You're right though, that if you define the function on the protocol, anyone could implement it in their custom bignum type, which is arbitrary-width.

Yes, that would be the better algorithm. So it's probably more efficient than I thought.

Terms of Service

Privacy Policy

Cookie Policy