The pow() function

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

6 Likes