1 /* mpc_mul -- Multiply two complex numbers
3 Copyright (C) 2002, 2004, 2005, 2008, 2009 Andreas Enge, Paul Zimmermann, Philippe Th\'eveny
5 This file is part of the MPC Library.
7 The MPC Library is free software; you can redistribute it and/or modify
8 it under the terms of the GNU Lesser General Public License as published by
9 the Free Software Foundation; either version 2.1 of the License, or (at your
10 option) any later version.
12 The MPC Library is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
15 License for more details.
17 You should have received a copy of the GNU Lesser General Public License
18 along with the MPC Library; see the file COPYING.LIB. If not, write to
19 the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
20 MA 02111-1307, USA. */
24 static int mul_infinite (mpc_ptr a, mpc_srcptr u, mpc_srcptr v);
25 static int mul_pure_imaginary (mpc_ptr a, mpc_srcptr u, mpfr_srcptr y,
26 mpc_rnd_t rnd, int overlap);
28 /* return inex such that MPC_INEX_RE(inex) = -1, 0, 1
29 MPC_INEX_IM(inex) = -1, 0, 1
30 depending on the signs of the real/imaginary parts of the result
33 mpc_mul (mpc_ptr a, mpc_srcptr b, mpc_srcptr c, mpc_rnd_t rnd)
35 int brs, bis, crs, cis;
37 /* Conforming to ISO C99 standard (G.5.1 multiplicative operators),
38 infinities have special treatment if both parts are NaN when computed
41 return mul_infinite (a, b, c);
43 return mul_infinite (a, c, b);
45 /* NaN contamination of both part in result */
46 if (mpfr_nan_p (MPC_RE (b)) || mpfr_nan_p (MPC_IM (b))
47 || mpfr_nan_p (MPC_RE (c)) || mpfr_nan_p (MPC_IM (c)))
49 mpfr_set_nan (MPC_RE (a));
50 mpfr_set_nan (MPC_IM (a));
51 return MPC_INEX (0, 0);
54 /* save operands' sign */
55 brs = MPFR_SIGNBIT (MPC_RE (b));
56 bis = MPFR_SIGNBIT (MPC_IM (b));
57 crs = MPFR_SIGNBIT (MPC_RE (c));
58 cis = MPFR_SIGNBIT (MPC_IM (c));
60 /* first check for real multiplication */
61 if (mpfr_zero_p (MPC_IM (b))) /* b * (x+i*y) = b*x + i *(b*y) */
64 inex = mpc_mul_fr (a, c, MPC_RE (b), rnd);
66 /* Sign of zeros is wrong in some cases. This correction doesn't change
68 if (mpfr_zero_p (MPC_RE (a)))
69 mpfr_setsign (MPC_RE (a), MPC_RE (a), MPC_RND_RE(rnd) == GMP_RNDD
70 || (brs != crs && bis == cis), GMP_RNDN); /* exact */
71 if (mpfr_zero_p (MPC_IM (a)))
72 mpfr_setsign (MPC_IM (a), MPC_IM (a), MPC_RND_IM (rnd) == GMP_RNDD
73 || (brs != cis && bis != crs), GMP_RNDN); /* exact */
77 if (mpfr_zero_p (MPC_IM (c)))
80 inex = mpc_mul_fr (a, b, MPC_RE (c), rnd);
82 /* Sign of zeros is wrong in some cases. This correction doesn't change
84 if (mpfr_zero_p (MPC_RE (a)))
85 mpfr_setsign (MPC_RE (a), MPC_RE (a), MPC_RND_RE(rnd) == GMP_RNDD
86 || (brs != crs && bis == cis), GMP_RNDN);
87 if (mpfr_zero_p (MPC_IM (a)))
88 mpfr_setsign (MPC_IM (a), MPC_IM (a), MPC_RND_IM (rnd) == GMP_RNDD
89 || (brs != cis && bis != crs), GMP_RNDN);
94 /* check for purely complex multiplication */
95 if (mpfr_zero_p (MPC_RE (b))) /* i*b * (x+i*y) = -b*y + i*(b*x) */
98 inex = mul_pure_imaginary (a, c, MPC_IM (b), rnd, (a == b || a == c));
100 /* Sign of zeros is wrong in some cases (note that Re(a) cannot be a
102 if (mpfr_zero_p (MPC_IM (a)))
103 mpfr_setsign (MPC_IM (a), MPC_IM (a), MPC_RND_IM (rnd) == GMP_RNDD
104 || (brs != cis && bis != crs), GMP_RNDN);
108 if (mpfr_zero_p (MPC_RE (c)))
109 /* note that a cannot be a zero */
110 return mul_pure_imaginary (a, b, MPC_IM (c), rnd, (a == b || a == c));
112 /* If the real and imaginary part of one argument have a very different */
113 /* exponent, it is not reasonable to use Karatsuba multiplication. */
114 if ( SAFE_ABS (mp_exp_t, MPFR_EXP (MPC_RE (b)) - MPFR_EXP (MPC_IM (b)))
115 > (mp_exp_t) MPC_MAX_PREC (b) / 2
116 || SAFE_ABS (mp_exp_t, MPFR_EXP (MPC_RE (c)) - MPFR_EXP (MPC_IM (c)))
117 > (mp_exp_t) MPC_MAX_PREC (c) / 2)
118 return mpc_mul_naive (a, b, c, rnd);
120 return ((MPC_MAX_PREC(a)
121 <= (mp_prec_t) MUL_KARATSUBA_THRESHOLD * BITS_PER_MP_LIMB)
122 ? mpc_mul_naive : mpc_mul_karatsuba) (a, b, c, rnd);
125 /* compute a=u*v when u has an infinite part */
127 mul_infinite (mpc_ptr a, mpc_srcptr u, mpc_srcptr v)
129 /* let u = ur+i*ui and v =vr+i*vi */
132 /* save operands' sign */
133 int urs = mpfr_signbit (MPC_RE (u)) ? -1 : 1;
134 int uis = mpfr_signbit (MPC_IM (u)) ? -1 : 1;
135 int vrs = mpfr_signbit (MPC_RE (v)) ? -1 : 1;
136 int vis = mpfr_signbit (MPC_IM (v)) ? -1 : 1;
138 /* compute the sign of
139 x = urs * ur * vrs * vr - uis * ui * vis * vi
140 y = urs * ur * vis * vi + uis * ui * vrs * vr
141 +1 if positive, -1 if negative, 0 if zero or NaN */
142 if (mpfr_nan_p (MPC_RE (u)) || mpfr_nan_p (MPC_IM (u))
143 || mpfr_nan_p (MPC_RE (v)) || mpfr_nan_p (MPC_IM (v)))
148 else if (mpfr_inf_p (MPC_RE (u)))
150 /* u = (+/-inf) +i*v */
151 x = mpfr_zero_p (MPC_RE (v))
152 || (mpfr_inf_p (MPC_IM (u)) && mpfr_zero_p (MPC_IM (v)))
153 || (mpfr_zero_p (MPC_IM (u)) && mpfr_inf_p (MPC_IM (v)))
154 || ((mpfr_inf_p (MPC_IM (u)) || mpfr_inf_p (MPC_IM (v)))
155 && urs*vrs == uis*vis) ?
157 y = mpfr_zero_p (MPC_IM (v))
158 || (mpfr_inf_p (MPC_IM (u)) && mpfr_zero_p (MPC_RE (v)))
159 || (mpfr_zero_p (MPC_IM (u)) && mpfr_inf_p (MPC_RE (v)))
160 || ((mpfr_inf_p (MPC_IM (u)) || mpfr_inf_p (MPC_IM (u)))
161 && urs*vis == -uis*vrs) ?
166 /* u = u +i*(+/-inf) where |u| < inf */
167 x = mpfr_zero_p (MPC_IM (v))
168 || (mpfr_zero_p (MPC_RE (u)) && mpfr_inf_p (MPC_RE (v)))
169 || (mpfr_inf_p (MPC_RE (v)) && urs*vrs == uis*vis) ?
171 y = mpfr_zero_p (MPC_RE (v))
172 || (mpfr_zero_p (MPC_RE (u)) && mpfr_inf_p (MPC_IM (v)))
173 || (mpfr_inf_p (MPC_IM (v)) && urs*vis == -uis*vrs) ?
177 /* Naive result is NaN+i*NaN. We will try to obtain an infinite using
178 algorithm given in Annex G of ISO C99 standard */
181 int ur = mpfr_zero_p (MPC_RE (u)) || mpfr_nan_p (MPC_RE (u)) ?
183 int ui = mpfr_zero_p (MPC_IM (u)) || mpfr_nan_p (MPC_IM (u)) ?
185 int vr = mpfr_zero_p (MPC_RE (v)) || mpfr_nan_p (MPC_RE (v)) ?
187 int vi = mpfr_zero_p (MPC_IM (v)) || mpfr_nan_p (MPC_IM (v)) ?
191 ur = mpfr_inf_p (MPC_RE (u)) ? 1 : 0;
192 ui = mpfr_inf_p (MPC_IM (u)) ? 1 : 0;
196 vr = mpfr_inf_p (MPC_RE (v)) ? 1 : 0;
197 vi = mpfr_inf_p (MPC_IM (v)) ? 1 : 0;
200 x = urs * ur * vrs * vr - uis * ui * vis * vi;
201 y = urs * ur * vis * vi + uis * ui * vrs * vr;
205 mpfr_set_nan (MPC_RE (a));
207 mpfr_set_inf (MPC_RE (a), x);
210 mpfr_set_nan (MPC_IM (a));
212 mpfr_set_inf (MPC_IM (a), y);
214 return MPC_INEX (0, 0); /* exact */
218 mul_pure_imaginary (mpc_ptr a, mpc_srcptr u, mpfr_srcptr y, mpc_rnd_t rnd,
221 int inex_re, inex_im;
225 mpc_init3 (result, MPFR_PREC (MPC_RE (a)), MPFR_PREC (MPC_IM (a)));
229 inex_re = -mpfr_mul (MPC_RE(result), MPC_IM(u), y, INV_RND(MPC_RND_RE(rnd)));
230 mpfr_neg (MPC_RE (result), MPC_RE (result), GMP_RNDN);
231 inex_im = mpfr_mul (MPC_IM(result), MPC_RE(u), y, MPC_RND_IM(rnd));
232 mpc_set (a, result, MPC_RNDNN);
237 return MPC_INEX(inex_re, inex_im);
241 mpc_mul_naive (mpc_ptr a, mpc_srcptr b, mpc_srcptr c, mpc_rnd_t rnd)
243 int overlap, inex_re, inex_im;
247 overlap = (a == b) || (a == c);
249 prec = MPC_MAX_PREC(b) + MPC_MAX_PREC(c);
251 mpfr_init2 (u, prec);
252 mpfr_init2 (v, prec);
254 /* Re(a) = Re(b)*Re(c) - Im(b)*Im(c) */
255 /* FIXME: this code suffers undue overflows: u or v can overflow while u-v
256 or u+v is representable */
257 mpfr_mul (u, MPC_RE(b), MPC_RE(c), GMP_RNDN); /* exact */
258 mpfr_mul (v, MPC_IM(b), MPC_IM(c), GMP_RNDN); /* exact */
262 mpfr_init2 (t, MPFR_PREC(MPC_RE(a)));
263 inex_re = mpfr_sub (t, u, v, MPC_RND_RE(rnd));
266 inex_re = mpfr_sub (MPC_RE(a), u, v, MPC_RND_RE(rnd));
268 /* Im(a) = Re(b)*Im(c) + Im(b)*Re(c) */
269 mpfr_mul (u, MPC_RE(b), MPC_IM(c), GMP_RNDN); /* exact */
270 if (b == c) /* square case */
271 inex_im = mpfr_mul_2exp (MPC_IM(a), u, 1, MPC_RND_IM(rnd));
274 mpfr_mul (v, MPC_IM(b), MPC_RE(c), GMP_RNDN); /* exact */
275 inex_im = mpfr_add (MPC_IM(a), u, v, MPC_RND_IM(rnd));
283 mpfr_set (MPC_RE(a), t, GMP_RNDN); /* exact */
287 return MPC_INEX(inex_re, inex_im);
291 /* Karatsuba multiplication, with 3 real multiplies */
293 mpc_mul_karatsuba (mpc_ptr rop, mpc_srcptr op1, mpc_srcptr op2, mpc_rnd_t rnd)
295 mpfr_srcptr a, b, c, d;
296 int mul_i, ok, inexact, mul_a, mul_c, inex_re, inex_im, sign_x, sign_u;
298 mp_prec_t prec, prec_re, prec_u, prec_v, prec_w;
299 mp_rnd_t rnd_re, rnd_u, rnd_x;
301 /* true if rop == op1 or rop == op2 */
303 /* overlap is quite difficult to handle, because we have to tentatively
304 round the variable u in the end to either the real or the imaginary
305 part of rop (it is not possible to tell now whether the real or
306 imaginary part is used). If this fails, we have to start again and
307 need the correct values of op1 and op2.
308 So we just create a new variable for the result in this case. */
310 overlap = (rop == op1) || (rop == op2);
312 mpc_init3 (result, MPFR_PREC (MPC_RE (rop)),
313 MPFR_PREC (MPC_IM (rop)));
315 result [0] = rop [0];
322 /* (a + i*b) * (c + i*d) = [ac - bd] + i*[ad + bc] */
324 mul_i = 0; /* number of multiplications by i */
325 mul_a = 1; /* implicit factor for a */
326 mul_c = 1; /* implicit factor for c */
328 if (mpfr_cmp_abs (a, b) < 0)
332 mul_a = -1; /* consider i * (a+i*b) = -b + i*a */
335 if (mpfr_cmp_abs (c, d) < 0)
339 mul_c = -1; /* consider -d + i*c instead of c + i*d */
342 /* find the precision and rounding mode for the new real part */
345 prec_re = MPFR_PREC(MPC_IM(rop));
346 rnd_re = MPC_RND_IM(rnd);
348 else /* mul_i = 0 or 2 */
350 prec_re = MPFR_PREC(MPC_RE(rop));
351 rnd_re = MPC_RND_RE(rnd);
355 rnd_re = INV_RND(rnd_re);
357 /* now |a| >= |b| and |c| >= |d| */
358 prec = MPC_MAX_PREC(rop);
361 mpfr_init2 (v, prec_v = MPFR_PREC(a) + MPFR_PREC(d));
362 mpfr_init2 (w, prec_w = MPFR_PREC(b) + MPFR_PREC(c));
365 mpfr_mul (v, a, d, GMP_RNDN); /* exact */
367 mpfr_neg (v, v, GMP_RNDN);
369 mpfr_mul (w, b, c, GMP_RNDN); /* exact */
371 mpfr_neg (w, w, GMP_RNDN);
373 /* compute sign(v-w) */
374 sign_x = mpfr_cmp_abs (v, w);
376 sign_x = 2 * mpfr_sgn (v) - mpfr_sgn (w);
377 else if (sign_x == 0)
378 sign_x = mpfr_sgn (v) - mpfr_sgn (w);
380 sign_x = mpfr_sgn (v) - 2 * mpfr_sgn (w);
382 sign_u = mul_a * mpfr_sgn (a) * mul_c * mpfr_sgn (c);
384 if (sign_x * sign_u < 0)
389 { int tmp; tmp = mul_a; mul_a = mul_c; mul_c = tmp; }
393 /* now sign_x * sign_u >= 0 */
396 /* the following should give failures with prob. <= 1/prec */
397 prec += mpc_ceil_log2 (prec) + 3;
399 mpfr_set_prec (u, prec_u = prec);
400 mpfr_set_prec (x, prec);
402 /* first compute away(b +/- a) and store it in u */
403 rnd_u = (mpfr_sgn (a) > 0) ? GMP_RNDU : GMP_RNDD;
405 rnd_u = INV_RND(rnd_u);
406 inexact = ((mul_a == -1) ? mpfr_sub : mpfr_add) (u, b, a, rnd_u);
408 /* then compute away(+/-c - d) and store it in x */
409 rnd_x = (mpfr_sgn (c) > 0) ? GMP_RNDU : GMP_RNDD;
410 inexact |= ((mul_c == -1) ? mpfr_add : mpfr_sub) (x, c, d, rnd_x);
412 mpfr_neg (x, x, GMP_RNDN);
415 mpfr_prec_round (u, prec_u = 2 * prec, GMP_RNDN);
417 /* compute away(u*x) and store it in u */
418 rnd_u = (sign_u > 0) ? GMP_RNDU : GMP_RNDD;
419 inexact |= mpfr_mul (u, u, x, rnd_u); /* (a+b)*(c-d) */
421 /* if all computations are exact up to here, it may be that
422 the real part is exact, thus we need if possible to
423 compute v - w exactly */
429 else if (mpfr_zero_p(w))
433 prec_x = (MPFR_EXP(v) > MPFR_EXP(w)) ? MPFR_EXP(v) - MPFR_EXP(w)
434 : MPFR_EXP(w) - MPFR_EXP(v);
435 prec_x += MPC_MAX (prec_v, prec_w) + 1;
437 /* +1 is necessary for a potential carry */
438 /* ensure we do not use a too large precision */
442 mpfr_prec_round (x, prec_x, GMP_RNDN);
445 inexact |= mpfr_sub (x, v, w, rnd_u); /* ad - bc */
447 /* in case u=0, ensure that rnd_u rounds x away from zero */
448 if (mpfr_sgn (u) == 0)
449 rnd_u = (mpfr_sgn (x) > 0) ? GMP_RNDU : GMP_RNDD;
450 inexact |= mpfr_add (u, u, x, rnd_u); /* ac - bd */
453 mpfr_can_round (u, prec_u - 3, rnd_u, GMP_RNDZ,
454 prec_re + (rnd_re == GMP_RNDN));
455 /* this ensures both we can round correctly and determine the correct
456 inexact flag (for rounding to nearest) */
460 /* if inexact is zero, then u is exactly ac-bd, otherwise fix the sign
461 of the inexact flag for u, which was rounded away from ac-bd */
463 inexact = mpfr_sgn (u);
467 inex_re = mpfr_set (MPC_RE(result), u, MPC_RND_RE(rnd));
470 inex_re = inexact; /* u is rounded away from 0 */
471 inex_im = mpfr_add (MPC_IM(result), v, w, MPC_RND_IM(rnd));
474 inex_im = mpfr_add (MPC_IM(result), v, w, MPC_RND_IM(rnd));
476 else if (mul_i == 1) /* (x+i*y)/i = y - i*x */
478 inex_im = mpfr_neg (MPC_IM(result), u, MPC_RND_IM(rnd));
481 inex_im = -inexact; /* u is rounded away from 0 */
482 inex_re = mpfr_add (MPC_RE(result), v, w, MPC_RND_RE(rnd));
485 inex_re = mpfr_add (MPC_RE(result), v, w, MPC_RND_RE(rnd));
487 else /* mul_i = 2, z/i^2 = -z */
489 inex_re = mpfr_neg (MPC_RE(result), u, MPC_RND_RE(rnd));
492 inex_re = -inexact; /* u is rounded away from 0 */
493 inex_im = -mpfr_add (MPC_IM(result), v, w,
494 INV_RND(MPC_RND_IM(rnd)));
495 mpfr_neg (MPC_IM(result), MPC_IM(result), MPC_RND_IM(rnd));
499 inex_im = -mpfr_add (MPC_IM(result), v, w,
500 INV_RND(MPC_RND_IM(rnd)));
501 mpfr_neg (MPC_IM(result), MPC_IM(result), MPC_RND_IM(rnd));
505 mpc_set (rop, result, MPC_RNDNN);
514 return MPC_INEX(inex_re, inex_im);