Support Complex Number Type

[tigercosmos]

add complex in SimplArray

[yungyuc]

@tigercosmos please provide more analyses

[tigercosmos]

I read the source code of numpy, and also I searched the C++ spec.
I think the most common and efficient way is to combine real and imaginary parts together.

for example, for a three-element complex64 array, the layout will be:

| R (4 bytes) | I (4 bytes) | R (4 bytes) | I (4 bytes) | R (4 bytes) | I (4 bytes) |

when we use the complex number, usually we will need both real and imaginary parts, so this layout ensures the memory efficiency.

[yungyuc]

It sounds like a plan to start with following the std::complex array layout, but we need a fuller analysis included in a specification with critical review. Let us use this thread to collect references. Could you please organize all prior arts for computer codes handling complex numbers?

[tigercosmos]

@yungyuc I checked the implementation of Numpy, std::complex, Eigen, FFTW.

• Numpy
  • NumPy defines its own numpy.complex64 and numpy.complex128 types, which are Python objects
  • Complex arrays are stored as interleaved real and imaginary parts in contiguous memory blocks.
• std::complex
  • the complex is a struct containing two members: the real part and the imaginary part.
  • Complex arrays are stored as interleaved real and imaginary parts in contiguous memory blocks.
• Eigen
  • leverage the std::complex
  • Complex arrays are stored as interleaved real and imaginary parts in contiguous memory blocks.
• FFTW
  • use C99 complex type, which is two consecutive floating-point numbers
  • Complex arrays are stored as interleaved real and imaginary parts in contiguous memory blocks.

To sum up, other works may have different complex types, but they all store the complex arrays in an interleaved way. Therefore, we can define our complex type, which should include the real and imaginary parts, and store the complex numbers in an interleaved array.

[yungyuc]

This is a list good enough to serve as a fundamental understanding for starting to prototype the complex value support for simple array, but it can use more clarity. A key point is to provide a reference and description to the interleaved storage style of the real and imaginary parts in a complex-valued array.

FFTW described the "interleaved format" as:

In the interleaved format, you provide pointers to the real part of a complex number, and the imaginary part understood to be stored in the next memory location.

The other storage style for the complex-valued array in FFTW is the split format:

The split format allows separate pointers to the real and imaginary parts of a complex array.

It helps to clarify that how the scalars complex64 and complex128 in Numpy are laid out in memory. It is defined in npy_common.h:

typedef struct
{
    double _Val[2];
} npy_cdouble;

typedef struct
{
    float _Val[2];
} npy_cfloat;

It will help to use example code to describe the scalar and array layout of all of the surveyed implementation, especially the standard C complex.h and C++ std::complex.

[tigercosmos]

Thanks for correcting me, I didn't realize that there are two formats for FFTW.

THe C complex definition is as:

 struct _C_double_complex {
 
     double _Val[2];
 
 };

and the std::complex definition is:

template<typename _Tp>
struct complex
{
// ...
private:
_Tp _M_real;
_Tp _M_imag;
};

I think I got the enough information, so I will start working on it.