Struct Complex 

pub struct Complex<T> {
    pub re: T,
    pub im: T,
}

Fields

re: T

im: T

Implementations

impl<T> Complex<T>

pub fn new(re: T, im: T) -> Self

Examples found in repository

crates/competitive/src/num/complex.rs (line 19)

    pub fn transpose(self) -> Self {
        Self::new(self.im, self.re)
    }
    pub fn map<U>(self, mut f: impl FnMut(T) -> U) -> Complex<U> {
        Complex::new(f(self.re), f(self.im))
    }
}
impl<T> Zero for Complex<T>
where
    T: Zero,
{
    fn zero() -> Self {
        Self::new(T::zero(), T::zero())
    }
}
impl<T> One for Complex<T>
where
    T: Zero + One,
{
    fn one() -> Self {
        Self::new(T::one(), T::zero())
    }
}
impl<T> Complex<T>
where
    T: Zero + One,
{
    pub fn i() -> Self {
        Self::new(T::zero(), T::one())
    }
}
impl<T> Complex<T>
where
    T: Neg<Output = T>,
{
    pub fn conjugate(self) -> Self {
        Self::new(self.re, -self.im)
    }
}
impl<T> Complex<T>
where
    T: Mul<Output: Add>,
{
    pub fn dot(self, rhs: Self) -> <<T as Mul>::Output as Add>::Output {
        self.re * rhs.re + self.im * rhs.im
    }
}
impl<T> Complex<T>
where
    T: Mul<Output: Sub>,
{
    pub fn cross(self, rhs: Self) -> <<T as Mul>::Output as Sub>::Output {
        self.re * rhs.im - self.im * rhs.re
    }
}
impl<T> Complex<T>
where
    T: Mul<Output: Add> + Clone,
{
    pub fn norm(self) -> <<T as Mul>::Output as Add>::Output {
        self.re.clone() * self.re + self.im.clone() * self.im
    }
}
impl<T> Complex<T>
where
    T: Zero + Ord + Mul<Output: Ord>,
{
    pub fn cmp_by_arg(self, other: Self) -> Ordering {
        fn pos<T>(c: &Complex<T>) -> bool
        where
            T: Zero + Ord,
        {
            let zero = T::zero();
            c.im < zero || c.im <= zero && c.re < zero
        }
        pos(&self)
            .cmp(&pos(&other))
            .then_with(|| (self.re * other.im).cmp(&(self.im * other.re)).reverse())
    }
}
impl<T> Complex<T>
where
    T: Float,
{
    pub fn polar(r: T, theta: T) -> Self {
        Self::new(r * theta.cos(), r * theta.sin())
    }
    pub fn primitive_nth_root_of_unity(n: T) -> Self {
        let theta = T::TAU / n;
        Self::new(theta.cos(), theta.sin())
    }
    pub fn abs(self) -> T {
        self.re.hypot(self.im)
    }
    pub fn unit(self) -> Self {
        self / self.abs()
    }
    pub fn angle(self) -> T {
        self.im.atan2(self.re)
    }
}
impl<T> Add for Complex<T>
where
    T: Add,
{
    type Output = Complex<<T as Add>::Output>;
    fn add(self, rhs: Self) -> Self::Output {
        Complex::new(self.re + rhs.re, self.im + rhs.im)
    }
}
impl<T> Add<T> for Complex<T>
where
    T: Add<Output = T>,
{
    type Output = Self;
    fn add(self, rhs: T) -> Self::Output {
        Self::new(self.re + rhs, self.im)
    }
}
impl<T> Sub for Complex<T>
where
    T: Sub,
{
    type Output = Complex<<T as Sub>::Output>;
    fn sub(self, rhs: Self) -> Self::Output {
        Complex::new(self.re - rhs.re, self.im - rhs.im)
    }
}
impl<T> Sub<T> for Complex<T>
where
    T: Sub<Output = T>,
{
    type Output = Self;
    fn sub(self, rhs: T) -> Self::Output {
        Self::new(self.re - rhs, self.im)
    }
}
impl<T, U> Mul for Complex<T>
where
    T: Clone + Mul,
    <T as Mul>::Output: Add<Output = U> + Sub<Output = U>,
{
    type Output = Complex<U>;
    fn mul(self, rhs: Self) -> Self::Output {
        Complex::new(
            self.re.clone() * rhs.re.clone() - self.im.clone() * rhs.im.clone(),
            self.re * rhs.im + self.im * rhs.re,
        )
    }
}
impl<T> Mul<T> for Complex<T>
where
    T: Clone + Mul,
{
    type Output = Complex<<T as Mul>::Output>;
    fn mul(self, rhs: T) -> Self::Output {
        Complex::new(self.re * rhs.clone(), self.im * rhs)
    }
}
impl<T> Div for Complex<T>
where
    T: Clone + Add<Output = T> + Sub<Output = T> + Mul<Output = T> + Div,
{
    type Output = Complex<<T as Div>::Output>;
    fn div(self, rhs: Self) -> Self::Output {
        let d = rhs.re.clone() * rhs.re.clone() + rhs.im.clone() * rhs.im.clone();
        Complex::new(
            (self.re.clone() * rhs.re.clone() + self.im.clone() * rhs.im.clone()) / d.clone(),
            (self.im * rhs.re - self.re * rhs.im) / d,
        )
    }
}
impl<T> Div<T> for Complex<T>
where
    T: Clone + Div,
{
    type Output = Complex<<T as Div>::Output>;
    fn div(self, rhs: T) -> Self::Output {
        Complex::new(self.re / rhs.clone(), self.im / rhs)
    }
}
impl<T> Neg for Complex<T>
where
    T: Neg,
{
    type Output = Complex<<T as Neg>::Output>;
    fn neg(self) -> Self::Output {
        Complex::new(-self.re, -self.im)
    }
}
macro_rules! impl_complex_ref_binop {
    (impl<$T:ident> $imp:ident $method:ident ($l:ty, $r:ty) where $($w:ident)*) => {
        impl<$T> $imp<$r> for &$l
        where
            $T: Clone $(+ $w<Output = $T>)*,
        {
            type Output = <$l as $imp<$r>>::Output;
            fn $method(self, rhs: $r) -> <$l as $imp<$r>>::Output {
                $imp::$method(self.clone(), rhs)
            }
        }
        impl<$T> $imp<&$r> for $l
        where
            $T: Clone $(+ $w<Output = $T>)*,
        {
            type Output = <$l as $imp<$r>>::Output;
            fn $method(self, rhs: &$r) -> <$l as $imp<$r>>::Output {
                $imp::$method(self, rhs.clone())
            }
        }
        impl<$T> $imp<&$r> for &$l
        where
            $T: Clone $(+ $w<Output = $T>)*,
        {
            type Output = <$l as $imp<$r>>::Output;
            fn $method(self, rhs: &$r) -> <$l as $imp<$r>>::Output {
                $imp::$method(self.clone(), rhs.clone())
            }
        }
    };
}
impl_complex_ref_binop!(impl<T> Add add (Complex<T>, Complex<T>) where Add);
impl_complex_ref_binop!(impl<T> Add add (Complex<T>, T) where Add);
impl_complex_ref_binop!(impl<T> Sub sub (Complex<T>, Complex<T>) where Sub);
impl_complex_ref_binop!(impl<T> Sub sub (Complex<T>, T) where Sub);
impl_complex_ref_binop!(impl<T> Mul mul (Complex<T>, Complex<T>) where Add Sub Mul);
impl_complex_ref_binop!(impl<T> Mul mul (Complex<T>, T) where Mul);
impl_complex_ref_binop!(impl<T> Div div (Complex<T>, Complex<T>) where Add Sub Mul Div);
impl_complex_ref_binop!(impl<T> Div div (Complex<T>, T) where Div);
macro_rules! impl_complex_ref_unop {
    (impl<$T:ident> $imp:ident $method:ident ($t:ty) where $($w:ident)*) => {
        impl<$T> $imp for &$t
        where
            $T: Clone $(+ $w<Output = $T>)*,
        {
            type Output = <$t as $imp>::Output;
            fn $method(self) -> <$t as $imp>::Output {
                $imp::$method(self.clone())
            }
        }
    };
}
impl_complex_ref_unop!(impl<T> Neg neg (Complex<T>) where Neg);
macro_rules! impl_complex_op_assign {
    (impl<$T:ident> $imp:ident $method:ident ($l:ty, $r:ty) $fromimp:ident $frommethod:ident where $($w:ident)*) => {
        impl<$T> $imp<$r> for $l
        where
            $T: Clone $(+ $w<Output = $T>)*,
        {
            fn $method(&mut self, rhs: $r) {
                *self = $fromimp::$frommethod(self.clone(), rhs);
            }
        }
        impl<$T> $imp<&$r> for $l
        where
            $T: Clone $(+ $w<Output = $T>)*,
        {
            fn $method(&mut self, rhs: &$r) {
                $imp::$method(self, rhs.clone());
            }
        }
    };
}
impl_complex_op_assign!(impl<T> AddAssign add_assign (Complex<T>, Complex<T>) Add add where Add);
impl_complex_op_assign!(impl<T> AddAssign add_assign (Complex<T>, T) Add add where Add);
impl_complex_op_assign!(impl<T> SubAssign sub_assign (Complex<T>, Complex<T>) Sub sub where Sub);
impl_complex_op_assign!(impl<T> SubAssign sub_assign (Complex<T>, T) Sub sub where Sub);
impl_complex_op_assign!(impl<T> MulAssign mul_assign (Complex<T>, Complex<T>) Mul mul where Add Sub Mul);
impl_complex_op_assign!(impl<T> MulAssign mul_assign (Complex<T>, T) Mul mul where Mul);
impl_complex_op_assign!(impl<T> DivAssign div_assign (Complex<T>, Complex<T>) Div div where Add Sub Mul Div);
impl_complex_op_assign!(impl<T> DivAssign div_assign (Complex<T>, T) Div div where Div);
macro_rules! impl_complex_fold {
    (impl<$T:ident> $imp:ident $method:ident ($t:ty) $identimp:ident $identmethod:ident $fromimp:ident $frommethod:ident where $($w:ident)* $(+ $x:ident)*) => {
        impl<$T> $imp for $t
        where
            $T: $identimp $(+ $w<Output = $T>)* $(+ $x)*,
        {
            fn $method<I: Iterator<Item = Self>>(iter: I) -> Self {
                iter.fold(<Self as $identimp>::$identmethod(), $fromimp::$frommethod)
            }
        }
        impl<'a, $T: 'a> $imp<&'a $t> for $t
        where
            $T: Clone + $identimp $(+ $w<Output = $T>)* $(+ $x)*,
        {
            fn $method<I: Iterator<Item = &'a $t>>(iter: I) -> Self {
                iter.fold(<Self as $identimp>::$identmethod(), $fromimp::$frommethod)
            }
        }
    };
}
impl_complex_fold!(impl<T> Sum sum (Complex<T>) Zero zero Add add where Add);
impl_complex_fold!(impl<T> Product product (Complex<T>) One one Mul mul where Add Sub Mul + Zero + Clone);

