Even and Odd Integers

Should isOdd have a default implementation of "return !isEven"? Then it would be optimized whenever isEven has an optimized implementation.

When would isEven have an optimized implementation? An example could be a bignum type implemented with [UInt]. Then isEven could be implemented with "return digits.first?.isEven ?? true" instead of requiring a full division.

Bravo @Dany_St-Amant!

I've updated the draft proposal here: swift-evolution/nnnn-binaryinteger-iseven-isodd-ismultiple.md at binaryinteger-iseven-isodd · robmaceachern/swift-evolution · GitHub

Some test cases for isMultiple(of:) are below. Let me know if anything looks off.

assert(0.isMultiple(of: 0))
assert(0.isMultiple(of: 2))
assert(0.isMultiple(of: -2))
assert(4.isMultiple(of: 2))
assert(4.isMultiple(of: -2))
assert(4.isMultiple(of: 4))
assert((-4).isMultiple(of: 2))
assert((-4).isMultiple(of: -2))
assert((-4).isMultiple(of: -4))

assert(2.isMultiple(of: 0) == false)
assert(3.isMultiple(of: 2) == false)
assert(3.isMultiple(of: -2) == false)
assert((-3).isMultiple(of: 2) == false)
assert((-3).isMultiple(of: -2) == false)

I have also updated the implementation of isOdd to be defined in terms of isEven instead of isMultiple directly (cc @CTMacUser). I'm not 100% sure if that is appropriate or not but it seems reasonable to me.

Re: isMultiple on floating point types. That seems like a bit of a can of worms to me but maybe someone can make a case for adding it.

It would be interesting to hear what the core team has to say about that. I think there is some benefit in keeping proposals as small and focused as possible to keep discussions and reviews on track but perhaps larger, more comprehensive, proposals would lead to a more cohesive set of functionality.

1 Like

Well alright, you're correct technically, but I'm not sure if we need to expose those low-level numerical details to the common user inside the stdlib. ;)
Also, floating point types are weird from a strict sense, I'm not even sure whether you could put a nice mathematical structure on them so that the common operations make sense and follow the usual laws... so treating them as an approximation of the reals is probably more useful for most cases. For everything else, I guess the method / function names should very obviously indicate that they're concerned with those low-level details.

My 2¢ on adding isMultiple to floating-point: it's trivially implementable for any conforming type, but I don't see any use-case for it, and I would want to see multiple use cases before we considered adding it.

Let's keep this proposal well-focused on BinaryInteger.

4 Likes

Hi Rob, quick notes on your proposed implementations:

  • isEven and isOdd should be @_transparent instead of @inlinable.
  • isEven should be implemented as follows:
var isEven: Bool { return _lowWord % 2 == 0 }

The semantics of BinaryInteger guarantee that this is correct, and it's potentially much more efficient for any bignum types conforming to the protocol.

Everything else looks pretty good to me. Are you ready to do the actual review?

3 Likes

Thanks Steve. I've updated the proposal draft.

I don't have an implementation PR ready but I would be able to take care of that tonight. Otherwise, I think this should be ready to go. Beyond opening a PR on swift-evolution (and participating in the active review) is there anything else required?

Re: @_transparent instead of @inlinable. I read through the TransparentAttr docs and wanted to sanity check this point with you:

  • Does the implementation need to call private things---either true- private functions, or internal functions that might go away in the next release? Then you can't allow it to be inlined.

_lowWord is marked public (and is @_transparent itself) but the underscore seems to imply some kind of privateness. I'm not familiar with how that convention is used in the standard library and if relying on an underscored property risks any future pain. It looks like _lowWord is used in other @_transparent implementations so I guess it won't be a problem.

_lowWord has public visibility, so you're fine using it. It's underscored to keep it out of the user-visible API surface; it itself is also marked @_transparent, so there's no binary compatibility concerns here.

Also, I actually have your proposal implemented on a branch, which is fine to use for the purposes of the proposal. Or you can do your own if you prefer. Mine isn't 100% in sync with your comments, since I've been maintaining it for a while, but it can be brought in sync without much hassle; I just wanted to have it for testing purposes.

4 Likes

Awesome! Thanks Steve.

This was interesting to see:

// Special case to avoid trapping on .min / -1.
if self == .min && other == -1 { return true }

Nice catch.

I've added a link to your PR in the proposal and I've also simplified the proposed solution section now that we have an implementation to point to. I figured it'd be a bit of pain to keep the docs and implementation details in sync between the two if there are any further changes.

Swift evolution PR is now available here: [Proposal] Add `isEven`, `isOdd`, and `isMultiple(of:)` to BinaryInteger by robmaceachern · Pull Request #891 · apple/swift-evolution · GitHub

Thanks everybody!

1 Like

Is there a reason it isn’t just “if other == -1 { return true }” though?

I considered that. It would also work fine. There’s not a strong reason to pick either one, and some hand-wavy arguments in favor of both. It doesn’t actually matter, since the proposal is the API surface and semantics. The implementation can always change.