From gcc-patches Wed Sep 15 08:10:40 2010 From: Wang Feng Date: Wed, 15 Sep 2010 08:10:40 +0000 To: gcc-patches Subject: [PATCH, libstdc++, complex] complex multiplication algorithm improved Message-Id: X-MARC-Message: https://marc.info/?l=gcc-patches&m=128453825427015 MIME-Version: 1 Content-Type: multipart/mixed; boundary="--0015175cd11c8795a0049047ddaa" --0015175cd11c8795a0049047ddaa Content-Type: text/plain; charset=UTF-8 Hi, Complex number multiplication done with 4 multiplications, but this one only need 3: (a+ib)(c+id) = ac - bd + i( bc + ad ) -- 4 multiplies = ac - bd + i[ ( a + b )( c + d ) - ac - bd ] -- 3 multiplies diff -ru gcc/libstdc++-v3/include/std/complex gcc.working.copy/libstdc++-v3//include/std/complex --- gcc/libstdc++-v3/include/std/complex 2010-08-13 16:48:07.000000000 +0800 +++ gcc.working.copy/libstdc++-v3//include/std/complex 2010-09-11 13:21:00.000000000 +0800 @@ -291,9 +291,13 @@ complex<_Tp>& complex<_Tp>::operator*=(const complex<_Up>& __z) { - const _Tp __r = _M_real * __z.real() - _M_imag * __z.imag(); - _M_imag = _M_real * __z.imag() + _M_imag * __z.real(); - _M_real = __r; + //(a+ib)(c+id) = ac - bd + i( bc + ad ) -- 4 multiplies + // = ac - bd + i[ ( a + b )( c + d ) - ac - bd ] -- 3 multiplies + const _Tp ac = _M_real * __z.real(); + const _Tp bd = _M_imag * __z.imag(); + const _Tp ab_cd = (_M_real+_M_imag) * (__z.real()+__z.imag()); + _M_real = ac - bd; + _M_imag = ab_cd - ac - bd; return *this; } @@ -304,10 +308,11 @@ complex<_Tp>& complex<_Tp>::operator/=(const complex<_Up>& __z) { - const _Tp __r = _M_real * __z.real() + _M_imag * __z.imag(); - const _Tp __n = std::norm(__z); - _M_imag = (_M_imag * __z.real() - _M_real * __z.imag()) / __n; - _M_real = __r / __n; + // a + ib ( a + ib ) ( c - id ) + //-------- = --------------------- -- 6 multiplies + // c + id c^2 + d^2 + *this *= conj(__z); + *this /= norm(__z); return *this; } --0015175cd11c8795a0049047ddaa Content-Type: application/octet-stream; name="complex.patch" Content-Disposition: attachment; filename="complex.patch" Content-Transfer-Encoding: base64 X-Attachment-Id: f_ge3wp5zb0 ZGlmZiAtcnUgZ2NjL2xpYnN0ZGMrKy12My9pbmNsdWRlL3N0ZC9jb21wbGV4 IGdjYy53b3JraW5nLmNvcHkvbGlic3RkYysrLXYzLy9pbmNsdWRlL3N0ZC9j b21wbGV4Ci0tLSBnY2MvbGlic3RkYysrLXYzL2luY2x1ZGUvc3RkL2NvbXBs ZXgJMjAxMC0wOC0xMyAxNjo0ODowNy4wMDAwMDAwMDAgKzA4MDAKKysrIGdj Yy53b3JraW5nLmNvcHkvbGlic3RkYysrLXYzLy9pbmNsdWRlL3N0ZC9jb21w bGV4CTIwMTAtMDktMTEgMTM6MjE6MDAuMDAwMDAwMDAwICswODAwCkBAIC0y OTEsOSArMjkxLDEzIEBACiAgICAgY29tcGxleDxfVHA+JgogICAgIGNvbXBs ZXg8X1RwPjo6b3BlcmF0b3IqPShjb25zdCBjb21wbGV4PF9VcD4mIF9feikK ICAgICB7Ci0gICAgICBjb25zdCBfVHAgX19yID0gX01fcmVhbCAqIF9fei5y ZWFsKCkgLSBfTV9pbWFnICogX196LmltYWcoKTsKLSAgICAgIF9NX2ltYWcg PSBfTV9yZWFsICogX196LmltYWcoKSArIF9NX2ltYWcgKiBfX3oucmVhbCgp OwotICAgICAgX01fcmVhbCA9IF9fcjsKKyAgICAgIC8vKGEraWIpKGMraWQp ID0gYWMgLSBiZCArIGkoIGJjICsgYWQgKSAtLSA0IG11bHRpcGxpZXMKKyAg ICAgIC8vICAgICAgICAgICAgID0gYWMgLSBiZCArIGlbICggYSArIGIgKSgg YyArIGQgKSAtIGFjIC0gYmQgXSAtLSAzIG11bHRpcGxpZXMKKyAgICAgIGNv bnN0IF9UcCBhYyA9IF9NX3JlYWwgKiBfX3oucmVhbCgpOworICAgICAgY29u c3QgX1RwIGJkID0gX01faW1hZyAqIF9fei5pbWFnKCk7CisgICAgICBjb25z dCBfVHAgYWJfY2QgPSAoX01fcmVhbCtfTV9pbWFnKSAqIChfX3oucmVhbCgp K19fei5pbWFnKCkpOworICAgICAgX01fcmVhbCA9IGFjIC0gYmQ7CisgICAg ICBfTV9pbWFnID0gYWJfY2QgLSBhYyAtIGJkOwogICAgICAgcmV0dXJuICp0 aGlzOwogICAgIH0KIApAQCAtMzA0LDEwICszMDgsMTEgQEAKICAgICBjb21w bGV4PF9UcD4mCiAgICAgY29tcGxleDxfVHA+OjpvcGVyYXRvci89KGNvbnN0 IGNvbXBsZXg8X1VwPiYgX196KQogICAgIHsKLSAgICAgIGNvbnN0IF9UcCBf X3IgPSAgX01fcmVhbCAqIF9fei5yZWFsKCkgKyBfTV9pbWFnICogX196Lmlt YWcoKTsKLSAgICAgIGNvbnN0IF9UcCBfX24gPSBzdGQ6Om5vcm0oX196KTsK LSAgICAgIF9NX2ltYWcgPSAoX01faW1hZyAqIF9fei5yZWFsKCkgLSBfTV9y ZWFsICogX196LmltYWcoKSkgLyBfX247Ci0gICAgICBfTV9yZWFsID0gX19y IC8gX19uOworICAgICAgLy8gYSArIGliICAgICggYSArIGliICkgKCBjIC0g aWQgKQorICAgICAgLy8tLS0tLS0tLSA9IC0tLS0tLS0tLS0tLS0tLS0tLS0t LSAgLS0gNiBtdWx0aXBsaWVzCisgICAgICAvLyBjICsgaWQgICAgICAgICAg Y14yICsgZF4yCisgICAgICAqdGhpcyAqPSBjb25qKF9feik7CisgICAgICAq dGhpcyAvPSBub3JtKF9feik7CiAgICAgICByZXR1cm4gKnRoaXM7CiAgICAg fQogICAgIAo= --0015175cd11c8795a0049047ddaa--