impl<T: Scan> Scan for Complex<T> {
    type Output = Complex<<T as Scan>::Output>;
    fn scan<I: ScanSource>(iter: &mut I) -> Option<Self::Output> {
        Some(Complex::new(
            <T as Scan>::scan(iter)?,
            <T as Scan>::scan(iter)?,
        ))
    }

crates/competitive/src/math/fast_fourier_transform.rs (line 101)

    pub fn eval_twiddle(cache: &[Complex<f64>], step: usize, n: usize, k: usize) -> Complex<f64> {
        let k = step * k;
        let w = cache[(k >> 2) << 1].conjugate();
        let w = match k & 3 {
            0 => w,
            1 => Complex::new(-w.re, -w.im),
            2 => Complex::new(-w.im, w.re),
            _ => Complex::new(w.im, -w.re),
        };
        cache[step * n].conjugate() * w
    }

    #[target_feature(enable = "avx2,fma")]
    pub unsafe fn fft_soa(a: &mut [Complex4]) {
        let n = a.len() * 4;
        RotateCache::ensure(n / 2);
        RotateCache::with(|cache| {
            let parity = n.trailing_zeros() & 1;
            for leaf in (0..n).step_by(16) {
                let mut level = (n + leaf).trailing_zeros();
                level -= u32::from(level & 1 != parity);
                while level >= 4 {
                    let len = 1usize << level;
                    let q = leaf >> level;
                    let width = len / 16;
                    let start = q * width * 4;
                    let (a, rest) = a[start..start + width * 4].split_at_mut(width);
                    let (b, rest) = rest.split_at_mut(width);
                    let (c, d) = rest.split_at_mut(width);
                    let w1 = eval_twiddle(cache, 4, n >> level, q);
                    let w2 = w1 * w1;
                    let w3 = w1 * w2;
                    let (w1r, w1i) = (_mm256_set1_pd(w1.re), _mm256_set1_pd(w1.im));
                    let (w2r, w2i) = (_mm256_set1_pd(w2.re), _mm256_set1_pd(w2.im));
                    let (w3r, w3i) = (_mm256_set1_pd(w3.re), _mm256_set1_pd(w3.im));
                    for i in 0..width {
                        let (ar, ai) = load4(&a[i]);
                        let (br, bi) = load4(&b[i]);
                        let (cr, ci) = load4(&c[i]);
                        let (dr, di) = load4(&d[i]);
                        let (br, bi) = mul4(br, bi, w1r, w1i);
                        let (cr, ci) = mul4(cr, ci, w2r, w2i);
                        let (dr, di) = mul4(dr, di, w3r, w3i);
                        let acr = _mm256_add_pd(ar, cr);
                        let aci = _mm256_add_pd(ai, ci);
                        let bdr = _mm256_add_pd(br, dr);
                        let bdi = _mm256_add_pd(bi, di);
                        let acd_r = _mm256_sub_pd(ar, cr);
                        let acd_i = _mm256_sub_pd(ai, ci);
                        let bdd_r = _mm256_sub_pd(br, dr);
                        let bdd_i = _mm256_sub_pd(bi, di);
                        store4(&mut a[i], _mm256_add_pd(acr, bdr), _mm256_add_pd(aci, bdi));
                        store4(&mut b[i], _mm256_sub_pd(acr, bdr), _mm256_sub_pd(aci, bdi));
                        store4(
                            &mut c[i],
                            _mm256_sub_pd(acd_r, bdd_i),
                            _mm256_add_pd(acd_i, bdd_r),
                        );
                        store4(
                            &mut d[i],
                            _mm256_add_pd(acd_r, bdd_i),
                            _mm256_sub_pd(acd_i, bdd_r),
                        );
                    }
                    level -= 2;
                }
            }
            if parity != 0 {
                let blocks = n / 8;
                for k in 0..blocks {
                    let w = eval_twiddle(cache, 2, blocks, k);
                    let wr = _mm256_set1_pd(w.re);
                    let wi = _mm256_set1_pd(w.im);
                    let (ar, ai) = load4(&a[k * 2]);
                    let (br, bi) = load4(&a[k * 2 + 1]);
                    let (br, bi) = mul4(br, bi, wr, wi);
                    store4(&mut a[k * 2], _mm256_add_pd(ar, br), _mm256_add_pd(ai, bi));
                    store4(
                        &mut a[k * 2 + 1],
                        _mm256_sub_pd(ar, br),
                        _mm256_sub_pd(ai, bi),
                    );
                }
            }
        });
    }

    #[target_feature(enable = "avx2,fma")]
    pub unsafe fn ifft_soa(a: &mut [Complex4]) {
        let n = a.len() * 4;
        RotateCache::ensure(n / 2);
        RotateCache::with(|cache| {
            let parity = n.trailing_zeros() & 1;
            if parity != 0 {
                let blocks = n / 8;
                for k in 0..blocks {
                    let w = eval_twiddle(cache, 2, blocks, k).conjugate();
                    let wr = _mm256_set1_pd(w.re);
                    let wi = _mm256_set1_pd(w.im);
                    let (ar, ai) = load4(&a[k * 2]);
                    let (br, bi) = load4(&a[k * 2 + 1]);
                    store4(&mut a[k * 2], _mm256_add_pd(ar, br), _mm256_add_pd(ai, bi));
                    let (br, bi) = mul4(_mm256_sub_pd(ar, br), _mm256_sub_pd(ai, bi), wr, wi);
                    store4(&mut a[k * 2 + 1], br, bi);
                }
            }
            for leaf in (12..n).step_by(16) {
                let max_level = (leaf + 3).trailing_ones();
                let mut level = 4 + parity;
                while level <= max_level {
                    let len = 1usize << level;
                    let q = leaf >> level;
                    let width = len / 16;
                    let start = q * width * 4;
                    let (a, rest) = a[start..start + width * 4].split_at_mut(width);
                    let (b, rest) = rest.split_at_mut(width);
                    let (c, d) = rest.split_at_mut(width);
                    let w1 = eval_twiddle(cache, 4, n >> level, q).conjugate();
                    let w2 = w1 * w1;
                    let w3 = w1 * w2;
                    let (w1r, w1i) = (_mm256_set1_pd(w1.re), _mm256_set1_pd(w1.im));
                    let (w2r, w2i) = (_mm256_set1_pd(w2.re), _mm256_set1_pd(w2.im));
                    let (w3r, w3i) = (_mm256_set1_pd(w3.re), _mm256_set1_pd(w3.im));
                    for i in 0..width {
                        let (ar, ai) = load4(&a[i]);
                        let (br, bi) = load4(&b[i]);
                        let (cr, ci) = load4(&c[i]);
                        let (dr, di) = load4(&d[i]);
                        let abr = _mm256_add_pd(ar, br);
                        let abi = _mm256_add_pd(ai, bi);
                        let cdr = _mm256_add_pd(cr, dr);
                        let cdi = _mm256_add_pd(ci, di);
                        let abd_r = _mm256_sub_pd(ar, br);
                        let abd_i = _mm256_sub_pd(ai, bi);
                        let cdd_r = _mm256_sub_pd(cr, dr);
                        let cdd_i = _mm256_sub_pd(ci, di);
                        store4(&mut a[i], _mm256_add_pd(abr, cdr), _mm256_add_pd(abi, cdi));
                        let (br, bi) = mul4(
                            _mm256_add_pd(abd_r, cdd_i),
                            _mm256_sub_pd(abd_i, cdd_r),
                            w1r,
                            w1i,
                        );
                        store4(&mut b[i], br, bi);
                        let (cr, ci) =
                            mul4(_mm256_sub_pd(abr, cdr), _mm256_sub_pd(abi, cdi), w2r, w2i);
                        store4(&mut c[i], cr, ci);
                        let (dr, di) = mul4(
                            _mm256_sub_pd(abd_r, cdd_i),
                            _mm256_add_pd(abd_i, cdd_r),
                            w3r,
                            w3i,
                        );
                        store4(&mut d[i], dr, di);
                    }
                    level += 2;
                }
            }
            let scale = _mm256_set1_pd(4.0 / n as f64);
            for value in a {
                let (re, im) = load4(value);
                store4(value, _mm256_mul_pd(re, scale), _mm256_mul_pd(im, scale));
            }
        });
    }

    #[target_feature(enable = "avx2,fma")]
    unsafe fn dot_one_soa(a: &mut [Complex4], b: &[Complex4]) {
        let n = a.len() * 4;
        RotateCache::ensure(n / 2);
        RotateCache::with(|cache| {
            for i in 0..a.len() {
                let (mut br, mut bi) = load4(&b[i]);
                let mut rr = _mm256_setzero_pd();
                let mut ri = _mm256_setzero_pd();
                let w = eval_twiddle(cache, 1, a.len(), i);
                let wr = _mm256_setr_pd(w.re, 1.0, 1.0, 1.0);
                let wi = _mm256_setr_pd(w.im, 0.0, 0.0, 0.0);
                for lane in 0..4 {
                    let ar = _mm256_set1_pd(a[i].re[lane]);
                    let ai = _mm256_set1_pd(a[i].im[lane]);
                    multiply_accumulate4(&mut rr, &mut ri, ar, ai, br, bi);
                    if lane != 3 {
                        br = _mm256_permute4x64_pd::<0x93>(br);
                        bi = _mm256_permute4x64_pd::<0x93>(bi);
                        (br, bi) = mul4(br, bi, wr, wi);
                    }
                }
                store4(&mut a[i], rr, ri);
            }
        });
    }

    #[inline]
    fn pack_f64(values: impl Iterator<Item = f64>, n: usize) -> Vec<Complex4> {
        let mut result = Vec::with_capacity(n / 4);
        advise_huge_pages(&mut result);
        result.resize(n / 4, Complex4::default());
        for (i, value) in values.enumerate() {
            if i < n {
                result[i >> 2].re[i & 3] = value;
            } else {
                result[(i - n) >> 2].im[i & 3] = value;
            }
        }
        result
    }

    #[target_feature(enable = "avx2,fma")]
    pub unsafe fn convolve_f64_avx2(
        a: impl ExactSizeIterator<Item = f64>,
        b: impl ExactSizeIterator<Item = f64>,
        range: std::ops::Range<usize>,
    ) -> Vec<f64> {
        let n = (range.end.next_power_of_two() / 2).max(4);
        let mut fa = pack_f64(a, n);
        let mut fb = pack_f64(b, n);
        fft_soa(&mut fa);
        fft_soa(&mut fb);
        dot_one_soa(&mut fa, &fb);
        drop(fb);
        ifft_soa(&mut fa);
        range
            .map(|i| {
                if i < n {
                    fa[i >> 2].re[i & 3]
                } else {
                    fa[(i - n) >> 2].im[i & 3]
                }
            })
            .collect()
    }
    #[target_feature(enable = "avx2")]
    pub unsafe fn convolve_i64_avx2(a: Vec<i64>, b: Vec<i64>, len: usize) -> Vec<i64> {
        super::convolve_i64_naive(a, b, len)
    }
    #[target_feature(enable = "avx512f,avx512dq,avx512cd,avx512bw,avx512vl")]
    pub unsafe fn convolve_i64_avx512(a: Vec<i64>, b: Vec<i64>, len: usize) -> Vec<i64> {
        super::convolve_i64_naive(a, b, len)
    }
}

