Scippy

SCIP

Solving Constraint Integer Programs

dbldblarith.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2018 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file dbldblarith.h
17  * @brief defines macros for basic operations in double-double arithmetic giving roughly twice the precision of a double
18  * @author Robert Lion Gottwald
19  *
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef _SCIP_DBLDBL_ARITH_
25 #define _SCIP_DBLDBL_ARITH_
26 
27 #include "math.h"
28 
29 
30 #ifndef DISABLE_QUADPREC
31 
32 /* smaller epsilon value for use with quadprecision */
33 #define QUAD_EPSILON 1e-12
34 
35 /* convenience macros for nicer usage of double double arithmetic */
36 #define QUAD_HI(x) x ## hi
37 #define QUAD_LO(x) x ## lo
38 #define QUAD(x) QUAD_HI(x), QUAD_LO(x)
39 #define QUAD_MEMBER(x) QUAD_HI(x); QUAD_LO(x)
40 #define QUAD_TO_DBL(x) ( QUAD_HI(x) + QUAD_LO(x) )
41 #define QUAD_SCALE(x, a) do { QUAD_HI(x) *= (a); QUAD_LO(x) *= (a); } while(0)
42 #define QUAD_ASSIGN(a, constant) do { QUAD_HI(a) = (constant); QUAD_LO(a) = 0.0; } while(0)
43 #define QUAD_ASSIGN_Q(a, b) do { QUAD_HI(a) = QUAD_HI(b); QUAD_LO(a) = QUAD_LO(b); } while(0)
44 #define QUAD_ARRAY_SIZE(size) ((size)*2)
45 #define QUAD_ARRAY_LOAD(r, a, idx) do { QUAD_HI(r) = (a)[2*(idx)]; QUAD_LO(r) = (a)[2*(idx) + 1]; } while(0)
46 #define QUAD_ARRAY_STORE(a, idx, x) do { (a)[2*(idx)] = QUAD_HI(x); (a)[2*(idx) + 1] = QUAD_LO(x); } while(0)
47 
48 /* define all the SCIPquadprec... macros such that they use the SCIPdbldbl... macros that expands the quad precision arguments using the above macros */
49 #define SCIPquadprecProdDD(r, a, b) SCIPdbldblProd(QUAD_HI(r), QUAD_LO(r), a, b)
50 #define SCIPquadprecSquareD(r, a) SCIPdbldblSquare(QUAD_HI(r), QUAD_LO(r), a)
51 #define SCIPquadprecSumDD(r, a, b) SCIPdbldblSum(QUAD_HI(r), QUAD_LO(r), a, b)
52 #define SCIPquadprecDivDD(r, a, b) SCIPdbldblDiv(QUAD_HI(r), QUAD_LO(r), a, b)
53 #define SCIPquadprecSumQD(r, a, b) SCIPdbldblSum21(QUAD_HI(r), QUAD_LO(r), QUAD_HI(a), QUAD_LO(a), b)
54 #define SCIPquadprecProdQD(r, a, b) SCIPdbldblProd21(QUAD_HI(r), QUAD_LO(r), QUAD_HI(a), QUAD_LO(a), b)
55 #define SCIPquadprecDivDQ(r, a, b) SCIPdbldblDiv12(QUAD_HI(r), QUAD_LO(r), a, QUAD_HI(b), QUAD_LO(b))
56 #define SCIPquadprecDivQD(r, a, b) SCIPdbldblDiv21(QUAD_HI(r), QUAD_LO(r), QUAD_HI(a), QUAD_LO(a), b)
57 #define SCIPquadprecProdQQ(r, a, b) SCIPdbldblProd22(QUAD_HI(r), QUAD_LO(r), QUAD_HI(a), QUAD_LO(a), QUAD_HI(b), QUAD_LO(b))
58 #define SCIPquadprecSumQQ(r, a, b) SCIPdbldblSum22(QUAD_HI(r), QUAD_LO(r), QUAD_HI(a), QUAD_LO(a), QUAD_HI(b), QUAD_LO(b))
59 #define SCIPquadprecSquareQ(r, a) SCIPdbldblSquare2(QUAD_HI(r), QUAD_LO(r), QUAD_HI(a), QUAD_LO(a))
60 #define SCIPquadprecDivQQ(r, a, b) SCIPdbldblDiv22(QUAD_HI(r), QUAD_LO(r), QUAD_HI(a), QUAD_LO(a), QUAD_HI(b), QUAD_LO(b))
61 #define SCIPquadprecSqrtD(r, a) SCIPdbldblSqrt(QUAD_HI(r), QUAD_LO(r), a)
62 #define SCIPquadprecSqrtQ(r, a) SCIPdbldblSqrt2(QUAD_HI(r), QUAD_LO(r), QUAD_HI(a), QUAD_LO(a))
63 #define SCIPquadprecAbsQ(r, a) SCIPdbldblAbs2(QUAD_HI(r), QUAD_LO(r), QUAD_HI(a), QUAD_LO(a))
64 #define SCIPquadprecFloorQ(r, a) SCIPdbldblFloor2(QUAD_HI(r), QUAD_LO(r), QUAD_HI(a), QUAD_LO(a))
65 #define SCIPquadprecCeilQ(r, a) SCIPdbldblCeil2(QUAD_HI(r), QUAD_LO(r), QUAD_HI(a), QUAD_LO(a))
66 #define SCIPquadprecEpsFloorQ(r, a, eps) SCIPdbldblEpsFloor2(QUAD_HI(r), QUAD_LO(r), QUAD_HI(a), QUAD_LO(a), eps)
67 #define SCIPquadprecEpsCeilQ(r, a, eps) SCIPdbldblEpsCeil2(QUAD_HI(r), QUAD_LO(r), QUAD_HI(a), QUAD_LO(a), eps)
68 
69 #else
70 
71 /* normal epsilon value if quadprecision is disabled */
72 #define QUAD_EPSILON 1e-9
73 
74 /* dummy macros that use normal arithmetic */
75 #define QUAD_HI(x) x
76 #define QUAD_LO(x) 0.0
77 #define QUAD(x) x
78 #define QUAD_MEMBER(x) x
79 #define QUAD_TO_DBL(x) (x)
80 #define QUAD_SCALE(x, a) do { (x) *= (a); } while(0)
81 #define QUAD_ASSIGN(a, constant) do { (a) = constant; } while(0)
82 #define QUAD_ASSIGN_Q(a, b) do { (a) = (b); } while(0)
83 #define QUAD_ARRAY_SIZE(size) (size)
84 #define QUAD_ARRAY_LOAD(r, a, idx) do { r = (a)[(idx)]; } while(0)
85 #define QUAD_ARRAY_STORE(a, idx, x) do { (a)[(idx)] = (x); } while(0)
86 
87 #define SCIPquadprecProdDD(r, a, b) do { (r) = (a) * (b); } while(0)
88 #define SCIPquadprecSquareD(r, a) do { (r) = (a) * (a); } while(0)
89 #define SCIPquadprecSumDD(r, a, b) do { (r) = (a) + (b); } while(0)
90 #define SCIPquadprecDivDD(r, a, b) do { (r) = (a) / (b); } while(0)
91 #define SCIPquadprecSumQD(r, a, b) do { (r) = (a) + (b); } while(0)
92 #define SCIPquadprecProdQD(r, a, b) do { (r) = (a) * (b); } while(0)
93 #define SCIPquadprecDivDQ(r, a, b) do { (r) = (a) / (b); } while(0)
94 #define SCIPquadprecDivQD(r, a, b) do { (r) = (a) / (b); } while(0)
95 #define SCIPquadprecProdQQ(r, a, b) do { (r) = (a) * (b); } while(0)
96 #define SCIPquadprecSumQQ(r, a, b) do { (r) = (a) + (b); } while(0)
97 #define SCIPquadprecSquareQ(r, a) do { (r) = (a) * (a); } while(0)
98 #define SCIPquadprecDivQQ(r, a, b) do { (r) = (a) / (b); } while(0)
99 #define SCIPquadprecSqrtD(r, a) do { (r) = sqrt(a); } while(0)
100 #define SCIPquadprecSqrtQ(r, a) do { (r) = sqrt(a); } while(0)
101 #define SCIPquadprecAbsQ(r, a) do { (r) = fabs(a); } while(0)
102 #define SCIPquadprecFloorQ(r, a) do { (r) = floor(a); } while(0)
103 #define SCIPquadprecCeilQ(r, a) do { (r) = ceil(a); } while(0)
104 #define SCIPquadprecEpsFloorQ(r, a, eps) do { (r) = floor((a) + (eps)); } while(0)
105 #define SCIPquadprecEpsCeilQ(r, a, eps) do { (r) = ceil((a) - (eps)); } while(0)
106 
107 #endif
108 
109 #define __SCIPdbldblSplit(rhi, rlo, x) \
110  do { \
111  const double __tmp_split_dbl = 134217729.0 * (x); \
112  (rhi) = __tmp_split_dbl - (__tmp_split_dbl - (x)); \
113  (rlo) = (x) - (rhi);\
114  } while(0)
115 
116 /** multiply two floating point numbers, both given by one double, and return the result as two doubles. */
117 #define SCIPdbldblProd(rhi, rlo, a, b) \
118  do { \
119  double __tmp_dbldbl_prod_ahi; \
120  double __tmp_dbldbl_prod_alo; \
121  double __tmp_dbldbl_prod_bhi; \
122  double __tmp_dbldbl_prod_blo; \
123  __SCIPdbldblSplit(__tmp_dbldbl_prod_ahi, __tmp_dbldbl_prod_alo, a); \
124  __SCIPdbldblSplit(__tmp_dbldbl_prod_bhi, __tmp_dbldbl_prod_blo, b); \
125  (rhi) = (a) * (b); \
126  (rlo) = __tmp_dbldbl_prod_alo * __tmp_dbldbl_prod_blo - \
127  ((((rhi) - __tmp_dbldbl_prod_ahi * __tmp_dbldbl_prod_bhi) \
128  - __tmp_dbldbl_prod_alo * __tmp_dbldbl_prod_bhi) \
129  - __tmp_dbldbl_prod_ahi * __tmp_dbldbl_prod_blo); \
130  } while(0)
131 
132 /** square a floating point number given by one double and return the result as two doubles. */
133 #define SCIPdbldblSquare(rhi, rlo, a) \
134  do { \
135  double __tmp_dbldbl_square_ahi; \
136  double __tmp_dbldbl_square_alo; \
137  __SCIPdbldblSplit(__tmp_dbldbl_square_ahi, __tmp_dbldbl_square_alo, a); \
138  (rhi) = (a) * (a); \
139  (rlo) = __tmp_dbldbl_square_alo * __tmp_dbldbl_square_alo - \
140  ((((rhi) - __tmp_dbldbl_square_ahi * __tmp_dbldbl_square_ahi) \
141  - 2.0 * __tmp_dbldbl_square_alo * __tmp_dbldbl_square_ahi)); \
142  } while(0)
143 
144 /** add two floating point numbers, both given by one double, and return the result as two doubles. */
145 #define SCIPdbldblSum(rhi, rlo, a, b) \
146  do { \
147  double __tmp1_dbldbl_sum; \
148  double __tmp2_dbldbl_sum; \
149  __tmp2_dbldbl_sum = (a) + (b); \
150  __tmp1_dbldbl_sum = __tmp2_dbldbl_sum - (a); \
151  (rlo) = ((a) - (__tmp2_dbldbl_sum - __tmp1_dbldbl_sum)) + ((b) - __tmp1_dbldbl_sum); \
152  (rhi) = __tmp2_dbldbl_sum; \
153  } while(0)
154 
155 /** divide two floating point numbers, both given by one double, and return the result as two doubles. */
156 #define SCIPdbldblDiv(rhi, rlo, a, b) \
157  do { \
158  double __tmp_dbldbl_div_hi; \
159  double __tmp_dbldbl_div_lo; \
160  double __estim_dbldbl_div = (a)/(b); \
161  SCIPdbldblProd(__tmp_dbldbl_div_hi, __tmp_dbldbl_div_lo, b, __estim_dbldbl_div); \
162  SCIPdbldblSum21(__tmp_dbldbl_div_hi, __tmp_dbldbl_div_lo, __tmp_dbldbl_div_hi, __tmp_dbldbl_div_lo, -(a)); \
163  __tmp_dbldbl_div_hi /= (b); \
164  __tmp_dbldbl_div_lo /= (b); \
165  SCIPdbldblSum21(rhi, rlo, -__tmp_dbldbl_div_hi, -__tmp_dbldbl_div_lo, __estim_dbldbl_div); \
166  } while(0)
167 
168 /** add two floating point numbers, the first is given by two doubles, the second is given by one double,
169  * and return the result as two doubles.
170  */
171 #define SCIPdbldblSum21(rhi, rlo, ahi, alo, b) \
172  do { \
173  double __tmp_dbldbl_sum21_hi; \
174  double __tmp_dbldbl_sum21_lo; \
175  SCIPdbldblSum(__tmp_dbldbl_sum21_hi, __tmp_dbldbl_sum21_lo, ahi, b); \
176  (rlo) = __tmp_dbldbl_sum21_lo + (alo); \
177  (rhi) = __tmp_dbldbl_sum21_hi; \
178  } while(0)
179 
180 
181 /** multiply two floating point numbers, the first is given by two doubles, the second is given by one double,
182  * and return the result as two doubles.
183  */
184 #define SCIPdbldblProd21(rhi, rlo, ahi, alo, b) \
185  do { \
186  double __tmp_dbldbl_prod21_hi; \
187  double __tmp_dbldbl_prod21_lo; \
188  SCIPdbldblProd(__tmp_dbldbl_prod21_hi, __tmp_dbldbl_prod21_lo, ahi, b); \
189  (rlo) = (alo) * (b) + __tmp_dbldbl_prod21_lo; \
190  (rhi) = __tmp_dbldbl_prod21_hi; \
191  } while(0)
192 
193 /** divide two floating point numbers, the first is given by one double, the second is given by two doubles,
194  * and return the result as two doubles.
195  */
196 #define SCIPdbldblDiv12(rhi, rlo, a, bhi, blo) \
197  do { \
198  double __tmp_dbldbl_div12_hi; \
199  double __tmp_dbldbl_div12_lo; \
200  double __estim_dbldbl_div12 = (a)/(bhi); \
201  SCIPdbldblProd21(__tmp_dbldbl_div12_hi, __tmp_dbldbl_div12_lo, bhi, blo, __estim_dbldbl_div12); \
202  SCIPdbldblSum21(__tmp_dbldbl_div12_hi, __tmp_dbldbl_div12_lo, __tmp_dbldbl_div12_hi, __tmp_dbldbl_div12_lo, -(a)); \
203  __tmp_dbldbl_div12_hi /= (bhi); \
204  __tmp_dbldbl_div12_lo /= (bhi); \
205  SCIPdbldblSum21(rhi, rlo, -__tmp_dbldbl_div12_hi, -__tmp_dbldbl_div12_lo, __estim_dbldbl_div12); \
206  } while(0)
207 
208 
209 /** divide two floating point numbers, the first is given by two doubles, the second is given by one double,
210  * and return the result as two doubles.
211  */
212 #define SCIPdbldblDiv21(rhi, rlo, ahi, alo, b) \
213  do { \
214  double __tmp_dbldbl_div21_hi; \
215  double __tmp_dbldbl_div21_lo; \
216  double __estim_dbldbl_div21_hi; \
217  double __estim_dbldbl_div21_lo; \
218  __estim_dbldbl_div21_hi = (ahi)/(b); \
219  __estim_dbldbl_div21_lo = (alo)/(b); \
220  SCIPdbldblProd21(__tmp_dbldbl_div21_hi, __tmp_dbldbl_div21_lo, __estim_dbldbl_div21_hi, __estim_dbldbl_div21_lo, b); \
221  SCIPdbldblSum22(__tmp_dbldbl_div21_hi, __tmp_dbldbl_div21_lo, __tmp_dbldbl_div21_hi, __tmp_dbldbl_div21_lo, -(ahi), -(alo)); \
222  __tmp_dbldbl_div21_hi /= (b); \
223  __tmp_dbldbl_div21_lo /= (b); \
224  SCIPdbldblSum22(rhi, rlo, __estim_dbldbl_div21_hi, __estim_dbldbl_div21_lo, -__tmp_dbldbl_div21_hi, -__tmp_dbldbl_div21_lo); \
225  } while(0)
226 
227 /** multiply two floating point numbers, both given by two doubles, and return the result as two doubles. */
228 #define SCIPdbldblProd22(rhi, rlo, ahi, alo, bhi, blo) \
229  do { \
230  double __tmp_dbldbl_prod22_hi; \
231  double __tmp_dbldbl_prod22_lo; \
232  SCIPdbldblProd(__tmp_dbldbl_prod22_hi, __tmp_dbldbl_prod22_lo, ahi, bhi); \
233  SCIPdbldblSum21(__tmp_dbldbl_prod22_hi, __tmp_dbldbl_prod22_lo, \
234  __tmp_dbldbl_prod22_hi, __tmp_dbldbl_prod22_lo, (alo) * (bhi)); \
235  SCIPdbldblSum21(rhi, rlo, \
236  __tmp_dbldbl_prod22_hi, __tmp_dbldbl_prod22_lo, (ahi) * (blo)); \
237  } while(0)
238 
239 /** add two floating point numbers, both given by two doubles, and return the result as two doubles. */
240 #define SCIPdbldblSum22(rhi, rlo, ahi, alo, bhi, blo) \
241  do { \
242  double __tmp_dbldbl_sum22_hi; \
243  double __tmp_dbldbl_sum22_lo; \
244  SCIPdbldblSum21(__tmp_dbldbl_sum22_hi, __tmp_dbldbl_sum22_lo, ahi, alo, bhi); \
245  SCIPdbldblSum21(rhi, rlo, __tmp_dbldbl_sum22_hi, __tmp_dbldbl_sum22_lo, blo); \
246  } while(0)
247 
248 /** square a floating point number given by two doubles and return the result as two doubles. */
249 #define SCIPdbldblSquare2(rhi, rlo, ahi, alo) \
250  do { \
251  double __tmp_dbldbl_square2_hi; \
252  double __tmp_dbldbl_square2_lo; \
253  SCIPdbldblSquare(__tmp_dbldbl_square2_hi, __tmp_dbldbl_square2_lo, (ahi)); \
254  SCIPdbldblSum21(rhi, rlo, __tmp_dbldbl_square2_hi, __tmp_dbldbl_square2_lo, 2 * (ahi) * (alo)); \
255  } while(0)
256 
257 /** divide two floating point numbers, both given by two doubles, and return the result as two doubles. */
258 #define SCIPdbldblDiv22(rhi, rlo, ahi, alo, bhi, blo) \
259  do { \
260  double __tmp_dbldbl_div22_hi; \
261  double __tmp_dbldbl_div22_lo; \
262  double __estim_dbldbl_div22_hi = (ahi) / (bhi); \
263  double __estim_dbldbl_div22_lo = (alo) / (bhi); \
264  SCIPdbldblProd22(__tmp_dbldbl_div22_hi, __tmp_dbldbl_div22_lo, \
265  bhi, blo, __estim_dbldbl_div22_hi, __estim_dbldbl_div22_lo); \
266  SCIPdbldblSum22(__tmp_dbldbl_div22_hi, __tmp_dbldbl_div22_lo, \
267  __tmp_dbldbl_div22_hi, __tmp_dbldbl_div22_lo, -(ahi), -(alo)); \
268  __tmp_dbldbl_div22_hi /= (bhi); \
269  __tmp_dbldbl_div22_lo /= (bhi); \
270  SCIPdbldblSum22(rhi, rlo, __estim_dbldbl_div22_hi, __estim_dbldbl_div22_lo, \
271  -__tmp_dbldbl_div22_hi, -__tmp_dbldbl_div22_lo); \
272  } while(0)
273 
274 
275 /** take the square root of a floating point number given by one double and return the result as two doubles. */
276 #define SCIPdbldblSqrt(rhi, rlo, a) \
277  do { \
278  double __estim_dbldbl_sqrt = sqrt(a); \
279  SCIPdbldblDiv(rhi, rlo, a, __estim_dbldbl_sqrt); \
280  SCIPdbldblSum21(rhi, rlo, rhi, rlo, __estim_dbldbl_sqrt); \
281  (rhi) *= 0.5; \
282  (rlo) *= 0.5; \
283  } while(0)
284 
285 
286 /** take the square root of a floating point number given by two doubles and return the result as two doubles. */
287 #define SCIPdbldblSqrt2(rhi, rlo, ahi, alo) \
288  do { \
289  double __estim_dbldbl_sqrt2 = sqrt(ahi); \
290  SCIPdbldblDiv21(rhi, rlo, ahi, alo, __estim_dbldbl_sqrt2); \
291  SCIPdbldblSum21(rhi, rlo, rhi, rlo, __estim_dbldbl_sqrt2); \
292  (rhi) *= 0.5; \
293  (rlo) *= 0.5; \
294  } while(0)
295 
296 /** compute the absolute value of the floating point number given by two doubles */
297 #define SCIPdbldblAbs2(rhi, rlo, ahi, alo) \
298  do { \
299  if( ahi < 0.0 ) \
300  { \
301  (rhi) = -(ahi); \
302  (rlo) = -(alo); \
303  } \
304  else \
305  { \
306  (rhi) = (ahi); \
307  (rlo) = (alo); \
308  } \
309  } while(0)
310 
311 /** compute the floored value of the floating point number given by two doubles */
312 #define SCIPdbldblFloor2(rhi, rlo, ahi, alo) \
313  do { \
314  double __tmp_dbldbl_floor; \
315  __tmp_dbldbl_floor = floor((ahi) + (alo)); \
316  SCIPdbldblSum21(rhi, rlo, ahi, alo, -__tmp_dbldbl_floor); \
317  if( ((rhi) - 1.0) + (rlo) < 0.0 && (rhi) + (rlo) >= 0.0 ) \
318  { \
319  /* floor in double precision was fine */ \
320  (rhi) = __tmp_dbldbl_floor; \
321  (rlo) = 0.0; \
322  } \
323  else \
324  { \
325  /* floor in double precision needs to be corrected */ \
326  double __tmp2_dbldbl_floor = floor((rhi) + (rlo)); \
327  SCIPdbldblSum(rhi, rlo, __tmp_dbldbl_floor, __tmp2_dbldbl_floor); \
328  } \
329  } while(0)
330 
331 /** compute the ceiled value of the floating point number given by two doubles */
332 #define SCIPdbldblCeil2(rhi, rlo, ahi, alo) \
333  do { \
334  double __tmp_dbldbl_ceil; \
335  __tmp_dbldbl_ceil = ceil((ahi) + (alo)); \
336  SCIPdbldblSum21(rhi, rlo, -(ahi), -(alo), __tmp_dbldbl_ceil); \
337  if( ((rhi) - 1.0) + (rlo) < 0.0 && (rhi) + (rlo) >= 0.0 ) \
338  { \
339  /* ceil in double precision was fine */ \
340  (rhi) = __tmp_dbldbl_ceil; \
341  (rlo) = 0.0; \
342  } \
343  else \
344  { \
345  /* ceil in double precision needs to be corrected */ \
346  double __tmp2_dbldbl_ceil = floor((rhi) + (rlo)); \
347  SCIPdbldblSum(rhi, rlo, __tmp_dbldbl_ceil, -__tmp2_dbldbl_ceil); \
348  } \
349  } while(0)
350 
351 /** compute the floored value of the floating point number given by two doubles, add epsilon first for safety */
352 #define SCIPdbldblEpsFloor2(rhi, rlo, ahi, alo, eps) SCIPdbldblFloor2(rhi, rlo, ahi, (alo) + (eps))
353 
354 /** compute the ceiled value of the floating point number given by two doubles, subtract epsilon first for safety */
355 #define SCIPdbldblEpsCeil2(rhi, rlo, ahi, alo, eps) SCIPdbldblCeil2(rhi, rlo, ahi, (alo) - (eps))
356 
357 #endif