apple / apple/swift-numerics

Should complex multiplication use augmented arithmetic?

Open
#238 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
Swift
Stars
1.9k
Forks
181
Avg merge
2d 5h
Merged PRs (30d)
6

Description

Currently, complex multiplication is implemented with `*` and `+`:

https://github.com/apple/swift-numerics/blob/5428505255ad35b8debd2c2c432350b213e4dff5/Sources/ComplexModule/Complex%2BNumeric.swift#L15-L17

However, there are well-known cancellation issues when computing the sum or difference of products in this manner. Here are some references:

* [Accurate Differences of Products with Kahan’s Algorithm](https://pharr.org/matt/blog/2019/11/03/difference-of-floats) (Matt Pharr)
* [Numerically stable method for solving quadratic equations](https://stackoverflow.com/questions/48979861/numerically-stable-method-for-solving-quadratic-equations/50065711#50065711) (StackOverflow)
* [On the Cost of Floating-Point Computation
Without Extra-Precise Arithmetic](https://people.eecs.berkeley.edu/~wkahan/Qdrtcs.pdf) (William Kahan)
* [Further analysis of Kahan's algorithm for the accurate computation of 2 x 2 determinants](https://hal.inria.fr/ensl-00649347/en) (Jeannerod, Louvet, Muller)

Given four numbers (a, b, c, d), we want to compute ab-cd to good accuracy even when the two products are nearly equal. The sources above (among others) describe a way to do so using fused multiply-add instructions, which can be written in Swift as:

```swift
// Computes a*b - c*d accurately
func differenceOfProducts(_ a: T, _ b: T, _ c: T, _ d: T) -> T {
let cd = c * d
let e = cd.addingProduct(-c, d)
let ab_cd = (-cd).addingProduct(a, b)
return ab_cd + e
}
```

This uses one more multiplication than the naive approach, but it is robust against catastrophic cancellation and it mitigates some (but not all) spurious overflows.

The same idea can be applied to the sum of products, and either version can perform both operations by simply negating one of the inputs. Furthermore, there are a variety of options for the name and signature of the function, such as:

```swift
func sumOfProducts(_ a: T, _ b: T, _ c: T, _ d: T) -> T { ... }

func add(product ab: (T, T), plusProduct cd: (T, T)) -> T { ... }

func subtract(product ab: (T, T), minusProduct cd: (T, T)) -> T { ... }

func dotProduct(_ u: (T, T), _ v: (T, T)) -> T { ... }

func determinant(_ M: (T, T, T, T) -> T { ... }

...
```

Should we add a function along these lines to Numerics, and use it to compute the components of complex multiplication?

If so, what spelling do we prefer, and where should it reside? (Free function / static method on `FloatingPoint` / namespaced in `Augmented` / etc.)

Contributor guide

Open the contributing guide

Research direction

Start with Sources/ComplexModule/Complex+Numeric.swift at the linked complex multiplication implementation. Read the cited references and inspect existing NumericModule APIs to evaluate the fused multiply-add approach and possible function placement or naming. Done means the API design is settled and the complex multiplication components use the chosen accurate arithmetic, with focused tests covering cancellation and overflow behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
swift
Domain
performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.