SE-0288: Adding isPower(of:) to BinaryInteger

dingobye · 2020-08-27T01:46:16.578Z

Thanks for your support, Nathan!

May I know, apart from 2, is there any other base in your use case?

Mordil · 2020-08-27T01:48:08.820Z

Base 2 and Base 10 are the ones that I often use.

I think once I did base 16, but I honestly don't remember the context.

Andrew · 2020-08-28T04:28:44.287Z

I do similar checks (especially powers of 2) all the time, a big +1 from me.

This is consistent with other similar APIs already in Swift, and used frequently enough to be worth inclusion. It also considerably improves readability and confidence over inline alternatives like n != 0 && n & (n - 1) & n != 0 and n % d == 0.

In reviewing this proposal I searched projects for usage, and considered recent code reviews that had both inline methods. Those reviews all asked for comments explaining that code, or extraction of that code for readability.

anon9791410 · 2020-08-28T07:13:01.352Z

I'm happy with this.

It seems strange to me that we'd get this before integer exponentiation, which I need more often, but I'll take it regardless.

public extension Numeric {
  /// Raise this base to a `power`.
  func toThe<Power: UnsignedInteger>(_ power: Power) -> Self
  where Power.Stride: SignedInteger {
    power == 0
    ? 1
    : (1..<power).reduce(self) { result, _ in result * self }
  }
}

gribozavr · 2020-08-28T11:16:58.411Z

+1, checking for integers being powers of 2 and powers of 10 is a problem that sometimes arises in practice. Rolling a custom solution leads to either inefficient code (for example, repeatedly dividing in a loop) or requires a trick that people don't know about (like using popcount or x & (x - 1)), therefore I think isPower(of:) passes the bar for inclusion into the standard library.

ssuuyyuu · 2020-08-28T12:21:31.232Z

+1, love to see this available in the standard library!

dingobye · 2020-08-28T14:10:04.987Z

Thank you for the inputs, Jessy!

In the case of exponentiation, there are APIs in SE-0246, which are proposed to serve BinaryFloatingPoint though. It would be worth further investigation/discussions on how to define such API at Numeric level.

dingobye · 2020-08-28T16:00:04.804Z

Indeed! After all, the alternative inline solutions are not as intuitive as FizzBuzz

James_Dempsey · 2020-08-28T18:17:21.635Z

I am +1 for this proposal.

It adds functionality that can be difficult to get correct and clarity at the call site.

Although checking for powers of 2 is by far the most common case, the more general nature of the API mirrors the style and flexibility of isMultiple(of:) and so feels like a very Swift approach.

I read the proposal twice.

typesanitizer · 2020-08-28T19:43:37.645Z

Could you specify the expected behavior when base is negative? For example, in

    // Here if base is 0, 1 or -1, return true iff self equals base.
    if base.magnitude <= 1 { return self == base }

This will return false when self == 1 and base == -1...

Also, quotientAndRemainder's documentation says:

A tuple containing the quotient and remainder of this value divided by rhs . The remainder has the same sign as rhs .

But that doesn't seem to be the case in practice.

$ echo 'print((10 as Int).quotientAndRemainder(dividingBy: -3))' | xcrun swift
(quotient: -3, remainder: 1)

That makes it unclear what the later code using quotientAndRemainder is trying to do.

(EDIT: I've filed [SR-13471] Mismatch between behavior of quotientAndRemainder and docs · Issue #55913 · apple/swift · GitHub for quotientAndRemainder.)

Nevin · 2020-08-28T19:45:36.367Z

typesanitizer:

Could you specify the expected behavior when base is negative? For example, in
    // Here if base is 0, 1 or -1, return true iff self equals base.
    if base.magnitude <= 1 { return self == base }
This will return false when self == 1 and base == -1 ...

The line immediately before what you quoted is if self == 1 { return true }.

typesanitizer · 2020-08-28T19:56:08.917Z

Good point. I'm assuming that's for the base case t^0 but I don't think that necessarily matches user expectations. For example, if you ask me what the powers of 2 where, I would start out 2, 4, 8, 16.... That said, 0.isMultiple(of: 10) also returns true, so maybe this is intended to be consistent with that...

Lantua · 2020-08-28T20:08:18.474Z

So do we support negative base as part of the semantic?

dingobye · 2020-08-28T23:06:35.000Z

typesanitizer:

Could you specify the expected behavior when base is negative?

Same as non-negative base, i.e., we expected success iff (1) self is equal to 1 (which equals any_base^0), or (2) self is the product of one or more base.

typesanitizer:

That makes it unclear what the later code using quotientAndRemainder is trying to do.

As per the line immediately below quotientAndRemainder, the proposed solution only checks whether remainder is zero, regardless of its sign. In this case, either quotientAndRemainder behaviour works.

typesanitizer:

For example, if you ask me what the powers of 2 where, I would start out 2, 4, 8, 16....

To be more comprehensive, 1, 1/2, 1/4, 1/8... are powers of 2 as well. As a result, the proposed solution is compliant to the mathematic nature.

dingobye · 2020-08-28T23:09:53.994Z

Yes, we support negative base as long as its type Self is signed. Please refer to the above comments.

Joe_Groff · 2020-08-28T23:49:21.880Z

dingobye:

Same as non-negative base , i.e., we expected success iff (1) self is equal to 1 (which equals any_base^0), or (2) self is the product of one or more base .

typesanitizer:

That makes it unclear what the later code using quotientAndRemainder is trying to do.

As per the line immediately below quotientAndRemainder , the proposed solution only checks whether remainder is zero, regardless of its sign. In this case, either quotientAndRemainder behaviour works.

typesanitizer:

For example, if you ask me what the powers of 2 where, I would start out 2, 4, 8, 16....

To be more comprehensive, 1, 1/2, 1/4, 1/8... are powers of 2 as well. As a result, the proposed solution is compliant to the mathematic nature.

It might be good to clarify these points in the proposal, if you have a moment to revise it. Thanks @dingobye!

dingobye · 2020-08-29T03:18:18.903Z

Sure! I just had it updated.

Chris_Lattner3 · 2020-08-29T04:32:22.862Z

This is a very nice proposal - I agree that we should provide a more explicit API for the common case of power-of-2 checks. The way that you made this more general (to any power, including dynamic ones) without requiring duplicate public user APIs, and without sacrificing performance for the power of two case is really great.

Strong +1 from me,

-Chris

ktoso · 2020-09-03T05:33:58.352Z

Just dropping in to leave a happy +1 for this

Especially for powers of two this is a quite nice API and comes in handy.

Joe_Groff · 2020-09-15T22:46:59.134Z

Thanks everyone for your feedback! The core team has decided to accept this proposal.