fn bit_reverse<T>(f: &mut [T]) {
    let mut ip = vec![0u32];
    let mut k = f.len();
    let mut m = 1;
    while 2 * m < k {
        k /= 2;
        for j in 0..m {
            ip.push(ip[j] + k as u32);
        }
        m *= 2;
    }
    if m == k {
        for i in 1..m {
            for j in 0..i {
                let ji = j + ip[i] as usize;
                let ij = i + ip[j] as usize;
                f.swap(ji, ij);
            }
        }
    } else {
        for i in 1..m {
            for j in 0..i {
                let ji = j + ip[i] as usize;
                let ij = i + ip[j] as usize;
                f.swap(ji, ij);
                f.swap(ji + m, ij + m);
            }
        }
    }
}

fn real_twiddles(n: usize, inverse: bool, mut f: impl FnMut(usize, Complex<f64>)) {
    const BLOCK: usize = 256;
    let sign = if inverse { 1.0 } else { -1.0 };
    let step = Complex::primitive_nth_root_of_unity(sign * n as f64);
    for start in (1..n / 4).step_by(BLOCK) {
        let mut w = Complex::polar(1.0, sign * std::f64::consts::TAU * start as f64 / n as f64);
        for k in start..(start + BLOCK).min(n / 4) {
            f(k, w);
            w *= step;
        }
    }
}

pub fn transform_real(t: impl IntoIterator<Item = f64>, len: usize) -> Vec<Complex<f64>> {
    let n = len.max(4).next_power_of_two();
    let mut f = vec![Complex::zero(); n / 2];
    for (i, t) in t.into_iter().enumerate() {
        if i & 1 == 0 {
            f[i / 2].re = t;
        } else {
            f[i / 2].im = t;
        }
    }
    fft(&mut f);
    bit_reverse(&mut f);
    f[0] = Complex::new(f[0].re + f[0].im, f[0].re - f[0].im);
    f[n / 4] = f[n / 4].conjugate();
    real_twiddles(n, false, |k, wk| {
        let c = wk.conjugate().transpose() + 1.;
        let d = c * (f[k] - f[n / 2 - k].conjugate()) * 0.5;
        f[k] -= d;
        f[n / 2 - k] += d.conjugate();
    });
    f
}

pub fn inverse_transform_real(mut f: Vec<Complex<f64>>, len: usize) -> Vec<f64> {
    let n = len.max(4).next_power_of_two();
    assert_eq!(f.len(), n / 2);
    f[0] = Complex::new((f[0].re + f[0].im) * 0.5, (f[0].re - f[0].im) * 0.5);
    f[n / 4] = f[n / 4].conjugate();
    real_twiddles(n, true, |k, wk| {
        let c = wk.transpose().conjugate() + 1.;
        let d = c * (f[k] - f[n / 2 - k].conjugate()) * 0.5;
        f[k] -= d;
        f[n / 2 - k] += d.conjugate();
    });
    bit_reverse(&mut f);
    ifft(&mut f);
    let inv = 1. / (n / 2) as f64;
    (0..len)
        .map(|i| inv * if i & 1 == 0 { f[i / 2].re } else { f[i / 2].im })
        .collect()
}

crates/competitive/src/geometry/circle.rs (line 25)

    pub fn cross_circle(&self, other: &Self) -> Option<(Complex<T>, Complex<T>)> {
        let d = (self.c - other.c).abs();
        let rc = (d * d + self.r * self.r - other.r * other.r) / (d + d);
        let rs2 = self.r * self.r - rc * rc;
        if Approx(rs2) < Approx(T::zero()) {
            return None;
        }
        let rs = rs2.abs().sqrt();
        let diff = (other.c - self.c) / d;
        Some((
            self.c + diff * Complex::new(rc, rs),
            self.c + diff * Complex::new(rc, -rs),
        ))
    }

pub fn transpose(self) -> Self

Examples found in repository

crates/competitive/src/math/fast_fourier_transform.rs (line 397)

pub fn transform_real(t: impl IntoIterator<Item = f64>, len: usize) -> Vec<Complex<f64>> {
    let n = len.max(4).next_power_of_two();
    let mut f = vec![Complex::zero(); n / 2];
    for (i, t) in t.into_iter().enumerate() {
        if i & 1 == 0 {
            f[i / 2].re = t;
        } else {
            f[i / 2].im = t;
        }
    }
    fft(&mut f);
    bit_reverse(&mut f);
    f[0] = Complex::new(f[0].re + f[0].im, f[0].re - f[0].im);
    f[n / 4] = f[n / 4].conjugate();
    real_twiddles(n, false, |k, wk| {
        let c = wk.conjugate().transpose() + 1.;
        let d = c * (f[k] - f[n / 2 - k].conjugate()) * 0.5;
        f[k] -= d;
        f[n / 2 - k] += d.conjugate();
    });
    f
}

pub fn inverse_transform_real(mut f: Vec<Complex<f64>>, len: usize) -> Vec<f64> {
    let n = len.max(4).next_power_of_two();
    assert_eq!(f.len(), n / 2);
    f[0] = Complex::new((f[0].re + f[0].im) * 0.5, (f[0].re - f[0].im) * 0.5);
    f[n / 4] = f[n / 4].conjugate();
    real_twiddles(n, true, |k, wk| {
        let c = wk.transpose().conjugate() + 1.;
        let d = c * (f[k] - f[n / 2 - k].conjugate()) * 0.5;
        f[k] -= d;
        f[n / 2 - k] += d.conjugate();
    });
    bit_reverse(&mut f);
    ifft(&mut f);
    let inv = 1. / (n / 2) as f64;
    (0..len)
        .map(|i| inv * if i & 1 == 0 { f[i / 2].re } else { f[i / 2].im })
        .collect()
}

pub fn map<U>(self, f: impl FnMut(T) -> U) -> Complex<U>

impl<T> Complex<T>

where T: Zero + One,

pub fn i() -> Self

impl<T> Complex<T>

where T: Neg<Output = T>,

pub fn conjugate(self) -> Self

Examples found in repository

