Even and Odd Integers

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.

Not totally...
Floats try hard to look like real numbers, but from a mathematical standpoint, they are only a cheap copy (after all, they can only express an infinitesimal small subset of all reals ;-)
So, in the realm of numerics, it's actually rather common that simple calculations like 1 / (3 as Double) can't be solved, and the computer cheats with approximation when it reaches the limits of its datatypes.
Normally, that doesn't matter, and there's little you can do about results that aren't exact - but still, it can be interesting to see when approximation happens, and when not.

I probably wouldn't call the method Double.isMultiple, though...