3 * IBM Accurate Mathematical Library
4 * written by International Business Machines Corp.
5 * Copyright (C) 2001-2013 Free Software Foundation, Inc.
7 * This program 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
10 * (at your option) any later version.
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU Lesser General Public License for more details.
17 * You should have received a copy of the GNU Lesser General Public License
18 * along with this program; if not, see <http://www.gnu.org/licenses/>.
20 /************************************************************************/
21 /* MODULE_NAME: mpa.c */
41 /* Arithmetic functions for multiple precision numbers. */
42 /* Relative errors are bounded */
43 /************************************************************************/
49 #include <sys/param.h> /* For MIN() */
50 /* mcr() compares the sizes of the mantissas of two multiple precision */
51 /* numbers. Mantissas are compared regardless of the signs of the */
52 /* numbers, even if x->d[0] or y->d[0] are zero. Exponents are also */
54 static int mcr(const mp_no *x, const mp_no *y, int p) {
57 for (i=1; i<=p2; i++) {
58 if (X[i] == Y[i]) continue;
59 else if (X[i] > Y[i]) return 1;
66 /* acr() compares the absolute values of two multiple precision numbers */
67 int __acr(const mp_no *x, const mp_no *y, int p) {
71 if (Y[0] == ZERO) i= 0;
74 else if (Y[0] == ZERO) i= 1;
77 else if (EX < EY) i=-1;
85 /* cr90 compares the values of two multiple precision numbers */
86 int __cr(const mp_no *x, const mp_no *y, int p) {
89 if (X[0] > Y[0]) i= 1;
90 else if (X[0] < Y[0]) i=-1;
91 else if (X[0] < ZERO ) i= __acr(y,x,p);
98 /* Copy a multiple precision number. Set *y=*x. x=y is permissible. */
99 void __cpy(const mp_no *x, mp_no *y, int p) {
103 for (i=0; i <= p; i++) Y[i] = X[i];
109 /* Copy a multiple precision number x of precision m into a */
110 /* multiple precision number y of precision n. In case n>m, */
111 /* the digits of y beyond the m'th are set to zero. In case */
112 /* n<m, the digits of x beyond the n'th are ignored. */
113 /* x=y is permissible. */
115 void __cpymn(const mp_no *x, int m, mp_no *y, int n) {
121 EY = EX; k=MIN(m2,n2);
122 for (i=0; i <= k; i++) Y[i] = X[i];
123 for ( ; i <= n2; i++) Y[i] = ZERO;
128 /* Convert a multiple precision number *x into a double precision */
129 /* number *y, normalized case (|x| >= 2**(-1022))) */
130 static void norm(const mp_no *x, double *y, int p)
140 else if (p==2) c = X[1] + R* X[2];
141 else if (p==3) c = X[1] + R*(X[2] + R* X[3]);
142 else if (p==4) c =(X[1] + R* X[2]) + R*R*(X[3] + R*X[4]);
145 for (a=ONE, z[1]=X[1]; z[1] < TWO23; )
146 {a *= TWO; z[1] *= TWO; }
148 for (i=2; i<5; i++) {
150 u = (z[i] + CUTTER)-CUTTER;
151 if (u > z[i]) u -= RADIX;
156 u = (z[3] + TWO71) - TWO71;
157 if (u > z[3]) u -= TWO19;
162 for (i=5; i <= p; i++) {
163 if (X[i] == ZERO) continue;
164 else {z[3] += ONE; break; }
170 c = (z[1] + R *(z[2] + R * z[3]))/a;
175 for (i=1; i<EX; i++) c *= RADIX;
176 for (i=1; i>EX; i--) c *= RADIXI;
183 /* Convert a multiple precision number *x into a double precision */
184 /* number *y, denormalized case (|x| < 2**(-1022))) */
185 static void denorm(const mp_no *x, double *y, int p)
195 if (EX<-44 || (EX==-44 && X[1]<TWO5))
199 if (EX==-42) {z[1]=X[1]+TWO10; z[2]=ZERO; z[3]=ZERO; k=3;}
200 else if (EX==-43) {z[1]= TWO10; z[2]=X[1]; z[3]=ZERO; k=2;}
201 else {z[1]= TWO10; z[2]=ZERO; z[3]=X[1]; k=1;}
204 if (EX==-42) {z[1]=X[1]+TWO10; z[2]=X[2]; z[3]=ZERO; k=3;}
205 else if (EX==-43) {z[1]= TWO10; z[2]=X[1]; z[3]=X[2]; k=2;}
206 else {z[1]= TWO10; z[2]=ZERO; z[3]=X[1]; k=1;}
209 if (EX==-42) {z[1]=X[1]+TWO10; z[2]=X[2]; k=3;}
210 else if (EX==-43) {z[1]= TWO10; z[2]=X[1]; k=2;}
211 else {z[1]= TWO10; z[2]=ZERO; k=1;}
215 u = (z[3] + TWO57) - TWO57;
216 if (u > z[3]) u -= TWO5;
219 for (i=k+1; i <= p2; i++) {
220 if (X[i] == ZERO) continue;
221 else {z[3] += ONE; break; }
225 c = X[0]*((z[1] + R*(z[2] + R*z[3])) - TWO10);
233 /* Convert a multiple precision number *x into a double precision number *y. */
234 /* The result is correctly rounded to the nearest/even. *x is left unchanged */
236 void __mp_dbl(const mp_no *x, double *y, int p) {
242 if (X[0] == ZERO) {*y = ZERO; return; }
244 if (EX> -42) norm(x,y,p);
245 else if (EX==-42 && X[1]>=TWO10) norm(x,y,p);
250 /* dbl_mp() converts a double precision number x into a multiple precision */
251 /* number *y. If the precision p is too small the result is truncated. x is */
252 /* left unchanged. */
254 void __dbl_mp(double x, mp_no *y, int p) {
261 if (x == ZERO) {Y[0] = ZERO; return; }
262 else if (x > ZERO) Y[0] = ONE;
263 else {Y[0] = MONE; x=-x; }
266 for (EY=ONE; x >= RADIX; EY += ONE) x *= RADIXI;
267 for ( ; x < ONE; EY -= ONE) x *= RADIX;
271 for (i=1; i<=n; i++) {
272 u = (x + TWO52) - TWO52;
274 Y[i] = u; x -= u; x *= RADIX; }
275 for ( ; i<=p2; i++) Y[i] = ZERO;
280 /* add_magnitudes() adds the magnitudes of *x & *y assuming that */
281 /* abs(*x) >= abs(*y) > 0. */
282 /* The sign of the sum *z is undefined. x&y may overlap but not x&z or y&z. */
283 /* No guard digit is used. The result equals the exact sum, truncated. */
284 /* *x & *y are left unchanged. */
286 static void add_magnitudes(const mp_no *x, const mp_no *y, mp_no *z, int p) {
293 i=p2; j=p2+ EY - EX; k=p2+1;
296 {__cpy(x,z,p); return; }
299 for (; j>0; i--,j--) {
318 for (i=1; i<=p2; i++) Z[i] = Z[i+1]; }
323 /* sub_magnitudes() subtracts the magnitudes of *x & *y assuming that */
324 /* abs(*x) > abs(*y) > 0. */
325 /* The sign of the difference *z is undefined. x&y may overlap but not x&z */
326 /* or y&z. One guard digit is used. The error is less than one ulp. */
327 /* *x & *y are left unchanged. */
329 static void sub_magnitudes(const mp_no *x, const mp_no *y, mp_no *z, int p) {
338 Z[k] = Z[k+1] = ZERO; }
341 if (j > p2) {__cpy(x,z,p); return; }
343 i=p2; j=p2+1-j; k=p2;
345 Z[k+1] = RADIX - Y[j--];
353 for (; j>0; i--,j--) {
354 Z[k] += (X[i] - Y[j]);
371 for (i=1; Z[i] == ZERO; i++) ;
373 for (k=1; i <= p2+1; )
382 /* Add two multiple precision numbers. Set *z = *x + *y. x&y may overlap */
383 /* but not x&z or y&z. One guard digit is used. The error is less than */
384 /* one ulp. *x & *y are left unchanged. */
386 void __add(const mp_no *x, const mp_no *y, mp_no *z, int p) {
390 if (X[0] == ZERO) {__cpy(y,z,p); return; }
391 else if (Y[0] == ZERO) {__cpy(x,z,p); return; }
394 if (__acr(x,y,p) > 0) {add_magnitudes(x,y,z,p); Z[0] = X[0]; }
395 else {add_magnitudes(y,x,z,p); Z[0] = Y[0]; }
398 if ((n=__acr(x,y,p)) == 1) {sub_magnitudes(x,y,z,p); Z[0] = X[0]; }
399 else if (n == -1) {sub_magnitudes(y,x,z,p); Z[0] = Y[0]; }
406 /* Subtract two multiple precision numbers. *z is set to *x - *y. x&y may */
407 /* overlap but not x&z or y&z. One guard digit is used. The error is */
408 /* less than one ulp. *x & *y are left unchanged. */
410 void __sub(const mp_no *x, const mp_no *y, mp_no *z, int p) {
414 if (X[0] == ZERO) {__cpy(y,z,p); Z[0] = -Z[0]; return; }
415 else if (Y[0] == ZERO) {__cpy(x,z,p); return; }
418 if (__acr(x,y,p) > 0) {add_magnitudes(x,y,z,p); Z[0] = X[0]; }
419 else {add_magnitudes(y,x,z,p); Z[0] = -Y[0]; }
422 if ((n=__acr(x,y,p)) == 1) {sub_magnitudes(x,y,z,p); Z[0] = X[0]; }
423 else if (n == -1) {sub_magnitudes(y,x,z,p); Z[0] = -Y[0]; }
430 /* Multiply two multiple precision numbers. *z is set to *x * *y. x&y */
431 /* may overlap but not x&z or y&z. In case p=1,2,3 the exact result is */
432 /* truncated to p digits. In case p>3 the error is bounded by 1.001 ulp. */
433 /* *x & *y are left unchanged. */
435 void __mul(const mp_no *x, const mp_no *y, mp_no *z, int p) {
437 long i, i1, i2, j, k, k2;
443 { Z[0]=ZERO; return; }
445 /* Multiply, add and carry */
446 k2 = (p2<3) ? p2+p2 : p2+3;
449 if (k > p2) {i1=k-p2; i2=p2+1; }
452 /* rearange this inner loop to allow the fmadd instructions to be
453 independent and execute in parallel on processors that have
454 dual symetrical FP pipelines. */
457 /* make sure we have at least 2 iterations */
458 if (((i2 - i1) & 1L) == 1L)
460 /* Handle the odd iterations case. */
461 zk2 = x->d[i2-1]*y->d[i1];
465 /* Do two multiply/adds per loop iteration, using independent
466 accumulators; zk and zk2. */
467 for (i=i1,j=i2-1; i<i2-1; i+=2,j-=2)
469 zk += x->d[i]*y->d[j];
470 zk2 += x->d[i+1]*y->d[j-1];
472 zk += zk2; /* final sum. */
476 /* Special case when iterations is 1. */
477 zk += x->d[i1]*y->d[i1];
480 /* The orginal code. */
481 for (i=i1,j=i2-1; i<i2; i++,j--) zk += X[i]*Y[j];
484 u = (zk + CUTTER)-CUTTER;
485 if (u > zk) u -= RADIX;
492 /* Is there a carry beyond the most significant digit? */
494 for (i=1; i<=p2; i++) Z[i]=Z[i+1];
504 /* Invert a multiple precision number. Set *y = 1 / *x. */
505 /* Relative error bound = 1.001*r**(1-p) for p=2, 1.063*r**(1-p) for p=3, */
506 /* 2.001*r**(1-p) for p>3. */
507 /* *x=0 is not permissible. *x is left unchanged. */
509 void __inv(const mp_no *x, mp_no *y, int p) {
516 static const int np1[] = {0,0,0,0,1,2,2,2,2,3,3,3,3,3,3,3,3,3,
517 4,4,4,4,4,4,4,4,4,4,4,4,4,4,4};
518 const mp_no mptwo = {1,{1.0,2.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,
519 0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,
520 0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,
521 0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0}};
523 __cpy(x,&z,p); z.e=0; __mp_dbl(&z,&t,p);
524 t=ONE/t; __dbl_mp(t,y,p); EY -= EX;
526 for (i=0; i<np1[p]; i++) {
529 __sub(&mptwo,y,&z,p);
536 /* Divide one multiple precision number by another.Set *z = *x / *y. *x & *y */
537 /* are left unchanged. x&y may overlap but not x&z or y&z. */
538 /* Relative error bound = 2.001*r**(1-p) for p=2, 2.063*r**(1-p) for p=3 */
539 /* and 3.001*r**(1-p) for p>3. *y=0 is not permissible. */
541 void __dvd(const mp_no *x, const mp_no *y, mp_no *z, int p) {
545 if (X[0] == ZERO) Z[0] = ZERO;
546 else {__inv(y,&w,p); __mul(x,&w,z,p);}