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

The review of SE-0288, "Adding isPower(of:) to BinaryInteger", begins now and runs through September 4, 2020.

Reviews are an important part of the Swift evolution process. All review feedback should be either on this forum thread or, if you would like to keep your feedback private, directly to the review manager (via email or direct message in the Swift forums).

What goes into a review of a proposal?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift.

When reviewing a proposal, here are some questions to consider:

  • What is your evaluation of the proposal?
  • Is the problem being addressed significant enough to warrant a change to Swift?
  • Does this proposal fit well with the feel and direction of Swift?
  • If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
  • How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

As always, thank you for your contribution to making Swift a better language.

Joe Groff
Review Manager

22 Likes

I am skeptical that this is useful for any argument but 2 (or maybe powers of 2), but it does seem likely that we'll be able to optimize this effectively for constant powers, so the generalization probably doesn't hurt.

8 Likes

I'm a big +1 on this, as I've had to implement a solution a few times myself - or rely on the pow function in Foundation and still do some data transformations myself.

I appreciate the work being done to create a fast vs slow path, as the performance will be critical in the domains this proposal mentions.

4 Likes

Thanks for your inputs, John!

I agree that the base 2 is the most popular use case. In fact, I originally proposed the isPowerOf2 version in this pitch thread. However, the community seems to prefer the generalised one. Similarly, SE-0225 proposed three APIs (isMultiple(of:), isOdd and isEven), but only the generic one isMultiple(of:) has been accepted. As a result, this proposal ended up with generalisation instead.

Yes, for constant powers, if the type Self is simple enough (e.g. built-in integer types) for compiler to statically evaluate conditions like base == 2, the performance penalty can be eliminated thanks to optimisations such as constant-folding and simplify-cfg.

7 Likes

Thanks for your support, Nathan!

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

1 Like

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.

5 Likes

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.

2 Likes

I'm happy with this. :smiley_cat:

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 }
  }
}
3 Likes

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

2 Likes

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

2 Likes

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.

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

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.

1 Like

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 https://bugs.swift.org/browse/SR-13471 for quotientAndRemainder.)

2 Likes

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

4 Likes

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

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

1 Like

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.

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.

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.

1 Like

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

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

2 Likes
Terms of Service

Privacy Policy

Cookie Policy