crates/competitive/src/math/fast_fourier_transform.rs (line 98)

    pub fn eval_twiddle(cache: &[Complex<f64>], step: usize, n: usize, k: usize) -> Complex<f64> {
        let k = step * k;
        let w = cache[(k >> 2) << 1].conjugate();
        let w = match k & 3 {
            0 => w,
            1 => Complex::new(-w.re, -w.im),
            2 => Complex::new(-w.im, w.re),
            _ => Complex::new(w.im, -w.re),
        };
        cache[step * n].conjugate() * w
    }

    #[target_feature(enable = "avx2,fma")]
    pub unsafe fn fft_soa(a: &mut [Complex4]) {
        let n = a.len() * 4;
        RotateCache::ensure(n / 2);
        RotateCache::with(|cache| {
            let parity = n.trailing_zeros() & 1;
            for leaf in (0..n).step_by(16) {
                let mut level = (n + leaf).trailing_zeros();
                level -= u32::from(level & 1 != parity);
                while level >= 4 {
                    let len = 1usize << level;
                    let q = leaf >> level;
                    let width = len / 16;
                    let start = q * width * 4;
                    let (a, rest) = a[start..start + width * 4].split_at_mut(width);
                    let (b, rest) = rest.split_at_mut(width);
                    let (c, d) = rest.split_at_mut(width);
                    let w1 = eval_twiddle(cache, 4, n >> level, q);
                    let w2 = w1 * w1;
                    let w3 = w1 * w2;
                    let (w1r, w1i) = (_mm256_set1_pd(w1.re), _mm256_set1_pd(w1.im));
                    let (w2r, w2i) = (_mm256_set1_pd(w2.re), _mm256_set1_pd(w2.im));
                    let (w3r, w3i) = (_mm256_set1_pd(w3.re), _mm256_set1_pd(w3.im));
                    for i in 0..width {
                        let (ar, ai) = load4(&a[i]);
                        let (br, bi) = load4(&b[i]);
                        let (cr, ci) = load4(&c[i]);
                        let (dr, di) = load4(&d[i]);
                        let (br, bi) = mul4(br, bi, w1r, w1i);
                        let (cr, ci) = mul4(cr, ci, w2r, w2i);
                        let (dr, di) = mul4(dr, di, w3r, w3i);
                        let acr = _mm256_add_pd(ar, cr);
                        let aci = _mm256_add_pd(ai, ci);
                        let bdr = _mm256_add_pd(br, dr);
                        let bdi = _mm256_add_pd(bi, di);
                        let acd_r = _mm256_sub_pd(ar, cr);
                        let acd_i = _mm256_sub_pd(ai, ci);
                        let bdd_r = _mm256_sub_pd(br, dr);
                        let bdd_i = _mm256_sub_pd(bi, di);
                        store4(&mut a[i], _mm256_add_pd(acr, bdr), _mm256_add_pd(aci, bdi));
                        store4(&mut b[i], _mm256_sub_pd(acr, bdr), _mm256_sub_pd(aci, bdi));
                        store4(
                            &mut c[i],
                            _mm256_sub_pd(acd_r, bdd_i),
                            _mm256_add_pd(acd_i, bdd_r),
                        );
                        store4(
                            &mut d[i],
                            _mm256_add_pd(acd_r, bdd_i),
                            _mm256_sub_pd(acd_i, bdd_r),
                        );
                    }
                    level -= 2;
                }
            }
            if parity != 0 {
                let blocks = n / 8;
                for k in 0..blocks {
                    let w = eval_twiddle(cache, 2, blocks, k);
                    let wr = _mm256_set1_pd(w.re);
                    let wi = _mm256_set1_pd(w.im);
                    let (ar, ai) = load4(&a[k * 2]);
                    let (br, bi) = load4(&a[k * 2 + 1]);
                    let (br, bi) = mul4(br, bi, wr, wi);
                    store4(&mut a[k * 2], _mm256_add_pd(ar, br), _mm256_add_pd(ai, bi));
                    store4(
                        &mut a[k * 2 + 1],
                        _mm256_sub_pd(ar, br),
                        _mm256_sub_pd(ai, bi),
                    );
                }
            }
        });
    }

    #[target_feature(enable = "avx2,fma")]
    pub unsafe fn ifft_soa(a: &mut [Complex4]) {
        let n = a.len() * 4;
        RotateCache::ensure(n / 2);
        RotateCache::with(|cache| {
            let parity = n.trailing_zeros() & 1;
            if parity != 0 {
                let blocks = n / 8;
                for k in 0..blocks {
                    let w = eval_twiddle(cache, 2, blocks, k).conjugate();
                    let wr = _mm256_set1_pd(w.re);
                    let wi = _mm256_set1_pd(w.im);
                    let (ar, ai) = load4(&a[k * 2]);
                    let (br, bi) = load4(&a[k * 2 + 1]);
                    store4(&mut a[k * 2], _mm256_add_pd(ar, br), _mm256_add_pd(ai, bi));
                    let (br, bi) = mul4(_mm256_sub_pd(ar, br), _mm256_sub_pd(ai, bi), wr, wi);
                    store4(&mut a[k * 2 + 1], br, bi);
                }
            }
            for leaf in (12..n).step_by(16) {
                let max_level = (leaf + 3).trailing_ones();
                let mut level = 4 + parity;
                while level <= max_level {
                    let len = 1usize << level;
                    let q = leaf >> level;
                    let width = len / 16;
                    let start = q * width * 4;
                    let (a, rest) = a[start..start + width * 4].split_at_mut(width);
                    let (b, rest) = rest.split_at_mut(width);
                    let (c, d) = rest.split_at_mut(width);
                    let w1 = eval_twiddle(cache, 4, n >> level, q).conjugate();
                    let w2 = w1 * w1;
                    let w3 = w1 * w2;
                    let (w1r, w1i) = (_mm256_set1_pd(w1.re), _mm256_set1_pd(w1.im));
                    let (w2r, w2i) = (_mm256_set1_pd(w2.re), _mm256_set1_pd(w2.im));
                    let (w3r, w3i) = (_mm256_set1_pd(w3.re), _mm256_set1_pd(w3.im));
                    for i in 0..width {
                        let (ar, ai) = load4(&a[i]);
                        let (br, bi) = load4(&b[i]);
                        let (cr, ci) = load4(&c[i]);
                        let (dr, di) = load4(&d[i]);
                        let abr = _mm256_add_pd(ar, br);
                        let abi = _mm256_add_pd(ai, bi);
                        let cdr = _mm256_add_pd(cr, dr);
                        let cdi = _mm256_add_pd(ci, di);
                        let abd_r = _mm256_sub_pd(ar, br);
                        let abd_i = _mm256_sub_pd(ai, bi);
                        let cdd_r = _mm256_sub_pd(cr, dr);
                        let cdd_i = _mm256_sub_pd(ci, di);
                        store4(&mut a[i], _mm256_add_pd(abr, cdr), _mm256_add_pd(abi, cdi));
                        let (br, bi) = mul4(
                            _mm256_add_pd(abd_r, cdd_i),
                            _mm256_sub_pd(abd_i, cdd_r),
                            w1r,
                            w1i,
                        );
                        store4(&mut b[i], br, bi);
                        let (cr, ci) =
                            mul4(_mm256_sub_pd(abr, cdr), _mm256_sub_pd(abi, cdi), w2r, w2i);
                        store4(&mut c[i], cr, ci);
                        let (dr, di) = mul4(
                            _mm256_sub_pd(abd_r, cdd_i),
                            _mm256_add_pd(abd_i, cdd_r),
                            w3r,
                            w3i,
                        );
                        store4(&mut d[i], dr, di);
                    }
                    level += 2;
                }
            }
            let scale = _mm256_set1_pd(4.0 / n as f64);
            for value in a {
                let (re, im) = load4(value);
                store4(value, _mm256_mul_pd(re, scale), _mm256_mul_pd(im, scale));
            }
        });
    }

    #[target_feature(enable = "avx2,fma")]
    unsafe fn dot_one_soa(a: &mut [Complex4], b: &[Complex4]) {
        let n = a.len() * 4;
        RotateCache::ensure(n / 2);
        RotateCache::with(|cache| {
            for i in 0..a.len() {
                let (mut br, mut bi) = load4(&b[i]);
                let mut rr = _mm256_setzero_pd();
                let mut ri = _mm256_setzero_pd();
                let w = eval_twiddle(cache, 1, a.len(), i);
                let wr = _mm256_setr_pd(w.re, 1.0, 1.0, 1.0);
                let wi = _mm256_setr_pd(w.im, 0.0, 0.0, 0.0);
                for lane in 0..4 {
                    let ar = _mm256_set1_pd(a[i].re[lane]);
                    let ai = _mm256_set1_pd(a[i].im[lane]);
                    multiply_accumulate4(&mut rr, &mut ri, ar, ai, br, bi);
                    if lane != 3 {
                        br = _mm256_permute4x64_pd::<0x93>(br);
                        bi = _mm256_permute4x64_pd::<0x93>(bi);
                        (br, bi) = mul4(br, bi, wr, wi);
                    }
                }
                store4(&mut a[i], rr, ri);
            }
        });
    }

    #[inline]
    fn pack_f64(values: impl Iterator<Item = f64>, n: usize) -> Vec<Complex4> {
        let mut result = Vec::with_capacity(n / 4);
        advise_huge_pages(&mut result);
        result.resize(n / 4, Complex4::default());
        for (i, value) in values.enumerate() {
            if i < n {
                result[i >> 2].re[i & 3] = value;
            } else {
                result[(i - n) >> 2].im[i & 3] = value;
            }
        }
        result
    }

    #[target_feature(enable = "avx2,fma")]
    pub unsafe fn convolve_f64_avx2(
        a: impl ExactSizeIterator<Item = f64>,
        b: impl ExactSizeIterator<Item = f64>,
        range: std::ops::Range<usize>,
    ) -> Vec<f64> {
        let n = (range.end.next_power_of_two() / 2).max(4);
        let mut fa = pack_f64(a, n);
        let mut fb = pack_f64(b, n);
        fft_soa(&mut fa);
        fft_soa(&mut fb);
        dot_one_soa(&mut fa, &fb);
        drop(fb);
        ifft_soa(&mut fa);
        range
            .map(|i| {
                if i < n {
                    fa[i >> 2].re[i & 3]
                } else {
                    fa[(i - n) >> 2].im[i & 3]
                }
            })
            .collect()
    }
    #[target_feature(enable = "avx2")]
    pub unsafe fn convolve_i64_avx2(a: Vec<i64>, b: Vec<i64>, len: usize) -> Vec<i64> {
        super::convolve_i64_naive(a, b, len)
    }
    #[target_feature(enable = "avx512f,avx512dq,avx512cd,avx512bw,avx512vl")]
    pub unsafe fn convolve_i64_avx512(a: Vec<i64>, b: Vec<i64>, len: usize) -> Vec<i64> {
        super::convolve_i64_naive(a, b, len)
    }
}

fn bit_reverse<T>(f: &mut [T]) {
    let mut ip = vec![0u32];
    let mut k = f.len();
    let mut m = 1;
    while 2 * m < k {
        k /= 2;
        for j in 0..m {
            ip.push(ip[j] + k as u32);
        }
        m *= 2;
    }
    if m == k {
        for i in 1..m {
            for j in 0..i {
                let ji = j + ip[i] as usize;
                let ij = i + ip[j] as usize;
                f.swap(ji, ij);
            }
        }
    } else {
        for i in 1..m {
            for j in 0..i {
                let ji = j + ip[i] as usize;
                let ij = i + ip[j] as usize;
                f.swap(ji, ij);
                f.swap(ji + m, ij + m);
            }
        }
    }
}

fn real_twiddles(n: usize, inverse: bool, mut f: impl FnMut(usize, Complex<f64>)) {
    const BLOCK: usize = 256;
    let sign = if inverse { 1.0 } else { -1.0 };
    let step = Complex::primitive_nth_root_of_unity(sign * n as f64);
    for start in (1..n / 4).step_by(BLOCK) {
        let mut w = Complex::polar(1.0, sign * std::f64::consts::TAU * start as f64 / n as f64);
        for k in start..(start + BLOCK).min(n / 4) {
            f(k, w);
            w *= step;
        }
    }
}

pub fn transform_real(t: impl IntoIterator<Item = f64>, len: usize) -> Vec<Complex<f64>> {
    let n = len.max(4).next_power_of_two();
    let mut f = vec![Complex::zero(); n / 2];
    for (i, t) in t.into_iter().enumerate() {
        if i & 1 == 0 {
            f[i / 2].re = t;
        } else {
            f[i / 2].im = t;
        }
    }
    fft(&mut f);
    bit_reverse(&mut f);
    f[0] = Complex::new(f[0].re + f[0].im, f[0].re - f[0].im);
    f[n / 4] = f[n / 4].conjugate();
    real_twiddles(n, false, |k, wk| {
        let c = wk.conjugate().transpose() + 1.;
        let d = c * (f[k] - f[n / 2 - k].conjugate()) * 0.5;
        f[k] -= d;
        f[n / 2 - k] += d.conjugate();
    });
    f
}

pub fn inverse_transform_real(mut f: Vec<Complex<f64>>, len: usize) -> Vec<f64> {
    let n = len.max(4).next_power_of_two();
    assert_eq!(f.len(), n / 2);
    f[0] = Complex::new((f[0].re + f[0].im) * 0.5, (f[0].re - f[0].im) * 0.5);
    f[n / 4] = f[n / 4].conjugate();
    real_twiddles(n, true, |k, wk| {
        let c = wk.transpose().conjugate() + 1.;
        let d = c * (f[k] - f[n / 2 - k].conjugate()) * 0.5;
        f[k] -= d;
        f[n / 2 - k] += d.conjugate();
    });
    bit_reverse(&mut f);
    ifft(&mut f);
    let inv = 1. / (n / 2) as f64;
    (0..len)
        .map(|i| inv * if i & 1 == 0 { f[i / 2].re } else { f[i / 2].im })
        .collect()
}

impl<T> Complex<T>

where T: Mul<Output: Add>,

pub fn dot(self, rhs: Self) -> <<T as Mul>::Output as Add>::Output

Examples found in repository

crates/competitive/src/geometry/line.rs (line 27)

    pub fn is_orthogonal(&self, other: &Self) -> bool {
        Approx(self.dir().dot(other.dir())) == Approx(T::zero())
    }
}
impl<T> Line<T>
where
    T: Ccwable + Float,
{
    pub fn projection(&self, p: Complex<T>) -> Complex<T> {
        let e = self.dir().unit();
        self.p1 + e * (p - self.p1).dot(e)
    }
    pub fn reflection(&self, p: Complex<T>) -> Complex<T> {
        let d = self.projection(p) - p;
        p + d + d
    }
    pub fn distance_point(&self, p: Complex<T>) -> T {
        (p / self.dir().unit()).re
    }
}

