The pow() function

Using Swift
1

Why we have to import Darwin for access to the pow() function? What Darwin is it? Why the pow() function works only with Doubles, but does not with Ints? Why there is no pow() in stl?

2

Math functions (including pow) have been accepted for inclusion in the standard library, via SE–246. You can see the status of all proposals here, and the change log here.

2 Likes
3

It's worth noting that even after SE-0246 is fully landed, pow will not be available for Int. The power function for integers is significantly different from he power function for floating-point numbers¹, and requires some discussion. That's not to say that we shouldn't or won't add it, but it's a separate proposal.

I don't understand this question; what are you trying to ask here?

¹ How is it different, you ask?

  • Unlike floating-point numbers, pow(x: T, y: T) -> T overflows (and in Swift, would trap) for almost every pair of input values when T is a fixed-width integer type. Such a function is not useless, but it's also significantly less useful than a function that either evaluates x**y mod n or produces a bignum result.

  • Because of the considerations above, the optimal algorithm is also quite different. pow on fixed-width floating-point numbers is usually best computed via an extra-precise exp2(y log2(x)), while for integers it's generally better to use either naive repeated squaring and multiplication, or a Montgomery ladder (possibly with higher radix, depending on what your expected input distribution looks like).

Because of these considerations, it's not completely obvious that a pow function for integer values should have the same name or what it's signature should look like. Some further discussion is needed.

"Ok, but I don't really care about all that, I just want to compute x**y for small integers."

There are three cases that cover the vast majority of such use cases (and perfectly illustrate why we need to be a little bit careful designing such a function):

  1. I just want to raise some numbers to fixed powers. If want x**2, it's often significantly better to write x*x. This will always be fast regardless of optimization settings, while if you write pow(x, 2), even if an integer power function exists, you are depending on the optimizer to inline and do constant propagation and a bunch of dead code elimination. It'll be fast much of the time, but x*x is much simpler. Even if you want x**4, it's better to write x*x*x*x. Obviously this path leads to madness eventually, but it gets you through all the small powers you're likely to use.

  2. I want to compute powers of 2/4/8/16. Use a shift instead. This is hugely better in every way.

  3. I want to compute powers of 10. There are only 20 of them before you overflow UInt64. Using a lookup table is again better in every way.

Note that these three scenarios account for almost all uses of a power function on fixed-width integers, and the best solution in the three cases is radically different. This makes it difficult to write a library function that does the best thing in all cases without any overhead.

5 Likes
4

I mean, Darwin is father for macOS? MacOS seats on Darwin?

790×599 35 KB

5

Ah. "Darwin" in a Swift context refers to the the libSystem layer of macOS/iOS/tvOS/watchOS, not to a distribution. It's libc + Apple additions, basically.

6

Thanks. I will write x*x*x. I did not know that it is normal.

7

Does the compiler optimize that as efficiently as using a temporary for x2?

let y = x*x
let z = y*y
8

It should but it appears the overflow checks break the optimization, demo

2 Likes
9

This is an optimization that the compiler probably should be licensed to do even in the presence of overflow checks, since it's never possible that one expression overflows and the other one does not. There's a subtle language policy question here in that it would change what subexpression is considered to have trapped, but I think we ought to be able to resolve that.

4 Likes