Should complex multiplication use augmented arithmetic?
- 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
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