#[derive(Clone, Debug, PartialEq)]
pub struct LineSegment<T> {
    p1: Complex<T>,
    p2: Complex<T>,
}
impl<T> LineSegment<T> {
    pub fn new(p1: Complex<T>, p2: Complex<T>) -> Self {
        LineSegment { p1, p2 }
    }
}
impl<T> LineSegment<T>
where
    T: Ccwable,
{
    pub fn dir(&self) -> Complex<T> {
        self.p2 - self.p1
    }
    pub fn ccw(&self, p: Complex<T>) -> Ccw {
        Ccw::new(self.p1, self.p2, p)
    }
    pub fn is_parallel(&self, other: &Self) -> bool {
        Approx(self.dir().cross(other.dir())) == Approx(T::zero())
    }
    pub fn is_orthogonal(&self, other: &Self) -> bool {
        Approx(self.dir().dot(other.dir())) == Approx(T::zero())
    }
    pub fn intersect(&self, other: &Self) -> bool {
        self.ccw(other.p1) as i8 * self.ccw(other.p2) as i8 <= 0
            && other.ccw(self.p1) as i8 * other.ccw(self.p2) as i8 <= 0
    }
    pub fn intersect_point(&self, p: Complex<T>) -> bool {
        self.ccw(p) == Ccw::OnSegment
    }
}
impl<T> LineSegment<T>
where
    T: Ccwable + Float,
{
    pub fn projection(&self, p: Complex<T>) -> Complex<T> {
        let e = self.dir().unit();
        self.p1 + e * (p - self.p1).dot(e)
    }

crates/competitive/src/geometry/ccw.rs (line 46)

    pub fn new<T>(a: Complex<T>, b: Complex<T>, c: Complex<T>) -> Self
    where
        T: Ccwable,
    {
        let x = b - a;
        let y = c - a;
        let zero = T::zero();
        match x.cross(y).approx_cmp(&zero) {
            Ordering::Less => Self::Clockwise,
            Ordering::Greater => Self::CounterClockwise,
            Ordering::Equal => {
                if Approx(x.dot(y)) < Approx(zero) {
                    Self::OnlineBack
                } else if Approx((a - b).dot(c - b)) < Approx(zero) {
                    Self::OnlineFront
                } else {
                    Self::OnSegment
                }
            }
        }
    }
    pub fn new_open<T>(a: Complex<T>, b: Complex<T>, c: Complex<T>) -> Self
    where
        T: Ccwable,
    {
        let x = b - a;
        let y = c - a;
        let zero = T::zero();
        match x.cross(y).approx_cmp(&zero) {
            Ordering::Less => Self::Clockwise,
            Ordering::Greater => Self::CounterClockwise,
            Ordering::Equal => {
                if Approx(x.dot(y)) <= Approx(zero) {
                    Self::OnlineBack
                } else if Approx((a - b).dot(c - b)) <= Approx(zero) {
                    Self::OnlineFront
                } else {
                    Self::OnSegment
                }
            }
        }
    }

impl<T> Complex<T>

where T: Mul<Output: Sub>,

pub fn cross(self, rhs: Self) -> <<T as Mul>::Output as Sub>::Output

Examples found in repository

crates/competitive/src/geometry/line.rs (line 24)

    pub fn is_parallel(&self, other: &Self) -> bool {
        Approx(self.dir().cross(other.dir())) == Approx(T::zero())
    }
    pub fn is_orthogonal(&self, other: &Self) -> bool {
        Approx(self.dir().dot(other.dir())) == Approx(T::zero())
    }
}
impl<T> Line<T>
where
    T: Ccwable + Float,
{
    pub fn projection(&self, p: Complex<T>) -> Complex<T> {
        let e = self.dir().unit();
        self.p1 + e * (p - self.p1).dot(e)
    }
    pub fn reflection(&self, p: Complex<T>) -> Complex<T> {
        let d = self.projection(p) - p;
        p + d + d
    }
    pub fn distance_point(&self, p: Complex<T>) -> T {
        (p / self.dir().unit()).re
    }
}

#[derive(Clone, Debug, PartialEq)]
pub struct LineSegment<T> {
    p1: Complex<T>,
    p2: Complex<T>,
}
impl<T> LineSegment<T> {
    pub fn new(p1: Complex<T>, p2: Complex<T>) -> Self {
        LineSegment { p1, p2 }
    }
}
impl<T> LineSegment<T>
where
    T: Ccwable,
{
    pub fn dir(&self) -> Complex<T> {
        self.p2 - self.p1
    }
    pub fn ccw(&self, p: Complex<T>) -> Ccw {
        Ccw::new(self.p1, self.p2, p)
    }
    pub fn is_parallel(&self, other: &Self) -> bool {
        Approx(self.dir().cross(other.dir())) == Approx(T::zero())
    }
    pub fn is_orthogonal(&self, other: &Self) -> bool {
        Approx(self.dir().dot(other.dir())) == Approx(T::zero())
    }
    pub fn intersect(&self, other: &Self) -> bool {
        self.ccw(other.p1) as i8 * self.ccw(other.p2) as i8 <= 0
            && other.ccw(self.p1) as i8 * other.ccw(self.p2) as i8 <= 0
    }
    pub fn intersect_point(&self, p: Complex<T>) -> bool {
        self.ccw(p) == Ccw::OnSegment
    }
}
impl<T> LineSegment<T>
where
    T: Ccwable + Float,
{
    pub fn projection(&self, p: Complex<T>) -> Complex<T> {
        let e = self.dir().unit();
        self.p1 + e * (p - self.p1).dot(e)
    }
    pub fn reflection(&self, p: Complex<T>) -> Complex<T> {
        let d = self.projection(p) - p;
        p + d + d
    }
    pub fn cross_point(&self, other: &Self) -> Option<Complex<T>> {
        if self.intersect(other) {
            let a = self.dir().cross(other.dir());
            let b = self.dir().cross(self.p2 - other.p1);
            if Approx(a.abs()) == Approx(T::zero()) && Approx(b.abs()) == Approx(T::zero()) {
                Some(other.p1)
            } else {
                Some(other.p1 + (other.dir() * b / a))
            }
        } else {
            None
        }
    }

crates/competitive/src/geometry/ccw.rs (line 42)

    pub fn new<T>(a: Complex<T>, b: Complex<T>, c: Complex<T>) -> Self
    where
        T: Ccwable,
    {
        let x = b - a;
        let y = c - a;
        let zero = T::zero();
        match x.cross(y).approx_cmp(&zero) {
            Ordering::Less => Self::Clockwise,
            Ordering::Greater => Self::CounterClockwise,
            Ordering::Equal => {
                if Approx(x.dot(y)) < Approx(zero) {
                    Self::OnlineBack
                } else if Approx((a - b).dot(c - b)) < Approx(zero) {
                    Self::OnlineFront
                } else {
                    Self::OnSegment
                }
            }
        }
    }
    pub fn new_open<T>(a: Complex<T>, b: Complex<T>, c: Complex<T>) -> Self
    where
        T: Ccwable,
    {
        let x = b - a;
        let y = c - a;
        let zero = T::zero();
        match x.cross(y).approx_cmp(&zero) {
            Ordering::Less => Self::Clockwise,
            Ordering::Greater => Self::CounterClockwise,
            Ordering::Equal => {
                if Approx(x.dot(y)) <= Approx(zero) {
                    Self::OnlineBack
                } else if Approx((a - b).dot(c - b)) <= Approx(zero) {
                    Self::OnlineFront
                } else {
                    Self::OnSegment
                }
            }
        }
    }

crates/competitive/src/geometry/polygon.rs (line 34)

pub fn convex_diameter<T>(ps: &[Complex<T>]) -> T
where
    T: PartialOrd + Ccwable,
{
    let n = ps.len();
    let mut i = (0..n).max_by_key(|&i| TotalOrd(ps[i].re)).unwrap_or(0);
    let mut j = (0..n).min_by_key(|&i| TotalOrd(ps[i].re)).unwrap_or(0);
    let mut res = (ps[i] - ps[j]).norm();
    let (maxi, maxj) = (i, j);
    loop {
        let (ni, nj) = ((i + 1) % n, (j + 1) % n);
        if Approx((ps[ni] - ps[i]).cross(ps[nj] - ps[j])) < Approx(T::zero()) {
            i = ni;
        } else {
            j = nj;
        }
        let d = (ps[i] - ps[j]).norm();
        if res < d {
            res = d;
        }
        if i == maxi && j == maxj {
            break;
        }
    }
    res
}

impl<T> Complex<T>

where T: Mul<Output: Add> + Clone,

pub fn norm(self) -> <<T as Mul>::Output as Add>::Output

Examples found in repository

crates/competitive/src/geometry/polygon.rs (line 30)

pub fn convex_diameter<T>(ps: &[Complex<T>]) -> T
where
    T: PartialOrd + Ccwable,
{
    let n = ps.len();
    let mut i = (0..n).max_by_key(|&i| TotalOrd(ps[i].re)).unwrap_or(0);
    let mut j = (0..n).min_by_key(|&i| TotalOrd(ps[i].re)).unwrap_or(0);
    let mut res = (ps[i] - ps[j]).norm();
    let (maxi, maxj) = (i, j);
    loop {
        let (ni, nj) = ((i + 1) % n, (j + 1) % n);
        if Approx((ps[ni] - ps[i]).cross(ps[nj] - ps[j])) < Approx(T::zero()) {
            i = ni;
        } else {
            j = nj;
        }
        let d = (ps[i] - ps[j]).norm();
        if res < d {
            res = d;
        }
        if i == maxi && j == maxj {
            break;
        }
    }
    res
}

impl<T> Complex<T>

where T: Zero + Ord + Mul<Output: Ord>,

pub fn cmp_by_arg(self, other: Self) -> Ordering

impl<T> Complex<T>

where T: Float,

pub fn polar(r: T, theta: T) -> Self

Examples found in repository

crates/competitive/src/math/fast_fourier_transform.rs (line 374)

fn real_twiddles(n: usize, inverse: bool, mut f: impl FnMut(usize, Complex<f64>)) {
    const BLOCK: usize = 256;
    let sign = if inverse { 1.0 } else { -1.0 };
    let step = Complex::primitive_nth_root_of_unity(sign * n as f64);
    for start in (1..n / 4).step_by(BLOCK) {
        let mut w = Complex::polar(1.0, sign * std::f64::consts::TAU * start as f64 / n as f64);
        for k in start..(start + BLOCK).min(n / 4) {
            f(k, w);
            w *= step;
        }
    }
}

pub fn primitive_nth_root_of_unity(n: T) -> Self

Examples found in repository

crates/competitive/src/math/fast_fourier_transform.rs (line 27)

    pub fn ensure(n: usize) {
        assert_eq!(n.count_ones(), 1, "call with power of two but {}", n);
        Self::modify(|cache| {
            let mut m = cache.len();
            assert!(
                m.count_ones() <= 1,
                "length might be power of two but {}",
                m
            );
            if m >= n {
                return;
            }
            cache.reserve_exact(n - m);
            if cache.is_empty() {
                cache.push(Complex::one());
                m += 1;
            }
            while m < n {
                let p = Complex::primitive_nth_root_of_unity(-((m * 4) as f64));
                for i in 0..m {
                    cache.push(cache[i] * p);
                }
                m <<= 1;
            }
            assert_eq!(cache.len(), n);
        });
    }
}
crate::impl_assoc_value!(RotateCache, Vec<Complex<f64>>, vec![Complex::one()]);

#[cfg(target_arch = "x86_64")]
pub mod simd {
    // These primitives are called only after AVX2 and FMA have been detected.
    #![allow(clippy::missing_safety_doc, unsafe_op_in_unsafe_fn)]

    use super::{AssociatedValue, Complex, RotateCache, advise_huge_pages};
    use std::arch::x86_64::*;

    #[derive(Clone, Copy, Default)]
    #[repr(C, align(32))]
    pub struct Complex4 {
        pub re: [f64; 4],
        pub im: [f64; 4],
    }

    #[target_feature(enable = "avx2,fma")]
    #[inline]
    pub unsafe fn load4(value: &Complex4) -> (__m256d, __m256d) {
        (
            _mm256_load_pd(value.re.as_ptr()),
            _mm256_load_pd(value.im.as_ptr()),
        )
    }

