What is the Swift equivalent of Rust powi() function?

Using Swift
1 
pub fn powi(self, n: i32) -> f64

Excerpt of function documentation:

Raises a number to an integer power.

Using this function is generally faster than using powf. It might have a different sequence of rounding operations than powf, so the results are not guaranteed to agree.

Unspecified precision

The precision of this function is non-deterministic. This means it varies by platform, Rust version, and can even differ within the same execution from one invocation to the next.

f64 - Rust (rust-lang.org)

2

powi isn't exposed directly in Swift; as it's rarely the operation that you actually want to use due to it's very hand-wavy semantics (pow is generally more accurate, and even in cases where powi gives a good answer, you cannot actually depend on it continuing to do so).

It's generally better to just write out a sequence of multiplications; for smallish powers, this is easy, and guarantees you a stable result:

extension FloatingPoint {
  var cubed: Self { self*self*self }
}

while for larger powers, the accumulated rounding error from multiplication chains in powi can become an actual issue such that you're better off using pow.

If you really need powi specifically, you can get at it with no overhead by putting a shim in a header file:

__attribute__((__always_inline__))
static inline powi(double x, int n) -> double {
  __builtin_powi(x, n);
}
6 Likes
3

That's interesting! Got any more details on why exactly?

1 Like
4

powi (equivalently GCC/clang's __builtin_powi) evaluates a sequence of multiplications rounding to the precision of the type on each one, so the expected error is about sqrt(log(n)) ulp, with worst-case error about log(n) ulp.

The pow function (at least in reasonable quality math library¹) has an error bound around 1 ulp or less for all inputs.

e.g. on macOS/ARM, the worst-case error for float arguments to powi(x,6) on [1, 2] (which evaluates as (x*x*x)*(x*x*x)) is at x = 1.1194676, where it produces 1.9682003, which is about 3.5ulp away from the exact answer of 1.968199916517702.... The powf math library function, by comparison, produces 1.9682, which has an error of 0.43ulp--about 8x better.

As for why "you cannot actually depend on it continuing to do so" is true, powi doesn't have a stable algorithm; it is (basically) a black-box sequence of fast-math multiplications subject to the optimizer's whims, and new optimizations or changes to the surrounding context may perturb results.

¹ Paul Zimmermann and colleagues maintain a survey of math library accuracy (pdf link). Table 3 has the largest known errors for double-precision functions. Of particular note, GNU, AMD, NewLib, Musl, Apple, ARM, all achieve < 1 ulp of error across the input range for pow; Intel, CUDA and ROCm are all < 2ulp. Only MSVC, FreeBSD, and OpenLibm have large errors.

33 Likes
5

Fascinating, thanks for taking the time to write that up! I'm really glad I asked :)

6

Pretend like there's a better way to generate a fixed-length parameter pack metatype. What's better then?

public extension Numeric {
  func toThe<each Multiplication>(_: (repeat each Multiplication).Type) -> Self {
    var power = 1 as Self
    for _ in repeat (each Multiplication).self { power *= self }
    return power
  }
}

typealias Three<Element> = (Element, Element, Element)
2.toThe(Three<Void>.self)

public extension Numeric {
  func toThe<Power: UnsignedInteger>(_ power: Power) -> Self
  where Power.Stride: SignedInteger {
    (0..<power).reduce(1) { power, _ in power * self }
  }
}

2.toThe(3 as UInt)
7

Many thanks to @scanon for in-depth exposition.

8

Note that if people have a good use-case in mind for powi, I'm definitely open to exposing it via the Builtin module. We would probably avoid exposing it in the stdlib for the reasons I sketched out above, but it's fine to make available for more specialized libraries to use if they need it.

1 Like
9

This looks like an attempt to treat Swift generics as if they were C++ templates. Swift generics are not a code-generation mechanism. A macro would be the more appropriate way to implement this.

10

Setting aside the actual bindings, the implementation is a sort-of worst-of-both-worlds approach, where you're not getting the accuracy benefits of using pow, but you're also not getting the optimized multiplication tree that powi gives you (what you've sketched out does O(n) serially-dependent multiplications, instead of O(log(n)) multiplications typical for powi--e.g. using your implementation to raise a number to the eighth power would require seven multiplies, but it should require three).

You could mostly work around this by using multiplications that are explicitly marked as reassociatable, like Relaxed.product on Numerics main, but directly using a builtin binding powi would be preferable when you really want those semantics.

11

Thanks for the advice! The Numeric I showed was under-constrained. I only find this kind of thing useful for integers and powi doesn't cover them.

1 Like