Debian Codegraph @

3rdparty/dissection/src/qd/dd_real.cpp

raw
1 /*
2 * src/dd_real.cc
3 *
4 * This work was supported by the Director, Office of Science, Division
5 * of Mathematical, Information, and Computational Sciences of the
6 * U.S. Department of Energy under contract number DE-AC03-76SF00098.
7 *
8 * Copyright (c) 2000-2007
9 *
10 * Contains implementation of non-inlined functions of double-double
11 * package. Inlined functions are found in dd_inline.h (in include directory).
12 */
13 #include <cstdlib>
14 #include <cstdio>
15 #include <cmath>
16 #include <cstring>
17 #include <iostream>
18 #include <iomanip>
19 #include <string>
20
21 #include "config.h"
22 #include <qd/dd_real.h>
23 #include "util.h"
24
25 #include <qd/bits.h>
26
27 #ifndef QD_INLINE
28 #include <qd/dd_inline.h>
29 #endif
30 #include <algorithm> // 05 Apr.2018
31 using std::cout;
32 using std::cerr;
33 using std::endl;
34 using std::ostream;
35 using std::istream;
36 using std::ios_base;
37 using std::string;
38 using std::setw;
39 /* This routine is called whenever a fatal error occurs. */
40 void dd_real::error(const char *msg) {
41 // if (msg) { cerr << "ERROR " << msg << endl; }
42 }
43 /* Computes the square root of the double-double number dd.
44 NOTE: dd must be a non-negative number. */
45 QD_API dd_real sqrt(const dd_real &a) {
46 /* Strategy: Use Karp's trick: if x is an approximation
47 to sqrt(a), then
48
49 sqrt(a) = a*x + [a - (a*x)^2] * x / 2 (approx)
50
51 The approximation is accurate to twice the accuracy of x.
52 Also, the multiplication (a*x) and [-]*x can be done with
53 only half the precision.
54 */
55
56 if (a.is_zero())
57 return 0.0;
58
59 if (a.is_negative()) {
60 dd_real::error("(dd_real::sqrt): Negative argument.");
61 return dd_real::_nan;
62 }
63
64 double x = 1.0 / std::sqrt(a.x[0]);
65 double ax = a.x[0] * x;
66 return dd_real::add(ax, (a - dd_real::sqr(ax)).x[0] * (x * 0.5));
67 }
68
69 /* Computes the square root of a double in double-double precision.
70 NOTE: d must not be negative. */
71 dd_real dd_real::sqrt(double d) {
72 return ::sqrt(dd_real(d));
73 }
74
75 /* Computes the n-th root of the double-double number a.
76 NOTE: n must be a positive integer.
77 NOTE: If n is even, then a must not be negative. */
78 dd_real nroot(const dd_real &a, int n) {
79 /* Strategy: Use Newton iteration for the function
80
81 f(x) = x^(-n) - a
82
83 to find its root a^{-1/n}. The iteration is thus
84
85 x' = x + x * (1 - a * x^n) / n
86
87 which converges quadratically. We can then find
88 a^{1/n} by taking the reciprocal.
89 */
90
91 if (n <= 0) {
92 dd_real::error("(dd_real::nroot): N must be positive.");
93 return dd_real::_nan;
94 }
95
96 if (n%2 == 0 && a.is_negative()) {
97 dd_real::error("(dd_real::nroot): Negative argument.");
98 return dd_real::_nan;
99 }
100
101 if (n == 1) {
102 return a;
103 }
104 if (n == 2) {
105 return sqrt(a);
106 }
107
108 if (a.is_zero())
109 return 0.0;
110
111 /* Note a^{-1/n} = exp(-log(a)/n) */
112 dd_real r = abs(a);
113 dd_real x = std::exp(-std::log(r.x[0]) / n);
114
115 /* Perform Newton's iteration. */
116 x += x * (1.0 - r * npwr(x, n)) / static_cast<double>(n);
117 if (a.x[0] < 0.0)
118 x = -x;
119 return 1.0/x;
120 }
121
122 /* Computes the n-th power of a double-double number.
123 NOTE: 0^0 causes an error. */
124 dd_real npwr(const dd_real &a, int n) {
125
126 if (n == 0) {
127 if (a.is_zero()) {
128 dd_real::error("(dd_real::npwr): Invalid argument.");
129 return dd_real::_nan;
130 }
131 return 1.0;
132 }
133
134 dd_real r = a;
135 dd_real s = 1.0;
136 int N = std::abs(n);
137
138 if (N > 1) {
139 /* Use binary exponentiation */
140 while (N > 0) {
141 if (N % 2 == 1) {
142 s *= r;
143 }
144 N /= 2;
145 if (N > 0)
146 r = sqr(r);
147 }
148 } else {
149 s = r;
150 }
151
152 /* Compute the reciprocal if n is negative. */
153 if (n < 0)
154 return (1.0 / s);
155
156 return s;
157 }
158
159 dd_real pow(const dd_real &a, int n) {
160 return npwr(a, n);
161 }
162
163 dd_real pow(const dd_real &a, const dd_real &b) {
164 return dd_real(1.0); // 5 Apr.2018
165 // return exp(b * log(a));
166 }
167
168 static const int n_inv_fact = 15;
169 static const double inv_fact[n_inv_fact][2] = {
170 { 1.66666666666666657e-01, 9.25185853854297066e-18},
171 { 4.16666666666666644e-02, 2.31296463463574266e-18},
172 { 8.33333333333333322e-03, 1.15648231731787138e-19},
173 { 1.38888888888888894e-03, -5.30054395437357706e-20},
174 { 1.98412698412698413e-04, 1.72095582934207053e-22},
175 { 2.48015873015873016e-05, 2.15119478667758816e-23},
176 { 2.75573192239858925e-06, -1.85839327404647208e-22},
177 { 2.75573192239858883e-07, 2.37677146222502973e-23},
178 { 2.50521083854417202e-08, -1.44881407093591197e-24},
179 { 2.08767569878681002e-09, -1.20734505911325997e-25},
180 { 1.60590438368216133e-10, 1.25852945887520981e-26},
181 { 1.14707455977297245e-11, 2.06555127528307454e-28},
182 { 7.64716373181981641e-13, 7.03872877733453001e-30},
183 { 4.77947733238738525e-14, 4.39920548583408126e-31},
184 { 2.81145725434552060e-15, 1.65088427308614326e-31}
185 };
186
187 /* Exponential. Computes exp(x) in double-double precision. */
188 dd_real exp(const dd_real &a) {
189 /* Strategy: We first reduce the size of x by noting that
190
191 exp(kr + m * log(2)) = 2^m * exp(r)^k
192
193 where m and k are integers. By choosing m appropriately
194 we can make |kr| <= log(2) / 2 = 0.347. Then exp(r) is
195 evaluated using the familiar Taylor series. Reducing the
196 argument substantially speeds up the convergence. */
197
198 const double k = 512.0;
199 const double inv_k = 1.0 / k;
200
201 if (a.x[0] <= -709.0)
202 return 0.0;
203
204 if (a.x[0] >= 709.0)
205 return dd_real::_inf;
206
207 if (a.is_zero())
208 return 1.0;
209
210 if (a.is_one())
211 return dd_real::_e;
212
213 double m = std::floor(a.x[0] / dd_real::_log2.x[0] + 0.5);
214 dd_real r = mul_pwr2(a - dd_real::_log2 * m, inv_k);
215 dd_real s, t, p;
216
217 p = sqr(r);
218 s = r + mul_pwr2(p, 0.5);
219 p *= r;
220 t = p * dd_real(inv_fact[0][0], inv_fact[0][1]);
221 int i = 0;
222 do {
223 s += t;
224 p *= r;
225 ++i;
226 t = p * dd_real(inv_fact[i][0], inv_fact[i][1]);
227 } while (std::abs(to_double(t)) > inv_k * dd_real::_eps && i < 5);
228
229 s += t;
230
231 s = mul_pwr2(s, 2.0) + sqr(s);
232 s = mul_pwr2(s, 2.0) + sqr(s);
233 s = mul_pwr2(s, 2.0) + sqr(s);
234 s = mul_pwr2(s, 2.0) + sqr(s);
235 s = mul_pwr2(s, 2.0) + sqr(s);
236 s = mul_pwr2(s, 2.0) + sqr(s);
237 s = mul_pwr2(s, 2.0) + sqr(s);
238 s = mul_pwr2(s, 2.0) + sqr(s);
239 s = mul_pwr2(s, 2.0) + sqr(s);
240 s += 1.0;
241
242 return ldexp(s, static_cast<int>(m));
243 }
244 /* Logarithm. Computes log(x) in double-double precision.
245 This is a natural logarithm (i.e., base e). */
246 dd_real log(const dd_real &a) {
247 /* Strategy. The Taylor series for log converges much more
248 slowly than that of exp, due to the lack of the factorial
249 term in the denominator. Hence this routine instead tries
250 to determine the root of the function
251
252 f(x) = exp(x) - a
253
254 using Newton iteration. The iteration is given by
255
256 x' = x - f(x)/f'(x)
257 = x - (1 - a * exp(-x))
258 = x + a * exp(-x) - 1.
259
260 Only one iteration is needed, since Newton's iteration
261 approximately doubles the number of digits per iteration. */
262
263 if (a.is_one()) {
264 return 0.0;
265 }
266
267 if (a.x[0] <= 0.0) {
268 dd_real::error("(dd_real::log): Non-positive argument.");
269 return dd_real::_nan;
270 }
271
272 dd_real x = std::log(a.x[0]); /* Initial approximation */
273
274 x = x + a * exp(-x) - 1.0;
275 return x;
276 }
277
278 dd_real log10(const dd_real &a) {
279 return log(a) / dd_real::_log10;
280 }
281 static const dd_real _pi16 = dd_real(1.963495408493620697e-01,
282 7.654042494670957545e-18);
283
284 /* Table of sin(k * pi/16) and cos(k * pi/16). */
285 static const double sin_table [4][2] = {
286 {1.950903220161282758e-01, -7.991079068461731263e-18},
287 {3.826834323650897818e-01, -1.005077269646158761e-17},
288 {5.555702330196021776e-01, 4.709410940561676821e-17},
289 {7.071067811865475727e-01, -4.833646656726456726e-17}
290 };
291
292 static const double cos_table [4][2] = {
293 {9.807852804032304306e-01, 1.854693999782500573e-17},
294 {9.238795325112867385e-01, 1.764504708433667706e-17},
295 {8.314696123025452357e-01, 1.407385698472802389e-18},
296 {7.071067811865475727e-01, -4.833646656726456726e-17}
297 };
298
299 /* Computes sin(a) using Taylor series.
300 Assumes |a| <= pi/32. */
301 static dd_real sin_taylor(const dd_real &a) {
302 const double thresh = 0.5 * std::abs(to_double(a)) * dd_real::_eps;
303 dd_real r, s, t, x;
304
305 if (a.is_zero()) {
306 return 0.0;
307 }
308
309 int i = 0;
310 x = -sqr(a);
311 s = a;
312 r = a;
313 do {
314 r *= x;
315 t = r * dd_real(inv_fact[i][0], inv_fact[i][1]);
316 s += t;
317 i += 2;
318 } while (i < n_inv_fact && std::abs(to_double(t)) > thresh);
319
320 return s;
321 }
322
323 static dd_real cos_taylor(const dd_real &a) {
324 const double thresh = 0.5 * dd_real::_eps;
325 dd_real r, s, t, x;
326
327 if (a.is_zero()) {
328 return 1.0;
329 }
330
331 x = -sqr(a);
332 r = x;
333 s = 1.0 + mul_pwr2(r, 0.5);
334 int i = 1;
335 do {
336 r *= x;
337 t = r * dd_real(inv_fact[i][0], inv_fact[i][1]);
338 s += t;
339 i += 2;
340 } while (i < n_inv_fact && std::abs(to_double(t)) > thresh);
341
342 return s;
343 }
344
345 static void sincos_taylor(const dd_real &a,
346 dd_real &sin_a, dd_real &cos_a) {
347 if (a.is_zero()) {
348 sin_a = 0.0;
349 cos_a = 1.0;
350 return;
351 }
352
353 sin_a = sin_taylor(a);
354 cos_a = sqrt(1.0 - sqr(sin_a));
355 }
356
357
358 dd_real sin(const dd_real &a) {
359
360 /* Strategy. To compute sin(x), we choose integers a, b so that
361
362 x = s + a * (pi/2) + b * (pi/16)
363
364 and |s| <= pi/32. Using the fact that
365
366 sin(pi/16) = 0.5 * sqrt(2 - sqrt(2 + sqrt(2)))
367
368 we can compute sin(x) from sin(s), cos(s). This greatly
369 increases the convergence of the sine Taylor series. */
370
371 if (a.is_zero()) {
372 return 0.0;
373 }
374
375 // approximately reduce modulo 2*pi
376 dd_real z = nint(a / dd_real::_2pi);
377 dd_real r = a - dd_real::_2pi * z;
378
379 // approximately reduce modulo pi/2 and then modulo pi/16.
380 dd_real t;
381 double q = std::floor(r.x[0] / dd_real::_pi2.x[0] + 0.5);
382 t = r - dd_real::_pi2 * q;
383 int j = static_cast<int>(q);
384 q = std::floor(t.x[0] / _pi16.x[0] + 0.5);
385 t -= _pi16 * q;
386 int k = static_cast<int>(q);
387 int abs_k = std::abs(k);
388
389 if (j < -2 || j > 2) {
390 dd_real::error("(dd_real::sin): Cannot reduce modulo pi/2.");
391 return dd_real::_nan;
392 }
393
394 if (abs_k > 4) {
395 dd_real::error("(dd_real::sin): Cannot reduce modulo pi/16.");
396 return dd_real::_nan;
397 }
398
399 if (k == 0) {
400 switch (j) {
401 case 0:
402 return sin_taylor(t);
403 case 1:
404 return cos_taylor(t);
405 case -1:
406 return -cos_taylor(t);
407 default:
408 return -sin_taylor(t);
409 }
410 }
411
412 dd_real u(cos_table[abs_k-1][0], cos_table[abs_k-1][1]);
413 dd_real v(sin_table[abs_k-1][0], sin_table[abs_k-1][1]);
414 dd_real sin_t, cos_t;
415 sincos_taylor(t, sin_t, cos_t);
416 if (j == 0) {
417 if (k > 0) {
418 r = u * sin_t + v * cos_t;
419 } else {
420 r = u * sin_t - v * cos_t;
421 }
422 } else if (j == 1) {
423 if (k > 0) {
424 r = u * cos_t - v * sin_t;
425 } else {
426 r = u * cos_t + v * sin_t;
427 }
428 } else if (j == -1) {
429 if (k > 0) {
430 r = v * sin_t - u * cos_t;
431 } else if (k < 0) {
432 r = -u * cos_t - v * sin_t;
433 }
434 } else {
435 if (k > 0) {
436 r = -u * sin_t - v * cos_t;
437 } else {
438 r = v * cos_t - u * sin_t;
439 }
440 }
441
442 return r;
443 }
444
445 dd_real cos(const dd_real &a) {
446
447 if (a.is_zero()) {
448 return 1.0;
449 }
450
451 // approximately reduce modulo 2*pi
452 dd_real z = nint(a / dd_real::_2pi);
453 dd_real r = a - z * dd_real::_2pi;
454
455 // approximately reduce modulo pi/2 and then modulo pi/16
456 dd_real t;
457 double q = std::floor(r.x[0] / dd_real::_pi2.x[0] + 0.5);
458 t = r - dd_real::_pi2 * q;
459 int j = static_cast<int>(q);
460 q = std::floor(t.x[0] / _pi16.x[0] + 0.5);
461 t -= _pi16 * q;
462 int k = static_cast<int>(q);
463 int abs_k = std::abs(k);
464
465 if (j < -2 || j > 2) {
466 dd_real::error("(dd_real::cos): Cannot reduce modulo pi/2.");
467 return dd_real::_nan;
468 }
469
470 if (abs_k > 4) {
471 dd_real::error("(dd_real::cos): Cannot reduce modulo pi/16.");
472 return dd_real::_nan;
473 }
474
475 if (k == 0) {
476 switch (j) {
477 case 0:
478 return cos_taylor(t);
479 case 1:
480 return -sin_taylor(t);
481 case -1:
482 return sin_taylor(t);
483 default:
484 return -cos_taylor(t);
485 }
486 }
487
488 dd_real sin_t, cos_t;
489 sincos_taylor(t, sin_t, cos_t);
490 dd_real u(cos_table[abs_k-1][0], cos_table[abs_k-1][1]);
491 dd_real v(sin_table[abs_k-1][0], sin_table[abs_k-1][1]);
492
493 if (j == 0) {
494 if (k > 0) {
495 r = u * cos_t - v * sin_t;
496 } else {
497 r = u * cos_t + v * sin_t;
498 }
499 } else if (j == 1) {
500 if (k > 0) {
501 r = - u * sin_t - v * cos_t;
502 } else {
503 r = v * cos_t - u * sin_t;
504 }
505 } else if (j == -1) {
506 if (k > 0) {
507 r = u * sin_t + v * cos_t;
508 } else {
509 r = u * sin_t - v * cos_t;
510 }
511 } else {
512 if (k > 0) {
513 r = v * sin_t - u * cos_t;
514 } else {
515 r = - u * cos_t - v * sin_t;
516 }
517 }
518
519 return r;
520 }
521
522 void sincos(const dd_real &a, dd_real &sin_a, dd_real &cos_a) {
523
524 if (a.is_zero()) {
525 sin_a = 0.0;
526 cos_a = 1.0;
527 return;
528 }
529
530 // approximately reduce modulo 2*pi
531 dd_real z = nint(a / dd_real::_2pi);
532 dd_real r = a - dd_real::_2pi * z;
533
534 // approximately reduce module pi/2 and pi/16
535 dd_real t;
536 double q = std::floor(r.x[0] / dd_real::_pi2.x[0] + 0.5);
537 t = r - dd_real::_pi2 * q;
538 int j = static_cast<int>(q);
539 int abs_j = std::abs(j);
540 q = std::floor(t.x[0] / _pi16.x[0] + 0.5);
541 t -= _pi16 * q;
542 int k = static_cast<int>(q);
543 int abs_k = std::abs(k);
544
545 if (abs_j > 2) {
546 dd_real::error("(dd_real::sincos): Cannot reduce modulo pi/2.");
547 cos_a = sin_a = dd_real::_nan;
548 return;
549 }
550
551 if (abs_k > 4) {
552 dd_real::error("(dd_real::sincos): Cannot reduce modulo pi/16.");
553 cos_a = sin_a = dd_real::_nan;
554 return;
555 }
556
557 dd_real sin_t, cos_t;
558 dd_real s, c;
559
560 sincos_taylor(t, sin_t, cos_t);
561
562 if (abs_k == 0) {
563 s = sin_t;
564 c = cos_t;
565 } else {
566 dd_real u(cos_table[abs_k-1][0], cos_table[abs_k-1][1]);
567 dd_real v(sin_table[abs_k-1][0], sin_table[abs_k-1][1]);
568
569 if (k > 0) {
570 s = u * sin_t + v * cos_t;
571 c = u * cos_t - v * sin_t;
572 } else {
573 s = u * sin_t - v * cos_t;
574 c = u * cos_t + v * sin_t;
575 }
576 }
577
578 if (abs_j == 0) {
579 sin_a = s;
580 cos_a = c;
581 } else if (j == 1) {
582 sin_a = c;
583 cos_a = -s;
584 } else if (j == -1) {
585 sin_a = -c;
586 cos_a = s;
587 } else {
588 sin_a = -s;
589 cos_a = -c;
590 }
591
592 }
593
594 dd_real atan(const dd_real &a) {
595 return atan2(a, dd_real(1.0));
596 }
597
598 dd_real atan2(const dd_real &y, const dd_real &x) {
599 /* Strategy: Instead of using Taylor series to compute
600 arctan, we instead use Newton's iteration to solve
601 the equation
602
603 sin(z) = y/r or cos(z) = x/r
604
605 where r = sqrt(x^2 + y^2).
606 The iteration is given by
607
608 z' = z + (y - sin(z)) / cos(z) (for equation 1)
609 z' = z - (x - cos(z)) / sin(z) (for equation 2)
610
611 Here, x and y are normalized so that x^2 + y^2 = 1.
612 If |x| > |y|, then first iteration is used since the
613 denominator is larger. Otherwise, the second is used.
614 */
615
616 if (x.is_zero()) {
617
618 if (y.is_zero()) {
619 /* Both x and y is zero. */
620 dd_real::error("(dd_real::atan2): Both arguments zero.");
621 return dd_real::_nan;
622 }
623
624 return (y.is_positive()) ? dd_real::_pi2 : -dd_real::_pi2;
625 } else if (y.is_zero()) {
626 return (x.is_positive()) ? dd_real(0.0) : dd_real::_pi;
627 }
628
629 if (x == y) {
630 return (y.is_positive()) ? dd_real::_pi4 : -dd_real::_3pi4;
631 }
632
633 if (x == -y) {
634 return (y.is_positive()) ? dd_real::_3pi4 : -dd_real::_pi4;
635 }
636
637 dd_real r = sqrt(sqr(x) + sqr(y));
638 dd_real xx = x / r;
639 dd_real yy = y / r;
640
641 /* Compute double precision approximation to atan. */
642 dd_real z = std::atan2(to_double(y), to_double(x));
643 dd_real sin_z, cos_z;
644
645 if (std::abs(xx.x[0]) > std::abs(yy.x[0])) {
646 /* Use Newton iteration 1. z' = z + (y - sin(z)) / cos(z) */
647 sincos(z, sin_z, cos_z);
648 z += (yy - sin_z) / cos_z;
649 } else {
650 /* Use Newton iteration 2. z' = z - (x - cos(z)) / sin(z) */
651 sincos(z, sin_z, cos_z);
652 z -= (xx - cos_z) / sin_z;
653 }
654
655 return z;
656 }
657
658 dd_real tan(const dd_real &a) {
659 dd_real s, c;
660 sincos(a, s, c);
661 return s/c;
662 }
663
664 dd_real asin(const dd_real &a) {
665 dd_real abs_a = abs(a);
666
667 if (abs_a > 1.0) {
668 dd_real::error("(dd_real::asin): Argument out of domain.");
669 return dd_real::_nan;
670 }
671
672 if (abs_a.is_one()) {
673 return (a.is_positive()) ? dd_real::_pi2 : -dd_real::_pi2;
674 }
675
676 return atan2(a, sqrt(1.0 - sqr(a)));
677 }
678
679 dd_real acos(const dd_real &a) {
680 dd_real abs_a = abs(a);
681
682 if (abs_a > 1.0) {
683 dd_real::error("(dd_real::acos): Argument out of domain.");
684 return dd_real::_nan;
685 }
686
687 if (abs_a.is_one()) {
688 return (a.is_positive()) ? dd_real(0.0) : dd_real::_pi;
689 }
690
691 return atan2(sqrt(1.0 - sqr(a)), a);
692 }
693
694 dd_real sinh(const dd_real &a) {
695 if (a.is_zero()) {
696 return 0.0;
697 }
698
699 if (abs(a) > 0.05) {
700 dd_real ea = exp(a);
701 return mul_pwr2(ea - inv(ea), 0.5);
702 }
703
704 /* since a is small, using the above formula gives
705 a lot of cancellation. So use Taylor series. */
706 dd_real s = a;
707 dd_real t = a;
708 dd_real r = sqr(t);
709 double m = 1.0;
710 double thresh = std::abs((to_double(a)) * dd_real::_eps);
711
712 do {
713 m += 2.0;
714 t *= r;
715 t /= (m-1) * m;
716
717 s += t;
718 } while (abs(t) > thresh);
719
720 return s;
721
722 }
723
724 dd_real cosh(const dd_real &a) {
725 if (a.is_zero()) {
726 return 1.0;
727 }
728
729 dd_real ea = exp(a);
730 return mul_pwr2(ea + inv(ea), 0.5);
731 }
732
733 dd_real tanh(const dd_real &a) {
734 if (a.is_zero()) {
735 return 0.0;
736 }
737
738 if (std::abs(to_double(a)) > 0.05) {
739 dd_real ea = exp(a);
740 dd_real inv_ea = inv(ea);
741 return (ea - inv_ea) / (ea + inv_ea);
742 } else {
743 dd_real s, c;
744 s = sinh(a);
745 c = sqrt(1.0 + sqr(s));
746 return s / c;
747 }
748 }
749
750 void sincosh(const dd_real &a, dd_real &s, dd_real &c) {
751 if (std::abs(to_double(a)) <= 0.05) {
752 s = sinh(a);
753 c = sqrt(1.0 + sqr(s));
754 } else {
755 dd_real ea = exp(a);
756 dd_real inv_ea = inv(ea);
757 s = mul_pwr2(ea - inv_ea, 0.5);
758 c = mul_pwr2(ea + inv_ea, 0.5);
759 }
760 }
761
762 dd_real asinh(const dd_real &a) {
763 return log(a + sqrt(sqr(a) + 1.0));
764 }
765
766 dd_real acosh(const dd_real &a) {
767 if (a < 1.0) {
768 dd_real::error("(dd_real::acosh): Argument out of domain.");
769 return dd_real::_nan;
770 }
771
772 return log(a + sqrt(sqr(a) - 1.0));
773 }
774
775 dd_real atanh(const dd_real &a) {
776 if (abs(a) >= 1.0) {
777 dd_real::error("(dd_real::atanh): Argument out of domain.");
778 return dd_real::_nan;
779 }
780
781 return mul_pwr2(log((1.0 + a) / (1.0 - a)), 0.5);
782 }
783
784 QD_API dd_real fmod(const dd_real &a, const dd_real &b) {
785 dd_real n = aint(a / b);
786 return (a - b * n);
787 }
788
789 QD_API dd_real ddrand() {
790 static const double m_const = 4.6566128730773926e-10; /* = 2^{-31} */
791 double m = m_const;
792 dd_real r = 0.0;
793 double d;
794
795 /* Strategy: Generate 31 bits at a time, using lrand48
796 random number generator. Shift the bits, and reapeat
797 4 times. */
798
799 for (int i = 0; i < 4; i++, m *= m_const) {
800 // d = lrand48() * m;
801 d = std::rand() * m;
802 r += d;
803 }
804
805 return r;
806 }
807
808 /* polyeval(c, n, x)
809 Evaluates the given n-th degree polynomial at x.
810 The polynomial is given by the array of (n+1) coefficients. */
811 dd_real polyeval(const dd_real *c, int n, const dd_real &x) {
812 /* Just use Horner's method of polynomial evaluation. */
813 dd_real r = c[n];
814
815 for (int i = n-1; i >= 0; i--) {
816 r *= x;
817 r += c[i];
818 }
819
820 return r;
821 }
822
823 /* polyroot(c, n, x0)
824 Given an n-th degree polynomial, finds a root close to
825 the given guess x0. Note that this uses simple Newton
826 iteration scheme, and does not work for multiple roots. */
827 QD_API dd_real polyroot(const dd_real *c, int n,
828 const dd_real &x0, int max_iter, double thresh) {
829 dd_real x = x0;
830 dd_real f;
831 dd_real *d = new dd_real[n];
832 bool conv = false;
833 int i;
834 double max_c = std::abs(to_double(c[0]));
835 double v;
836
837 if (thresh == 0.0) thresh = dd_real::_eps;
838
839 /* Compute the coefficients of the derivatives. */
840 for (i = 1; i <= n; i++) {
841 v = std::abs(to_double(c[i]));
842 if (v > max_c) max_c = v;
843 d[i-1] = c[i] * static_cast<double>(i);
844 }
845 thresh *= max_c;
846
847 /* Newton iteration. */
848 for (i = 0; i < max_iter; i++) {
849 f = polyeval(c, n, x);
850
851 if (abs(f) < thresh) {
852 conv = true;
853 break;
854 }
855 x -= (f / polyeval(d, n-1, x));
856 }
857 delete [] d;
858
859 if (!conv) {
860 dd_real::error("(dd_real::polyroot): Failed to converge.");
861 return dd_real::_nan;
862 }
863
864 return x;
865 }
866
867
868 /* Constructor. Reads a double-double number from the string s
869 and constructs a double-double number. */
870 dd_real::dd_real(const char *s) {
871 if (dd_real::read(s, *this)) {
872 dd_real::error("(dd_real::dd_real): INPUT ERROR.");
873 *this = dd_real::_nan;
874 }
875 }
876
877 dd_real &dd_real::operator=(const char *s) {
878 if (dd_real::read(s, *this)) {
879 dd_real::error("(dd_real::operator=): INPUT ERROR.");
880 *this = dd_real::_nan;
881 }
882 return *this;
883 }
884
885 /* Outputs the double-double number dd. */
886 ostream &operator<<(ostream &os, const dd_real &dd) {
887 bool showpos = (os.flags() & ios_base::showpos) != 0;
888 bool uppercase = (os.flags() & ios_base::uppercase) != 0;
889 return os << dd.to_string(os.precision(), os.width(), os.flags(),
890 showpos, uppercase, os.fill());
891 }
892
893 /* Reads in the double-double number a. */
894 istream &operator>>(istream &s, dd_real &a) {
895 char str[255];
896 s >> str;
897 a = dd_real(str);
898 return s;
899 }
900
901 void dd_real::to_digits(char *s, int &expn, int precision) const {
902 int D = precision + 1; /* number of digits to compute */
903
904 dd_real r = abs(*this);
905 int e; /* exponent */
906 int i, d;
907
908 if (x[0] == 0.0) {
909 /* this == 0.0 */
910 expn = 0;
911 for (i = 0; i < precision; i++) s[i] = '0';
912 return;
913 }
914
915 /* First determine the (approximate) exponent. */
916 e = to_int(std::floor(std::log10(std::abs(x[0]))));
917
918 if (e < -300) {
919 r *= dd_real(10.0) ^ 300;
920 r /= dd_real(10.0) ^ (e + 300);
921 } else if (e > 300) {
922 r = ldexp(r, -53);
923 r /= dd_real(10.0) ^ e;
924 r = ldexp(r, 53);
925 } else {
926 r /= dd_real(10.0) ^ e;
927 }
928
929 /* Fix exponent if we are off by one */
930 if (r >= 10.0) {
931 r /= 10.0;
932 e++;
933 } else if (r < 1.0) {
934 r *= 10.0;
935 e--;
936 }
937
938 if (r >= 10.0 || r < 1.0) {
939 dd_real::error("(dd_real::to_digits): can't compute exponent.");
940 return;
941 }
942
943 /* Extract the digits */
944 for (i = 0; i < D; i++) {
945 d = static_cast<int>(r.x[0]);
946 r -= d;
947 r *= 10.0;
948
949 s[i] = static_cast<char>(d + '0');
950 }
951
952 /* Fix out of range digits. */
953 for (i = D-1; i > 0; i--) {
954 if (s[i] < '0') {
955 s[i-1]--;
956 s[i] += 10;
957 } else if (s[i] > '9') {
958 s[i-1]++;
959 s[i] -= 10;
960 }
961 }
962
963 if (s[0] <= '0') {
964 dd_real::error("(dd_real::to_digits): non-positive leading digit.");
965 return;
966 }
967
968 /* Round, handle carry */
969 if (s[D-1] >= '5') {
970 s[D-2]++;
971
972 i = D-2;
973 while (i > 0 && s[i] > '9') {
974 s[i] -= 10;
975 s[--i]++;
976 }
977 }
978
979 /* If first digit is 10, shift everything. */
980 if (s[0] > '9') {
981 e++;
982 for (i = precision; i >= 2; i--) s[i] = s[i-1];
983 s[0] = '1';
984 s[1] = '0';
985 }
986
987 s[precision] = 0;
988 expn = e;
989 }
990
991 /* Writes the double-double number into the character array s of length len.
992 The integer d specifies how many significant digits to write.
993 The string s must be able to hold at least (d+8) characters.
994 showpos indicates whether to use the + sign, and uppercase indicates
995 whether the E or e is to be used for the exponent. */
996 void dd_real::write(char *s, int len, int precision,
997 bool showpos, bool uppercase) const {
998 string str = to_string(precision, 0, ios_base::scientific, showpos, uppercase);
999 std::strncpy(s, str.c_str(), len-1);
1000 s[len-1] = 0;
1001 }
1002
1003
1004 void round_string(char *s, int precision, int *offset){
1005 /*
1006 Input string must be all digits or errors will occur.
1007 */
1008
1009 int i;
1010 int D = precision ;
1011
1012 /* Round, handle carry */
1013 if (s[D-1] >= '5') {
1014 s[D-2]++;
1015
1016 i = D-2;
1017 while (i > 0 && s[i] > '9') {
1018 s[i] -= 10;
1019 s[--i]++;
1020 }
1021 }
1022
1023 /* If first digit is 10, shift everything. */
1024 if (s[0] > '9') {
1025 // e++; // don't modify exponent here
1026 for (i = precision; i >= 2; i--) s[i] = s[i-1];
1027 s[0] = '1';
1028 s[1] = '0';
1029
1030 (*offset)++ ; // now offset needs to be increased by one
1031 precision++ ;
1032 }
1033
1034 s[precision] = 0; // add terminator for array
1035 }
1036
1037 string dd_real::to_string(int precision, int width, ios_base::fmtflags fmt,
1038 bool showpos, bool uppercase, char fill) const {
1039 string s;
1040 bool fixed = (fmt & ios_base::fixed) != 0;
1041 bool sgn = true;
1042 int i, e = 0;
1043
1044 if (isnan()) {
1045 s = uppercase ? "NAN" : "nan";
1046 sgn = false;
1047 } else {
1048 if (*this < 0.0)
1049 s += '-';
1050 else if (showpos)
1051 s += '+';
1052 else
1053 sgn = false;
1054
1055 if (isinf()) {
1056 s += uppercase ? "INF" : "inf";
1057 } else if (*this == 0.0) {
1058 /* Zero case */
1059 s += '0';
1060 if (precision > 0) {
1061 s += '.';
1062 s.append(precision, '0');
1063 }
1064 } else {
1065 /* Non-zero case */
1066 int off = (fixed ? (1 + to_int(floor(log10(abs(*this))))) : 1);
1067 int d = precision + off;
1068
1069 int d_with_extra = d;
1070 if(fixed)
1071 d_with_extra = std::max(60, d); // longer than the max accuracy for DD
1072
1073 // highly special case - fixed mode, precision is zero, abs(*this) < 1.0
1074 // without this trap a number like 0.9 printed fixed with 0 precision prints as 0
1075 // should be rounded to 1.
1076 if(fixed && (precision == 0) && (abs(*this) < 1.0)){
1077 if(abs(*this) >= 0.5)
1078 s += '1';
1079 else
1080 s += '0';
1081
1082 return s;
1083 }
1084
1085 // handle near zero to working precision (but not exactly zero)
1086 if (fixed && d <= 0) {
1087 s += '0';
1088 if (precision > 0) {
1089 s += '.';
1090 s.append(precision, '0');
1091 }
1092 } else { // default
1093
1094 char *t; // = new char[d+1];
1095 int j;
1096
1097 if(fixed){
1098 t = new char[d_with_extra+1];
1099 to_digits(t, e, d_with_extra);
1100 }
1101 else{
1102 t = new char[d+1];
1103 to_digits(t, e, d);
1104 }
1105
1106 if (fixed) {
1107 // fix the string if it's been computed incorrectly
1108 // round here in the decimal string if required
1109 round_string(t, d + 1 , &off);
1110
1111 if (off > 0) {
1112 for (i = 0; i < off; i++) s += t[i];
1113 if (precision > 0) {
1114 s += '.';
1115 for (j = 0; j < precision; j++, i++) s += t[i];
1116 }
1117 } else {
1118 s += "0.";
1119 if (off < 0) s.append(-off, '0');
1120 for (i = 0; i < d; i++) s += t[i];
1121 }
1122 } else {
1123 s += t[0];
1124 if (precision > 0) s += '.';
1125
1126 for (i = 1; i <= precision; i++)
1127 s += t[i];
1128
1129 }
1130 delete [] t;
1131 }
1132 }
1133
1134 // trap for improper offset with large values
1135 // without this trap, output of values of the for 10^j - 1 fail for j > 28
1136 // and are output with the point in the wrong place, leading to a dramatically off value
1137 if(fixed && (precision > 0)){
1138 // make sure that the value isn't dramatically larger
1139 double from_string = atof(s.c_str());
1140
1141 // if this ratio is large, then we've got problems
1142 if( fabs( from_string / this->x[0] ) > 3.0 ){
1143
1144 int point_position;
1145 char temp;
1146
1147 // loop on the string, find the point, move it up one
1148 // don't act on the first character
1149 for(i=1; i < s.length(); i++){
1150 if(s[i] == '.'){
1151 s[i] = s[i-1] ;
1152 s[i-1] = '.' ;
1153 break;
1154 }
1155 }
1156
1157 from_string = atof(s.c_str());
1158 // if this ratio is large, then the string has not been fixed
1159 if( fabs( from_string / this->x[0] ) > 3.0 ){
1160 dd_real::error("Re-rounding unsuccessful in large number fixed point trap.") ;
1161 }
1162 }
1163 }
1164
1165
1166 if (!fixed && !isinf()) {
1167 /* Fill in exponent part */
1168 s += uppercase ? 'E' : 'e';
1169 append_expn(s, e);
1170 }
1171 }
1172
1173 /* Fill in the blanks */
1174 int len = s.length();
1175 if (len < width) {
1176 int delta = width - len;
1177 if (fmt & ios_base::internal) {
1178 if (sgn)
1179 s.insert(static_cast<string::size_type>(1), delta, fill);
1180 else
1181 s.insert(static_cast<string::size_type>(0), delta, fill);
1182 } else if (fmt & ios_base::left) {
1183 s.append(delta, fill);
1184 } else {
1185 s.insert(static_cast<string::size_type>(0), delta, fill);
1186 }
1187 }
1188
1189 return s;
1190 }
1191
1192 /* Reads in a double-double number from the string s. */
1193 int dd_real::read(const char *s, dd_real &a) {
1194 const char *p = s;
1195 char ch;
1196 int sign = 0;
1197 int point = -1;
1198 int nd = 0;
1199 int e = 0;
1200 bool done = false;
1201 dd_real r = 0.0;
1202 int nread;
1203
1204 /* Skip any leading spaces */
1205 while (*p == ' ')
1206 p++;
1207
1208 while (!done && (ch = *p) != '\0') {
1209 if (ch >= '0' && ch <= '9') {
1210 int d = ch - '0';
1211 r *= 10.0;
1212 r += static_cast<double>(d);
1213 nd++;
1214 } else {
1215
1216 switch (ch) {
1217
1218 case '.':
1219 if (point >= 0)
1220 return -1;
1221 point = nd;
1222 break;
1223
1224 case '-':
1225 case '+':
1226 if (sign != 0 || nd > 0)
1227 return -1;
1228 sign = (ch == '-') ? -1 : 1;
1229 break;
1230
1231 case 'E':
1232 case 'e':
1233 nread = std::sscanf(p+1, "%d", &e);
1234 done = true;
1235 if (nread != 1)
1236 return -1;
1237 break;
1238
1239 default:
1240 return -1;
1241 }
1242 }
1243
1244 p++;
1245 }
1246
1247 if (point >= 0) {
1248 e -= (nd - point);
1249 }
1250
1251 if (e != 0) {
1252 r *= (dd_real(10.0) ^ e);
1253 }
1254
1255 a = (sign == -1) ? -r : r;
1256 return 0;
1257 }
1258 #if 0
1259 /* Debugging routines */
1260 void dd_real::dump(const string &name, std::ostream &os) const {
1261 std::ios_base::fmtflags old_flags = os.flags();
1262 std::streamsize old_prec = os.precision(19);
1263 os << std::scientific;
1264
1265 if (name.length() > 0) os << name << " = ";
1266 os << "[ " << setw(27) << x[0] << ", " << setw(27) << x[1] << " ]" << endl;
1267
1268 os.precision(old_prec);
1269 os.flags(old_flags);
1270 }
1271
1272 void dd_real::dump_bits(const string &name, std::ostream &os) const {
1273 string::size_type len = name.length();
1274 if (len > 0) {
1275 os << name << " = ";
1276 len +=3;
1277 }
1278 os << "[ ";
1279 len += 2;
1280 print_double_info(os, x[0]);
1281 os << endl;
1282 for (string::size_type i = 0; i < len; i++) os << ' ';
1283 print_double_info(os, x[1]);
1284 os << " ]" << endl;
1285 }
1286 #endif
1287 dd_real dd_real::debug_rand() {
1288
1289 if (std::rand() % 2 == 0)
1290 return ddrand();
1291
1292 int expn = 0;
1293 dd_real a = 0.0;
1294 double d;
1295 for (int i = 0; i < 2; i++) {
1296 d = std::ldexp(static_cast<double>(std::rand()) / RAND_MAX, -expn);
1297 a += d;
1298 expn = expn + 54 + std::rand() % 200;
1299 }
1300 return a;
1301 }
1302