    #[target_feature(enable = "avx2,fma")]
    #[inline]
    pub unsafe fn store4(value: &mut Complex4, re: __m256d, im: __m256d) {
        _mm256_store_pd(value.re.as_mut_ptr(), re);
        _mm256_store_pd(value.im.as_mut_ptr(), im);
    }

    #[target_feature(enable = "avx2,fma")]
    #[inline]
    pub unsafe fn mul4(ar: __m256d, ai: __m256d, br: __m256d, bi: __m256d) -> (__m256d, __m256d) {
        (
            _mm256_fmsub_pd(ar, br, _mm256_mul_pd(ai, bi)),
            _mm256_fmadd_pd(ai, br, _mm256_mul_pd(ar, bi)),
        )
    }

    #[target_feature(enable = "avx2,fma")]
    #[inline]
    pub unsafe fn multiply_accumulate4(
        rr: &mut __m256d,
        ri: &mut __m256d,
        ar: __m256d,
        ai: __m256d,
        br: __m256d,
        bi: __m256d,
    ) {
        *rr = _mm256_fmadd_pd(ar, br, *rr);
        *rr = _mm256_fnmadd_pd(ai, bi, *rr);
        *ri = _mm256_fmadd_pd(ai, br, *ri);
        *ri = _mm256_fmadd_pd(ar, bi, *ri);
    }

    #[inline]
    pub fn eval_twiddle(cache: &[Complex<f64>], step: usize, n: usize, k: usize) -> Complex<f64> {
        let k = step * k;
        let w = cache[(k >> 2) << 1].conjugate();
        let w = match k & 3 {
            0 => w,
            1 => Complex::new(-w.re, -w.im),
            2 => Complex::new(-w.im, w.re),
            _ => Complex::new(w.im, -w.re),
        };
        cache[step * n].conjugate() * w
    }

    #[target_feature(enable = "avx2,fma")]
    pub unsafe fn fft_soa(a: &mut [Complex4]) {
        let n = a.len() * 4;
        RotateCache::ensure(n / 2);
        RotateCache::with(|cache| {
            let parity = n.trailing_zeros() & 1;
            for leaf in (0..n).step_by(16) {
                let mut level = (n + leaf).trailing_zeros();
                level -= u32::from(level & 1 != parity);
                while level >= 4 {
                    let len = 1usize << level;
                    let q = leaf >> level;
                    let width = len / 16;
                    let start = q * width * 4;
                    let (a, rest) = a[start..start + width * 4].split_at_mut(width);
                    let (b, rest) = rest.split_at_mut(width);
                    let (c, d) = rest.split_at_mut(width);
                    let w1 = eval_twiddle(cache, 4, n >> level, q);
                    let w2 = w1 * w1;
                    let w3 = w1 * w2;
                    let (w1r, w1i) = (_mm256_set1_pd(w1.re), _mm256_set1_pd(w1.im));
                    let (w2r, w2i) = (_mm256_set1_pd(w2.re), _mm256_set1_pd(w2.im));
                    let (w3r, w3i) = (_mm256_set1_pd(w3.re), _mm256_set1_pd(w3.im));
                    for i in 0..width {
                        let (ar, ai) = load4(&a[i]);
                        let (br, bi) = load4(&b[i]);
                        let (cr, ci) = load4(&c[i]);
                        let (dr, di) = load4(&d[i]);
                        let (br, bi) = mul4(br, bi, w1r, w1i);
                        let (cr, ci) = mul4(cr, ci, w2r, w2i);
                        let (dr, di) = mul4(dr, di, w3r, w3i);
                        let acr = _mm256_add_pd(ar, cr);
                        let aci = _mm256_add_pd(ai, ci);
                        let bdr = _mm256_add_pd(br, dr);
                        let bdi = _mm256_add_pd(bi, di);
                        let acd_r = _mm256_sub_pd(ar, cr);
                        let acd_i = _mm256_sub_pd(ai, ci);
                        let bdd_r = _mm256_sub_pd(br, dr);
                        let bdd_i = _mm256_sub_pd(bi, di);
                        store4(&mut a[i], _mm256_add_pd(acr, bdr), _mm256_add_pd(aci, bdi));
                        store4(&mut b[i], _mm256_sub_pd(acr, bdr), _mm256_sub_pd(aci, bdi));
                        store4(
                            &mut c[i],
                            _mm256_sub_pd(acd_r, bdd_i),
                            _mm256_add_pd(acd_i, bdd_r),
                        );
                        store4(
                            &mut d[i],
                            _mm256_add_pd(acd_r, bdd_i),
                            _mm256_sub_pd(acd_i, bdd_r),
                        );
                    }
                    level -= 2;
                }
            }
            if parity != 0 {
                let blocks = n / 8;
                for k in 0..blocks {
                    let w = eval_twiddle(cache, 2, blocks, k);
                    let wr = _mm256_set1_pd(w.re);
                    let wi = _mm256_set1_pd(w.im);
                    let (ar, ai) = load4(&a[k * 2]);
                    let (br, bi) = load4(&a[k * 2 + 1]);
                    let (br, bi) = mul4(br, bi, wr, wi);
                    store4(&mut a[k * 2], _mm256_add_pd(ar, br), _mm256_add_pd(ai, bi));
                    store4(
                        &mut a[k * 2 + 1],
                        _mm256_sub_pd(ar, br),
                        _mm256_sub_pd(ai, bi),
                    );
                }
            }
        });
    }

    #[target_feature(enable = "avx2,fma")]
    pub unsafe fn ifft_soa(a: &mut [Complex4]) {
        let n = a.len() * 4;
        RotateCache::ensure(n / 2);
        RotateCache::with(|cache| {
            let parity = n.trailing_zeros() & 1;
            if parity != 0 {
                let blocks = n / 8;
                for k in 0..blocks {
                    let w = eval_twiddle(cache, 2, blocks, k).conjugate();
                    let wr = _mm256_set1_pd(w.re);
                    let wi = _mm256_set1_pd(w.im);
                    let (ar, ai) = load4(&a[k * 2]);
                    let (br, bi) = load4(&a[k * 2 + 1]);
                    store4(&mut a[k * 2], _mm256_add_pd(ar, br), _mm256_add_pd(ai, bi));
                    let (br, bi) = mul4(_mm256_sub_pd(ar, br), _mm256_sub_pd(ai, bi), wr, wi);
                    store4(&mut a[k * 2 + 1], br, bi);
                }
            }
            for leaf in (12..n).step_by(16) {
                let max_level = (leaf + 3).trailing_ones();
                let mut level = 4 + parity;
                while level <= max_level {
                    let len = 1usize << level;
                    let q = leaf >> level;
                    let width = len / 16;
                    let start = q * width * 4;
                    let (a, rest) = a[start..start + width * 4].split_at_mut(width);
                    let (b, rest) = rest.split_at_mut(width);
                    let (c, d) = rest.split_at_mut(width);
                    let w1 = eval_twiddle(cache, 4, n >> level, q).conjugate();
                    let w2 = w1 * w1;
                    let w3 = w1 * w2;
                    let (w1r, w1i) = (_mm256_set1_pd(w1.re), _mm256_set1_pd(w1.im));
                    let (w2r, w2i) = (_mm256_set1_pd(w2.re), _mm256_set1_pd(w2.im));
                    let (w3r, w3i) = (_mm256_set1_pd(w3.re), _mm256_set1_pd(w3.im));
                    for i in 0..width {
                        let (ar, ai) = load4(&a[i]);
                        let (br, bi) = load4(&b[i]);
                        let (cr, ci) = load4(&c[i]);
                        let (dr, di) = load4(&d[i]);
                        let abr = _mm256_add_pd(ar, br);
                        let abi = _mm256_add_pd(ai, bi);
                        let cdr = _mm256_add_pd(cr, dr);
                        let cdi = _mm256_add_pd(ci, di);
                        let abd_r = _mm256_sub_pd(ar, br);
                        let abd_i = _mm256_sub_pd(ai, bi);
                        let cdd_r = _mm256_sub_pd(cr, dr);
                        let cdd_i = _mm256_sub_pd(ci, di);
                        store4(&mut a[i], _mm256_add_pd(abr, cdr), _mm256_add_pd(abi, cdi));
                        let (br, bi) = mul4(
                            _mm256_add_pd(abd_r, cdd_i),
                            _mm256_sub_pd(abd_i, cdd_r),
                            w1r,
                            w1i,
                        );
                        store4(&mut b[i], br, bi);
                        let (cr, ci) =
                            mul4(_mm256_sub_pd(abr, cdr), _mm256_sub_pd(abi, cdi), w2r, w2i);
                        store4(&mut c[i], cr, ci);
                        let (dr, di) = mul4(
                            _mm256_sub_pd(abd_r, cdd_i),
                            _mm256_add_pd(abd_i, cdd_r),
                            w3r,
                            w3i,
                        );
                        store4(&mut d[i], dr, di);
                    }
                    level += 2;
                }
            }
            let scale = _mm256_set1_pd(4.0 / n as f64);
            for value in a {
                let (re, im) = load4(value);
                store4(value, _mm256_mul_pd(re, scale), _mm256_mul_pd(im, scale));
            }
        });
    }

    #[target_feature(enable = "avx2,fma")]
    unsafe fn dot_one_soa(a: &mut [Complex4], b: &[Complex4]) {
        let n = a.len() * 4;
        RotateCache::ensure(n / 2);
        RotateCache::with(|cache| {
            for i in 0..a.len() {
                let (mut br, mut bi) = load4(&b[i]);
                let mut rr = _mm256_setzero_pd();
                let mut ri = _mm256_setzero_pd();
                let w = eval_twiddle(cache, 1, a.len(), i);
                let wr = _mm256_setr_pd(w.re, 1.0, 1.0, 1.0);
                let wi = _mm256_setr_pd(w.im, 0.0, 0.0, 0.0);
                for lane in 0..4 {
                    let ar = _mm256_set1_pd(a[i].re[lane]);
                    let ai = _mm256_set1_pd(a[i].im[lane]);
                    multiply_accumulate4(&mut rr, &mut ri, ar, ai, br, bi);
                    if lane != 3 {
                        br = _mm256_permute4x64_pd::<0x93>(br);
                        bi = _mm256_permute4x64_pd::<0x93>(bi);
                        (br, bi) = mul4(br, bi, wr, wi);
                    }
                }
                store4(&mut a[i], rr, ri);
            }
        });
    }

    #[inline]
    fn pack_f64(values: impl Iterator<Item = f64>, n: usize) -> Vec<Complex4> {
        let mut result = Vec::with_capacity(n / 4);
        advise_huge_pages(&mut result);
        result.resize(n / 4, Complex4::default());
        for (i, value) in values.enumerate() {
            if i < n {
                result[i >> 2].re[i & 3] = value;
            } else {
                result[(i - n) >> 2].im[i & 3] = value;
            }
        }
        result
    }

