Complex Numbers (Pre-ACP)

language design
1

Continuing the discussion from Standard complex number in std library

Proposal

Problem statement

Currently, there is no stable counterpart to the C _Complex types, and a myriad of implementations exist on crates.io. Popular crates like num-complex exist, but more often there are implementations defined by the crates themselves, which, while compatible with the other types in having the exact same implementation, require a myriad of conversion functions to convert with each other. Additionally, there is no syntax supported like 1+2i or 1+2j for complex numbers. (This ACP doesn't cover this, but it does lay ground for future work in this area)

Motivating examples or use cases

A scientific computing library's functions (can be written in C):

// in comp
extern double _Complex computes_function(x: double _Complex);

can be represented in Rust without the need of complex structs and the like:

extern "C" {
  fn computes_function(x: c64) -> c64;
}
fn main() {
  let returned_value = computes_function(c32::new(3, 4))
}

with the special repr that only the standard library can provide. (This would, however, require that the complex numbers become lang items.)

Solution sketch

Complex numbers will have a implementation similar to this:

// c16, c32, c64, c128 to be defined this way using f16, f32, f64 and f128 respectively
#[lang = "complex"] // defines a special C-compatible repr which matches the ABI
struct c32 {
  re: f32,
  im: f32
}


impl c32 {
  fn conjugate() { ... }
  // more function impls as desired
}
// All the trait impls as per LLVM intrinsics
impl Add for c32 {}
impl Sub for c32 {}
impl Mul for c32 {}
impl Div for c32 {}

// syntax can be changed to use j
// in main.rs
fn main() {
  println!("{}", Complex(1, 2); 
}

The complex numbers will serve as structs and all operations will be defined as a struct operation.

Alternatives

Don't put it into the std (status quo)

We could just not put complex numbers in the std and let the popular libraries work. This would be acceptable if not for improving FFI with C, as it already implements the _Complex types and adding them to Rust would significantly improve the FFI experience with libraries already in C. I do not recommend this yet.

Links and related work

Standard complex number in std library

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

  • We think this problem seems worth solving, and the standard library might be the right place to solve it.
  • We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

  • We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
  • We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

Edit: The ACP transitioned into an RFC which is uploaded on GitHub here

3 Likes
Standard complex number in std library
2

A problem i see for FFI is that in C a complex number is not always passed as a struct.

On GNU _Complex is sometimes passed in SSE registers, but sometimes also passed as two separate parameters, sometimes also like a normal struct.

But MSVC does not actually support _Complex Ms docs

5 Likes
3

AFAIK it is a part of the C99 standard (Arithmetic types - cppreference.com) so I think that we can create a primitive that will have the implementation-specific FFI? MSVC does have _FComplex and the like so I think we can get away with doing FFI on that front.

4

This is not a problem — Rust itself also sometimes passes structs of two elements as separate values that may be in registers (a “scalar pair”). If compatibility with C is desired, the Complex struct can be given a special #[repr] which promises to match the C _Complex ABI when the generic parameter is a primitive float. It may technically be a new compiler feature, but all the pieces are (probably) already there.

5 Likes
5

This formula for complex multiplication doesn't handle "intermediate overflow" correctly; there are situations where the mathematically correct result (computed in infinite precision) would fit in T, but one or more of the intermediate products doesn't, so you don't get the right answer. Similar problems exist for division and complex norm. How do you plan to address this?

6

Answering out of turn, but is it by using the llvm intrinsics instead?

3 Likes
7

Yep, that was my idea. It's just that I was wondering if we wanted this as a primitive or a struct so I left it like that. Edited my post to use LLVM intrinsics instead.

(BTW, since this adds a new primitive to rust, would this technically not come under the scope of an ACP?)

2 Likes
8

This doesn't add a new primitive, unless you're talking about the syntax. But that can always be added later.

2 Likes
9

I'm not sure LLVM does implement numerically safe complex multiply, at least not in all cases.[1] Still, "this is the compiler's job" is a good answer to the question I asked, and "the compiler has intrinsics for complex arithmetic that (in principle) handle all the floating-point corner cases and are legible to optimization, but Rust doesn't expose them" is IMO a stronger argument for including complex numbers in the stdlib than just "there are a lot of crates already that define complex types and they're not interoperable". (You do mention that LLVM has these intrinsics in your problem statement, but you don't, IMO, give that the importance it deserves.)

  1. for example, llvm-project/compiler-rt/lib/builtins/muldc3.c at 5017370a1ce5009aed2855b645194bc141f72a2d · llvm/llvm-project · GitHub handles the naive formula producing a NaN that ought to be Inf, but it doesn't look like it even tries to detect the situation where the difference of two infinite-precision intermediates would be in the finite representable range of IEEE double. ↩︎

3 Likes
10

Can you link where that is in the langref? None of the places it says "complex" (that I found) are about complex numbers.

11

For the purposes of making the simplest possible ACP, please leave out the bits involving new custom lang syntax, and assume that this will have a constructor like c32::new(2.0, 4.0).

8 Likes
12

MLIR does

13

I agree. I'll add it as a major factor in the ACP and will change it as soon as I can.

1 Like
14

Well rust doesn't use MLIR, so that's not particularly relevant? (MLIR has all kinds of dialects, like sparse tensors for example.)

Whereas if there was, say, a llvm.complex.mul.f32 intrinsic that handled complex multiplication properly for us, that would be a stronger reason to have it built-in in some way, as it would be something a crate wouldn't use. (Like how https://doc.rust-lang.org/std/primitive.u128.html#method.carrying_mul_add is implemented on LLVM in a way not possible in a crate, which is one reason it's nice to have as a core method.)

1 Like
15

Hmm... It appears that [there were] (âš™ D119284 [IR] Add intrinsics to represent complex multiply and divide instructions.) some plans for complex numbers, but they are not entirely supported for now. It's odd because I thought there were some plans for doing so. I don't think this is a problem, as we can now use a platform dependent representation as a struct for the complex types. The advantage is still C FFI.

16

Is there a standard ABI for complex numbers in FORTRAN?

17

I don't think so since Fortran itself does not have a well defined ABI.

2 Likes
18

The ACP is very nearly complete. If there are no changes requested here, I'll submit it to the libs team. This is a final request for any additional feedback or changes I can incorporate.

1 Like
19

It's not clear from what you've written if the type is generic. It seems like it should be a generic Complex<T>, with optional type aliases type c32 = Complex<f32> and type c64 = Complex<f64>.

2 Likes
20

Integral T, such as Complex<i64>, are also sometimes useful. These are Gaussian integers, useful for all kinds of things in number theory, and can be used for geometry when you're dealing with integral coordinates.

6 Likes