    #[target_feature(enable = "avx2,fma")]
    pub unsafe fn convolve_f64_avx2(
        a: impl ExactSizeIterator<Item = f64>,
        b: impl ExactSizeIterator<Item = f64>,
        range: std::ops::Range<usize>,
    ) -> Vec<f64> {
        let n = (range.end.next_power_of_two() / 2).max(4);
        let mut fa = pack_f64(a, n);
        let mut fb = pack_f64(b, n);
        fft_soa(&mut fa);
        fft_soa(&mut fb);
        dot_one_soa(&mut fa, &fb);
        drop(fb);
        ifft_soa(&mut fa);
        range
            .map(|i| {
                if i < n {
                    fa[i >> 2].re[i & 3]
                } else {
                    fa[(i - n) >> 2].im[i & 3]
                }
            })
            .collect()
    }
    #[target_feature(enable = "avx2")]
    pub unsafe fn convolve_i64_avx2(a: Vec<i64>, b: Vec<i64>, len: usize) -> Vec<i64> {
        super::convolve_i64_naive(a, b, len)
    }
    #[target_feature(enable = "avx512f,avx512dq,avx512cd,avx512bw,avx512vl")]
    pub unsafe fn convolve_i64_avx512(a: Vec<i64>, b: Vec<i64>, len: usize) -> Vec<i64> {
        super::convolve_i64_naive(a, b, len)
    }
}

fn bit_reverse<T>(f: &mut [T]) {
    let mut ip = vec![0u32];
    let mut k = f.len();
    let mut m = 1;
    while 2 * m < k {
        k /= 2;
        for j in 0..m {
            ip.push(ip[j] + k as u32);
        }
        m *= 2;
    }
    if m == k {
        for i in 1..m {
            for j in 0..i {
                let ji = j + ip[i] as usize;
                let ij = i + ip[j] as usize;
                f.swap(ji, ij);
            }
        }
    } else {
        for i in 1..m {
            for j in 0..i {
                let ji = j + ip[i] as usize;
                let ij = i + ip[j] as usize;
                f.swap(ji, ij);
                f.swap(ji + m, ij + m);
            }
        }
    }
}

fn real_twiddles(n: usize, inverse: bool, mut f: impl FnMut(usize, Complex<f64>)) {
    const BLOCK: usize = 256;
    let sign = if inverse { 1.0 } else { -1.0 };
    let step = Complex::primitive_nth_root_of_unity(sign * n as f64);
    for start in (1..n / 4).step_by(BLOCK) {
        let mut w = Complex::polar(1.0, sign * std::f64::consts::TAU * start as f64 / n as f64);
        for k in start..(start + BLOCK).min(n / 4) {
            f(k, w);
            w *= step;
        }
    }
}

pub fn abs(self) -> T

Examples found in repository

crates/competitive/src/num/complex.rs (line 113)

    pub fn unit(self) -> Self {
        self / self.abs()
    }

crates/competitive/src/geometry/line.rs (line 109)

    pub fn distance_point(&self, p: Complex<T>) -> T {
        let r = self.projection(p);
        if self.intersect_point(r) {
            (r - p).abs()
        } else {
            (self.p1 - p).abs().min((self.p2 - p).abs())
        }
    }

crates/competitive/src/geometry/circle.rs (line 16)

    pub fn cross_circle(&self, other: &Self) -> Option<(Complex<T>, Complex<T>)> {
        let d = (self.c - other.c).abs();
        let rc = (d * d + self.r * self.r - other.r * other.r) / (d + d);
        let rs2 = self.r * self.r - rc * rc;
        if Approx(rs2) < Approx(T::zero()) {
            return None;
        }
        let rs = rs2.abs().sqrt();
        let diff = (other.c - self.c) / d;
        Some((
            self.c + diff * Complex::new(rc, rs),
            self.c + diff * Complex::new(rc, -rs),
        ))
    }
    pub fn contains_point(&self, p: Complex<T>) -> bool {
        Approx((self.c - p).abs()) <= Approx(self.r)
    }

crates/competitive/src/geometry/closest_pair.rs (line 33)

fn closest_pair_inner(a: &mut [Complex<f64>]) -> f64 {
    use std::cmp::min;
    let n = a.len();
    if n <= 1 {
        return f64::INFINITY;
    }
    let m = n / 2;
    let x = a[m].re;
    let mut d = min(
        TotalOrd(closest_pair_inner(&mut a[0..m])),
        TotalOrd(closest_pair_inner(&mut a[m..n])),
    )
    .0;
    a.sort_by_key(|&p| TotalOrd(p.im));
    let mut b: Vec<Complex<f64>> = vec![];
    for a in a.iter() {
        if (a.re - x).abs() >= d {
            continue;
        }
        let k = b.len();
        for j in 0..k {
            let p = *a - b[k - j - 1];
            if p.im >= d {
                break;
            }
            d = min(TotalOrd(d), TotalOrd(p.abs())).0;
        }
        b.push(*a);
    }
    d
}

pub fn unit(self) -> Self

Examples found in repository

crates/competitive/src/geometry/line.rs (line 35)

    pub fn projection(&self, p: Complex<T>) -> Complex<T> {
        let e = self.dir().unit();
        self.p1 + e * (p - self.p1).dot(e)
    }
    pub fn reflection(&self, p: Complex<T>) -> Complex<T> {
        let d = self.projection(p) - p;
        p + d + d
    }
    pub fn distance_point(&self, p: Complex<T>) -> T {
        (p / self.dir().unit()).re
    }
}

#[derive(Clone, Debug, PartialEq)]
pub struct LineSegment<T> {
    p1: Complex<T>,
    p2: Complex<T>,
}
impl<T> LineSegment<T> {
    pub fn new(p1: Complex<T>, p2: Complex<T>) -> Self {
        LineSegment { p1, p2 }
    }
}
impl<T> LineSegment<T>
where
    T: Ccwable,
{
    pub fn dir(&self) -> Complex<T> {
        self.p2 - self.p1
    }
    pub fn ccw(&self, p: Complex<T>) -> Ccw {
        Ccw::new(self.p1, self.p2, p)
    }
    pub fn is_parallel(&self, other: &Self) -> bool {
        Approx(self.dir().cross(other.dir())) == Approx(T::zero())
    }
    pub fn is_orthogonal(&self, other: &Self) -> bool {
        Approx(self.dir().dot(other.dir())) == Approx(T::zero())
    }
    pub fn intersect(&self, other: &Self) -> bool {
        self.ccw(other.p1) as i8 * self.ccw(other.p2) as i8 <= 0
            && other.ccw(self.p1) as i8 * other.ccw(self.p2) as i8 <= 0
    }
    pub fn intersect_point(&self, p: Complex<T>) -> bool {
        self.ccw(p) == Ccw::OnSegment
    }
}
impl<T> LineSegment<T>
where
    T: Ccwable + Float,
{
    pub fn projection(&self, p: Complex<T>) -> Complex<T> {
        let e = self.dir().unit();
        self.p1 + e * (p - self.p1).dot(e)
    }

pub fn angle(self) -> T

Trait Implementations

impl<T> Add for Complex<T>

where T: Add,

type Output = Complex<<T as Add>::Output>

The resulting type after applying the + operator.

fn add(self, rhs: Self) -> Self::Output

Performs the + operation.

impl<T> Add<&Complex<T>> for Complex<T>

where T: Clone + Add<Output = T>,

type Output = <Complex<T> as Add>::Output

The resulting type after applying the + operator.

fn add(self, rhs: &Complex<T>) -> <Complex<T> as Add<Complex<T>>>::Output

Performs the + operation.

impl<T> Add<&Complex<T>> for &Complex<T>

where T: Clone + Add<Output = T>,

type Output = <Complex<T> as Add>::Output

The resulting type after applying the + operator.

fn add(self, rhs: &Complex<T>) -> <Complex<T> as Add<Complex<T>>>::Output

Performs the + operation.

impl<T> Add<&T> for Complex<T>

where T: Clone + Add<Output = T>,

type Output = <Complex<T> as Add<T>>::Output

The resulting type after applying the + operator.

fn add(self, rhs: &T) -> <Complex<T> as Add<T>>::Output

Performs the + operation.

impl<T> Add<&T> for &Complex<T>

where T: Clone + Add<Output = T>,

type Output = <Complex<T> as Add<T>>::Output

The resulting type after applying the + operator.

fn add(self, rhs: &T) -> <Complex<T> as Add<T>>::Output

Performs the + operation.

impl<T> Add<Complex<T>> for &Complex<T>

where T: Clone + Add<Output = T>,

type Output = <Complex<T> as Add>::Output

The resulting type after applying the + operator.

fn add(self, rhs: Complex<T>) -> <Complex<T> as Add<Complex<T>>>::Output

Performs the + operation.

impl<T> Add<T> for Complex<T>

where T: Add<Output = T>,

type Output = Complex<T>

The resulting type after applying the + operator.

fn add(self, rhs: T) -> Self::Output

Performs the + operation.

impl<T> Add<T> for &Complex<T>

where T: Clone + Add<Output = T>,

type Output = <Complex<T> as Add<T>>::Output

The resulting type after applying the + operator.

fn add(self, rhs: T) -> <Complex<T> as Add<T>>::Output

Performs the + operation.

impl<T> AddAssign for Complex<T>

where T: Clone + Add<Output = T>,

fn add_assign(&mut self, rhs: Complex<T>)

Performs the += operation.

impl<T> AddAssign<&Complex<T>> for Complex<T>

where T: Clone + Add<Output = T>,

fn add_assign(&mut self, rhs: &Complex<T>)

Performs the += operation.

impl<T> AddAssign<&T> for Complex<T>

where T: Clone + Add<Output = T>,

fn add_assign(&mut self, rhs: &T)

Performs the += operation.

impl<T> AddAssign<T> for Complex<T>

where T: Clone + Add<Output = T>,

fn add_assign(&mut self, rhs: T)

Performs the += operation.

impl<T: Clone> Clone for Complex<T>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Copy> Copy for Complex<T>

impl<T: Debug> Debug for Complex<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Default> Default for Complex<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T> Div for Complex<T>

where T: Clone + Add<Output = T> + Sub<Output = T> + Mul<Output = T> + Div,

type Output = Complex<<T as Div>::Output>

The resulting type after applying the / operator.

fn div(self, rhs: Self) -> Self::Output

Performs the / operation.

impl<T> Div<&Complex<T>> for Complex<T>

where T: Clone + Add<Output = T> + Sub<Output = T> + Mul<Output = T> + Div<Output = T>,

type Output = <Complex<T> as Div>::Output

The resulting type after applying the / operator.

fn div(self, rhs: &Complex<T>) -> <Complex<T> as Div<Complex<T>>>::Output

Performs the / operation.

impl<T> Div<&Complex<T>> for &Complex<T>

where T: Clone + Add<Output = T> + Sub<Output = T> + Mul<Output = T> + Div<Output = T>,

type Output = <Complex<T> as Div>::Output

The resulting type after applying the / operator.

fn div(self, rhs: &Complex<T>) -> <Complex<T> as Div<Complex<T>>>::Output

Performs the / operation.

impl<T> Div<&T> for Complex<T>

where T: Clone + Div<Output = T>,

type Output = <Complex<T> as Div<T>>::Output

The resulting type after applying the / operator.

fn div(self, rhs: &T) -> <Complex<T> as Div<T>>::Output

Performs the / operation.

impl<T> Div<&T> for &Complex<T>

where T: Clone + Div<Output = T>,

type Output = <Complex<T> as Div<T>>::Output

The resulting type after applying the / operator.

fn div(self, rhs: &T) -> <Complex<T> as Div<T>>::Output

Performs the / operation.

impl<T> Div<Complex<T>> for &Complex<T>

where T: Clone + Add<Output = T> + Sub<Output = T> + Mul<Output = T> + Div<Output = T>,

type Output = <Complex<T> as Div>::Output

The resulting type after applying the / operator.

fn div(self, rhs: Complex<T>) -> <Complex<T> as Div<Complex<T>>>::Output

Performs the / operation.

impl<T> Div<T> for Complex<T>

where T: Clone + Div,

type Output = Complex<<T as Div>::Output>

The resulting type after applying the / operator.

fn div(self, rhs: T) -> Self::Output

Performs the / operation.

impl<T> Div<T> for &Complex<T>

where T: Clone + Div<Output = T>,

type Output = <Complex<T> as Div<T>>::Output

The resulting type after applying the / operator.

fn div(self, rhs: T) -> <Complex<T> as Div<T>>::Output

Performs the / operation.

impl<T> DivAssign for Complex<T>

where T: Clone + Add<Output = T> + Sub<Output = T> + Mul<Output = T> + Div<Output = T>,

fn div_assign(&mut self, rhs: Complex<T>)

Performs the /= operation.

impl<T> DivAssign<&Complex<T>> for Complex<T>

where T: Clone + Add<Output = T> + Sub<Output = T> + Mul<Output = T> + Div<Output = T>,

fn div_assign(&mut self, rhs: &Complex<T>)

Performs the /= operation.

impl<T> DivAssign<&T> for Complex<T>

where T: Clone + Div<Output = T>,

fn div_assign(&mut self, rhs: &T)

Performs the /= operation.

impl<T> DivAssign<T> for Complex<T>

where T: Clone + Div<Output = T>,

fn div_assign(&mut self, rhs: T)

Performs the /= operation.

impl<T: Eq> Eq for Complex<T>

impl<T: Hash> Hash for Complex<T>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<T, U> Mul for Complex<T>

where T: Clone + Mul, <T as Mul>::Output: Add<Output = U> + Sub<Output = U>,

type Output = Complex<U>

The resulting type after applying the * operator.

fn mul(self, rhs: Self) -> Self::Output

Performs the * operation.

impl<T> Mul<&Complex<T>> for Complex<T>

where T: Clone + Add<Output = T> + Sub<Output = T> + Mul<Output = T>,

type Output = <Complex<T> as Mul>::Output

The resulting type after applying the * operator.

fn mul(self, rhs: &Complex<T>) -> <Complex<T> as Mul<Complex<T>>>::Output

Performs the * operation.

impl<T> Mul<&Complex<T>> for &Complex<T>

where T: Clone + Add<Output = T> + Sub<Output = T> + Mul<Output = T>,

type Output = <Complex<T> as Mul>::Output

The resulting type after applying the * operator.

fn mul(self, rhs: &Complex<T>) -> <Complex<T> as Mul<Complex<T>>>::Output

Performs the * operation.

impl<T> Mul<&T> for Complex<T>

where T: Clone + Mul<Output = T>,

type Output = <Complex<T> as Mul<T>>::Output

The resulting type after applying the * operator.

fn mul(self, rhs: &T) -> <Complex<T> as Mul<T>>::Output

Performs the * operation.

impl<T> Mul<&T> for &Complex<T>

where T: Clone + Mul<Output = T>,

type Output = <Complex<T> as Mul<T>>::Output

The resulting type after applying the * operator.

fn mul(self, rhs: &T) -> <Complex<T> as Mul<T>>::Output

Performs the * operation.

impl<T> Mul<Complex<T>> for &Complex<T>

where T: Clone + Add<Output = T> + Sub<Output = T> + Mul<Output = T>,

type Output = <Complex<T> as Mul>::Output

The resulting type after applying the * operator.

fn mul(self, rhs: Complex<T>) -> <Complex<T> as Mul<Complex<T>>>::Output

Performs the * operation.

impl<T> Mul<T> for Complex<T>

where T: Clone + Mul,

type Output = Complex<<T as Mul>::Output>

The resulting type after applying the * operator.

fn mul(self, rhs: T) -> Self::Output

Performs the * operation.

impl<T> Mul<T> for &Complex<T>

where T: Clone + Mul<Output = T>,

type Output = <Complex<T> as Mul<T>>::Output

The resulting type after applying the * operator.

fn mul(self, rhs: T) -> <Complex<T> as Mul<T>>::Output

Performs the * operation.

impl<T> MulAssign for Complex<T>

where T: Clone + Add<Output = T> + Sub<Output = T> + Mul<Output = T>,

fn mul_assign(&mut self, rhs: Complex<T>)

Performs the *= operation.

impl<T> MulAssign<&Complex<T>> for Complex<T>

where T: Clone + Add<Output = T> + Sub<Output = T> + Mul<Output = T>,

fn mul_assign(&mut self, rhs: &Complex<T>)

Performs the *= operation.

impl<T> MulAssign<&T> for Complex<T>

where T: Clone + Mul<Output = T>,

fn mul_assign(&mut self, rhs: &T)

Performs the *= operation.

impl<T> MulAssign<T> for Complex<T>

where T: Clone + Mul<Output = T>,

fn mul_assign(&mut self, rhs: T)

Performs the *= operation.

impl<T> Neg for Complex<T>

where T: Neg,

type Output = Complex<<T as Neg>::Output>

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - operation.

impl<T> Neg for &Complex<T>

where T: Clone + Neg<Output = T>,

type Output = <Complex<T> as Neg>::Output

The resulting type after applying the - operator.

fn neg(self) -> <Complex<T> as Neg>::Output

Performs the unary - operation.

impl<T> One for Complex<T>

where T: Zero + One,

fn one() -> Self

fn is_one(&self) -> bool

where Self: PartialEq,

fn set_one(&mut self)

impl<T: Ord> Ord for Complex<T>

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

fn clamp_to<R>(self, range: R) -> Self

where Self: Sized, R: ClampBounds<Self>,

🔬This is a nightly-only experimental API. (clamp_to)

Restrict a value to a certain range.

impl<T: PartialEq> PartialEq for Complex<T>

fn eq(&self, other: &Self) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl<T: PartialOrd> PartialOrd for Complex<T>

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<T> Product for Complex<T>

where T: One + Add<Output = T> + Sub<Output = T> + Mul<Output = T> + Zero + Clone,

fn product<I: Iterator<Item = Self>>(iter: I) -> Self

Takes an iterator and generates Self from the elements by multiplying the items.

impl<'a, T> Product<&'a Complex<T>> for Complex<T>

where T: Clone + One + Add<Output = T> + Sub<Output = T> + Mul<Output = T> + Zero + 'a,

fn product<I: Iterator<Item = &'a Complex<T>>>(iter: I) -> Self

Takes an iterator and generates Self from the elements by multiplying the items.

impl<T: Scan> Scan for Complex<T>

type Output = Complex<<T as Scan>::Output>

fn scan<I: ScanSource>(iter: &mut I) -> Option<Self::Output>

impl<T: PartialEq> StructuralPartialEq for Complex<T>

impl<T> Sub for Complex<T>

where T: Sub,

type Output = Complex<<T as Sub>::Output>

The resulting type after applying the - operator.

fn sub(self, rhs: Self) -> Self::Output

Performs the - operation.

impl<T> Sub<&Complex<T>> for Complex<T>

where T: Clone + Sub<Output = T>,

type Output = <Complex<T> as Sub>::Output

The resulting type after applying the - operator.

fn sub(self, rhs: &Complex<T>) -> <Complex<T> as Sub<Complex<T>>>::Output

Performs the - operation.

impl<T> Sub<&Complex<T>> for &Complex<T>

where T: Clone + Sub<Output = T>,

type Output = <Complex<T> as Sub>::Output

The resulting type after applying the - operator.

fn sub(self, rhs: &Complex<T>) -> <Complex<T> as Sub<Complex<T>>>::Output

Performs the - operation.

impl<T> Sub<&T> for Complex<T>

where T: Clone + Sub<Output = T>,

type Output = <Complex<T> as Sub<T>>::Output

The resulting type after applying the - operator.

fn sub(self, rhs: &T) -> <Complex<T> as Sub<T>>::Output

Performs the - operation.

impl<T> Sub<&T> for &Complex<T>

where T: Clone + Sub<Output = T>,

type Output = <Complex<T> as Sub<T>>::Output

The resulting type after applying the - operator.

fn sub(self, rhs: &T) -> <Complex<T> as Sub<T>>::Output

Performs the - operation.

impl<T> Sub<Complex<T>> for &Complex<T>

where T: Clone + Sub<Output = T>,

type Output = <Complex<T> as Sub>::Output

The resulting type after applying the - operator.

fn sub(self, rhs: Complex<T>) -> <Complex<T> as Sub<Complex<T>>>::Output

Performs the - operation.

impl<T> Sub<T> for Complex<T>

where T: Sub<Output = T>,

type Output = Complex<T>

The resulting type after applying the - operator.

fn sub(self, rhs: T) -> Self::Output

Performs the - operation.

impl<T> Sub<T> for &Complex<T>

where T: Clone + Sub<Output = T>,

type Output = <Complex<T> as Sub<T>>::Output

The resulting type after applying the - operator.

fn sub(self, rhs: T) -> <Complex<T> as Sub<T>>::Output

Performs the - operation.

impl<T> SubAssign for Complex<T>

where T: Clone + Sub<Output = T>,

fn sub_assign(&mut self, rhs: Complex<T>)

Performs the -= operation.

impl<T> SubAssign<&Complex<T>> for Complex<T>

where T: Clone + Sub<Output = T>,

fn sub_assign(&mut self, rhs: &Complex<T>)

Performs the -= operation.

impl<T> SubAssign<&T> for Complex<T>

where T: Clone + Sub<Output = T>,

fn sub_assign(&mut self, rhs: &T)

Performs the -= operation.

impl<T> SubAssign<T> for Complex<T>

where T: Clone + Sub<Output = T>,

fn sub_assign(&mut self, rhs: T)

Performs the -= operation.

impl<T> Sum for Complex<T>

where T: Zero + Add<Output = T>,

fn sum<I: Iterator<Item = Self>>(iter: I) -> Self

Takes an iterator and generates Self from the elements by “summing up” the items.

impl<'a, T> Sum<&'a Complex<T>> for Complex<T>

where T: Clone + Zero + Add<Output = T> + 'a,

fn sum<I: Iterator<Item = &'a Complex<T>>>(iter: I) -> Self

Takes an iterator and generates Self from the elements by “summing up” the items.

impl<T> Zero for Complex<T>

where T: Zero,

fn zero() -> Self

fn is_zero(&self) -> bool

where Self: PartialEq,

fn set_zero(&mut self)