GCC Code Coverage Report

Directory: ./
File: numerics/multi_precision.cpp
Date: 2026-09-27 03:24:14
Exec Total Coverage
Lines: 352 475 74.1%
Functions: 23 36 63.9%
Branches: 264 802 32.9%
Line Branch Exec Source
1 /*
2 * Copyright (c) 2000-2022 Inria
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * * Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above copyright notice,
11 * this list of conditions and the following disclaimer in the documentation
12 * and/or other materials provided with the distribution.
13 * * Neither the name of the ALICE Project-Team nor the names of its
14 * contributors may be used to endorse or promote products derived from this
15 * software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
21 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 * POSSIBILITY OF SUCH DAMAGE.
28 *
29 * Contact: Bruno Levy
30 *
31 * https://www.inria.fr/fr/bruno-levy
32 *
33 * Inria,
34 * Domaine de Voluceau,
35 * 78150 Le Chesnay - Rocquencourt
36 * FRANCE
37 *
38 */
39
40 #include <geogram/basic/common.h>
41 #include <geogram/basic/numeric.h>
42
43 // This makes sure the compiler will not optimize y = a*x+b
44 // with fused multiply-add, this would break the exact
45 // predicates.
46 GEO_FP_CONTRACT_OFF
47
48 #include <geogram/numerics/multi_precision.h>
49 #include <geogram/numerics/PCK.h>
50 #include <geogram/basic/process.h>
51 #include <geogram/basic/logger.h>
52
53 namespace {
54
55 using namespace GEO;
56
57 /************************************************************************/
58
59 /**
60 * \brief Computes the sum of a length 2 expansion and a double
61 * into a length 3 expansion.
62 * \param[in] a1 high-magnitude component of first argument
63 * \param[in] a0 low-magnitude component of first argument
64 * \param[in] b second argument
65 * \param[in] x2 high-magnitude component of the result
66 * \param[in] x1 component of the result
67 * \param[in] x0 low-magnitude component of the result
68 * \details By Jonathan Shewchuk.
69 */
70 18159282 inline void two_one_sum(
71 double a1, double a0, double b, double& x2, double& x1, double& x0
72 ) {
73 double _i;
74 18159282 two_sum(a0, b, _i, x0);
75 18159282 two_sum(a1, _i, x2, x1);
76 18159282 }
77
78 /**
79 * \brief Computes the sum of two length 2 expansions
80 * into a length 4 expansion.
81 * \param[in] a1 high-magnitude component of first argument
82 * \param[in] a0 low-magnitude component of first argument
83 * \param[in] b1 high-magnitude component of second argument
84 * \param[in] b0 high-magnitude component of second argument
85 * \param[in] x3 high-magnitude component of the result
86 * \param[in] x2 component of the result
87 * \param[in] x1 component of the result
88 * \param[in] x0 low-magnitude component of the result
89 * \details By Jonathan Shewchuk.
90 */
91 6053094 inline void two_two_sum(
92 double a1, double a0, double b1, double b0,
93 double& x3, double& x2, double& x1, double& x0
94 ) {
95 double _j, _0;
96 6053094 two_one_sum(a1, a0, b0, _j, _0, x0);
97 6053094 two_one_sum(_j, _0, b1, x3, x2, x1);
98 6053094 }
99
100 #ifndef FP_FAST_FMA
101
102 /**
103 * \brief Computes the product between two doubles where
104 * the second one have already been split.
105 * \param[in] a first argument
106 * \param[in] b second argument
107 * \param[in] bhi high-magnitude part of second argument
108 * \param[in] blo low-magnitude part of second argument
109 * \param[out] x high-magnitude component of the result
110 * \param[out] y low-magnitude component of the result
111 * \details By Jonathan Shewchuk.
112 */
113 inline void two_product_presplit(
114 double a, double b, double bhi, double blo, double& x, double& y
115 ) {
116 x = a * b;
117 double ahi;
118 double alo;
119 split(a, ahi, alo);
120 double err1 = x - (ahi * bhi);
121 double err2 = err1 - (alo * bhi);
122 double err3 = err2 - (ahi * blo);
123 y = (alo * blo) - err3;
124 }
125
126 /**
127 * \brief Computes the product between two doubles
128 * where both have already been split.
129 * \param[in] a first argument
130 * \param[in] ahi high-magnitude part of first argument
131 * \param[in] alo low-magnitude part of first argument
132 * \param[in] b second argument
133 * \param[in] bhi high-magnitude part of second argument
134 * \param[in] blo low-magnitude part of second argument
135 * \param[out] x high-magnitude component of the result
136 * \param[out] y low-magnitude component of the result
137 * \details By Jonathan Shewchuk.
138 */
139 inline void two_product_2presplit(
140 double a, double ahi, double alo,
141 double b, double bhi, double blo,
142 double& x, double& y
143 ) {
144 x = a * b;
145 double err1 = x - (ahi * bhi);
146 double err2 = err1 - (alo * bhi);
147 double err3 = err2 - (ahi * blo);
148 y = (alo * blo) - err3;
149 }
150
151 #endif
152
153 /**
154 * \brief Computes the square of an expansion of length 2.
155 * \param[in] a1 high-magnitude component of the argument
156 * \param[in] a0 low-magnitude component of the argument
157 * \param[out] x an array of six doubles to store the result.
158 * \details By Jonathan Shewchuk.
159 * An expansion of length two can be squared more quickly than finding the
160 * product of two different expansions of length two, and the result is
161 * guaranteed to have no more than six (rather than eight) components.
162 */
163 6053094 inline void two_square(
164 double a1, double a0,
165 double* x
166 ) {
167 double _0, _1, _2;
168 double _j, _k, _l;
169 6053094 square(a0, _j, x[0]);
170 6053094 _0 = a0 + a0;
171 6053094 two_product(a1, _0, _k, _1);
172 6053094 two_one_sum(_k, _1, _j, _l, _2, x[1]);
173 6053094 square(a1, _j, _1);
174 6053094 two_two_sum(_j, _1, _l, _2, x[5], x[4], x[3], x[2]);
175 6053094 }
176
177 /**
178 * \brief Computes the product of two expansions of length 2.
179 * \param[in] a first argument (array of 2 doubles)
180 * \param[in] b second argument (array of 2 doubles)
181 * \param[out] x an array of 8 doubles to store the result
182 * \details By Jonathan Shewchuk.
183 */
184 70584156 void two_two_product(
185 const double* a,
186 const double* b,
187 double* x
188 ) {
189 double _0, _1, _2;
190 double _i, _j, _k, _l, _m, _n;
191
192 // If the target processor supports the FMA (Fused Multiply Add)
193 // instruction, then the product of two doubles into a length-2
194 // expansion can be implemented as follows. Thanks to Marc Glisse
195 // for the information.
196 // Note: under gcc, automatic generations of fma() for a*b+c needs
197 // to be deactivated, using -ffp-contract=off, else it may break
198 // other functions such as fast_expansion_sum_zeroelim().
199 #ifdef FP_FAST_FMA
200 70584156 two_product(a[0],b[0],_i,x[0]);
201 70584156 two_product(a[1],b[0],_j,_0);
202 70584156 two_sum(_i, _0, _k, _1);
203 70584156 fast_two_sum(_j, _k, _l, _2);
204 70584156 two_product(a[0], b[1], _i, _0);
205 70584156 two_sum(_1, _0, _k, x[1]);
206 70584156 two_sum(_2, _k, _j, _1);
207 70584156 two_sum(_l, _j, _m, _2);
208 70584156 two_product(a[1], b[1], _j, _0);
209 70584156 two_sum(_i, _0, _n, _0);
210 70584156 two_sum(_1, _0, _i, x[2]);
211 70584156 two_sum(_2, _i, _k, _1);
212 70584156 two_sum(_m, _k, _l, _2);
213 70584156 two_sum(_j, _n, _k, _0);
214 70584156 two_sum(_1, _0, _j, x[3]);
215 70584156 two_sum(_2, _j, _i, _1);
216 70584156 two_sum(_l, _i, _m, _2);
217 70584156 two_sum(_1, _k, _i, x[4]);
218 70584156 two_sum(_2, _i, _k, x[5]);
219 70584156 two_sum(_m, _k, x[7], x[6]);
220 #else
221 double a0hi, a0lo;
222 split(a[0], a0hi, a0lo);
223 double bhi, blo;
224 split(b[0], bhi, blo);
225 two_product_2presplit(
226 a[0], a0hi, a0lo, b[0], bhi, blo, _i, x[0]
227 );
228 double a1hi, a1lo;
229 split(a[1], a1hi, a1lo);
230 two_product_2presplit(
231 a[1], a1hi, a1lo, b[0], bhi, blo, _j, _0
232 );
233 two_sum(_i, _0, _k, _1);
234 fast_two_sum(_j, _k, _l, _2);
235 split(b[1], bhi, blo);
236 two_product_2presplit(
237 a[0], a0hi, a0lo, b[1], bhi, blo, _i, _0
238 );
239 two_sum(_1, _0, _k, x[1]);
240 two_sum(_2, _k, _j, _1);
241 two_sum(_l, _j, _m, _2);
242 two_product_2presplit(
243 a[1], a1hi, a1lo, b[1], bhi, blo, _j, _0
244 );
245 two_sum(_i, _0, _n, _0);
246 two_sum(_1, _0, _i, x[2]);
247 two_sum(_2, _i, _k, _1);
248 two_sum(_m, _k, _l, _2);
249 two_sum(_j, _n, _k, _0);
250 two_sum(_1, _0, _j, x[3]);
251 two_sum(_2, _j, _i, _1);
252 two_sum(_l, _i, _m, _2);
253 two_sum(_1, _k, _i, x[4]);
254 two_sum(_2, _i, _k, x[5]);
255 two_sum(_m, _k, x[7], x[6]);
256 #endif
257 70584156 }
258
259 // [Shewchuk 97]
260 // (https://people.eecs.berkeley.edu/~jrs/papers/robustr.pdf)
261 // Section 2.8: other operations
262 // Compression
263 // Note: when converting the algorithms in Shewchuk's article
264 // into code, indices in the article go from 1 to m, and in the
265 // code they go from 0 to m-1 !!!
266 // /!\ there is a bug in the original article,
267 // line 14 of the algorithm should be h_top <= q (small q and not capital Q)
268
269 /**
270 * \brief Compresses an expansion
271 * \details Modifies in-place an expansion in such a way that it
272 * is shorter. The represented value is not modified.
273 * \param[in,out] e a reference to the expansion to be compressed
274 */
275 2288927 void compress_expansion(expansion& e) {
276 2288927 expansion& h = e;
277
278 2288927 index_t m = e.length();
279 double Qnew,q;
280
281 2288927 index_t bottom = m-1;
282
1/2
✓ Branch 1 taken 2288927 times.
✗ Branch 2 not taken.
 2288927 double Q = e[bottom];
283
284
2/2
✓ Branch 0 taken 3832823 times.
✓ Branch 1 taken 2288927 times.
 6121750 for(int i=int(m)-2; i>=0; --i) {
285
1/2
✓ Branch 1 taken 3832823 times.
✗ Branch 2 not taken.
 3832823 fast_two_sum(Q, e[index_t(i)], Qnew, q);
286 3832823 Q = Qnew;
287
2/2
✓ Branch 0 taken 2424188 times.
✓ Branch 1 taken 1408635 times.
 3832823 if(q != 0.0) {
288
1/2
✓ Branch 1 taken 2424188 times.
✗ Branch 2 not taken.
 2424188 h[bottom] = Q;
289 2424188 --bottom;
290 2424188 Q = q;
291 }
292 }
293
1/2
✓ Branch 1 taken 2288927 times.
✗ Branch 2 not taken.
 2288927 h[bottom] = Q;
294
295 2288927 index_t top = 0;
296
2/2
✓ Branch 0 taken 2424188 times.
✓ Branch 1 taken 2288927 times.
 4713115 for(index_t i=bottom+1; i<m; ++i) {
297
1/2
✓ Branch 1 taken 2424188 times.
✗ Branch 2 not taken.
 2424188 fast_two_sum(h[i],Q,Qnew,q);
298 2424188 Q = Qnew;
299
1/2
✓ Branch 0 taken 2424188 times.
✗ Branch 1 not taken.
 2424188 if(q != 0) {
300
1/2
✓ Branch 1 taken 2424188 times.
✗ Branch 2 not taken.
 2424188 h[top] = q;
301 2424188 ++top;
302 }
303 }
304
1/2
✓ Branch 1 taken 2288927 times.
✗ Branch 2 not taken.
 2288927 h[top] = Q;
305
1/2
✓ Branch 1 taken 2288927 times.
✗ Branch 2 not taken.
 2288927 h.set_length(top+1);
306 2288927 }
307 }
308
309 namespace GEO {
310
311 ✗ void grow_expansion_zeroelim(
312 const expansion& e, double b, expansion& h
313 ) {
314 double Q, hh;
315 double Qnew;
316 index_t eindex, hindex;
317 ✗ index_t elen = e.length();
318
319 ✗ hindex = 0;
320 ✗ Q = b;
321 ✗ for(eindex = 0; eindex < elen; eindex++) {
322 ✗ double enow = e[eindex];
323 ✗ two_sum(Q, enow, Qnew, hh);
324 ✗ Q = Qnew;
325 ✗ if(hh != 0.0) {
326 ✗ h[hindex++] = hh;
327 }
328 }
329 ✗ if((Q != 0.0) || (hindex == 0)) {
330 ✗ h[hindex++] = Q;
331 }
332 ✗ h.set_length(hindex);
333 ✗ }
334
335 45527131 void scale_expansion_zeroelim(
336 const expansion& e, double b, expansion& h
337 ) {
338 double Q, sum;
339 double hh;
340 double product1;
341 double product0;
342 index_t eindex, hindex;
343
344 // If the target processor supports the FMA (Fused Multiply Add)
345 // instruction, then the product of two doubles into a length-2
346 // expansion can be implemented as follows. Thanks to Marc Glisse
347 // for the information.
348 // Note: under gcc, automatic generations of fma() for a*b+c needs
349 // to be deactivated, using -ffp-contract=off, else it may break
350 // other functions such as fast_expansion_sum_zeroelim().
351 #ifndef FP_FAST_FMA
352 double bhi, blo;
353 #endif
354 45527131 index_t elen = e.length();
355
356 // Sanity check: e and h cannot be the same.
357
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 45527131 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 45527131 geo_debug_assert(&e != &h);
358
359 #ifdef FP_FAST_FMA
360
1/2
✓ Branch 1 taken 45527131 times.
✗ Branch 2 not taken.
 45527131 two_product(e[0], b, Q, hh);
361 #else
362 split(b, bhi, blo);
363 two_product_presplit(e[0], b, bhi, blo, Q, hh);
364 #endif
365
366 45527131 hindex = 0;
367
2/2
✓ Branch 0 taken 18665206 times.
✓ Branch 1 taken 26861925 times.
 45527131 if(hh != 0) {
368
1/2
✓ Branch 1 taken 18665206 times.
✗ Branch 2 not taken.
 18665206 h[hindex++] = hh;
369 }
370
2/2
✓ Branch 0 taken 113630741 times.
✓ Branch 1 taken 45527131 times.
 159157872 for(eindex = 1; eindex < elen; eindex++) {
371
1/2
✓ Branch 1 taken 113630741 times.
✗ Branch 2 not taken.
 113630741 double enow = e[eindex];
372 #ifdef FP_FAST_FMA
373 113630741 two_product(enow, b, product1, product0);
374 #else
375 two_product_presplit(enow, b, bhi, blo, product1, product0);
376 #endif
377 113630741 two_sum(Q, product0, sum, hh);
378
2/2
✓ Branch 0 taken 13382004 times.
✓ Branch 1 taken 100248737 times.
 113630741 if(hh != 0) {
379
1/2
✓ Branch 1 taken 13382004 times.
✗ Branch 2 not taken.
 13382004 h[hindex++] = hh;
380 }
381 113630741 fast_two_sum(product1, sum, Q, hh);
382
2/2
✓ Branch 0 taken 85394764 times.
✓ Branch 1 taken 28235977 times.
 113630741 if(hh != 0) {
383
1/2
✓ Branch 1 taken 85394764 times.
✗ Branch 2 not taken.
 85394764 h[hindex++] = hh;
384 }
385 }
386
3/4
✓ Branch 0 taken 15822393 times.
✓ Branch 1 taken 29704738 times.
✓ Branch 2 taken 15822393 times.
✗ Branch 3 not taken.
 45527131 if((Q != 0.0) || (hindex == 0)) {
387
1/2
✓ Branch 1 taken 45527131 times.
✗ Branch 2 not taken.
 45527131 h[hindex++] = Q;
388 }
389
1/2
✓ Branch 1 taken 45527131 times.
✗ Branch 2 not taken.
 45527131 h.set_length(hindex);
390 45527131 }
391
392 43622481 void fast_expansion_sum_zeroelim(
393 const expansion& e, const expansion& f, expansion& h
394 ) {
395 double Q;
396 double Qnew;
397 double hh;
398 index_t eindex, findex, hindex;
399 double enow, fnow;
400 43622481 index_t elen = e.length();
401 43622481 index_t flen = f.length();
402
403 // sanity check: h cannot be e or f
404
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 43622481 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 43622481 geo_debug_assert(&h != &e);
405
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 43622481 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 43622481 geo_debug_assert(&h != &f);
406
407
1/2
✓ Branch 1 taken 43622481 times.
✗ Branch 2 not taken.
 43622481 enow = e[0];
408
1/2
✓ Branch 1 taken 43622481 times.
✗ Branch 2 not taken.
 43622481 fnow = f[0];
409 43622481 eindex = findex = 0;
410
2/2
✓ Branch 0 taken 38733483 times.
✓ Branch 1 taken 4888998 times.
 43622481 if((fnow > enow) == (fnow > -enow)) {
411 38733483 Q = enow;
412
1/2
✓ Branch 1 taken 38733483 times.
✗ Branch 2 not taken.
 38733483 enow = e[++eindex];
413 } else {
414 4888998 Q = fnow;
415
1/2
✓ Branch 1 taken 4888998 times.
✗ Branch 2 not taken.
 4888998 fnow = f[++findex];
416 }
417 43622481 hindex = 0;
418
4/4
✓ Branch 0 taken 31217077 times.
✓ Branch 1 taken 12405404 times.
✓ Branch 2 taken 30371587 times.
✓ Branch 3 taken 845490 times.
 43622481 if((eindex < elen) && (findex < flen)) {
419
2/2
✓ Branch 0 taken 23919828 times.
✓ Branch 1 taken 6451759 times.
 30371587 if((fnow > enow) == (fnow > -enow)) {
420 23919828 fast_two_sum(enow, Q, Qnew, hh);
421
1/2
✓ Branch 1 taken 23919828 times.
✗ Branch 2 not taken.
 23919828 enow = e[++eindex];
422 } else {
423 6451759 fast_two_sum(fnow, Q, Qnew, hh);
424
1/2
✓ Branch 1 taken 6451759 times.
✗ Branch 2 not taken.
 6451759 fnow = f[++findex];
425 }
426 30371587 Q = Qnew;
427
2/2
✓ Branch 0 taken 4777936 times.
✓ Branch 1 taken 25593651 times.
 30371587 if(hh != 0.0) {
428
1/2
✓ Branch 1 taken 4777936 times.
✗ Branch 2 not taken.
 4777936 h[hindex++] = hh;
429 }
430
4/4
✓ Branch 0 taken 269050898 times.
✓ Branch 1 taken 22572066 times.
✓ Branch 2 taken 261251377 times.
✓ Branch 3 taken 7799521 times.
 291622964 while((eindex < elen) && (findex < flen)) {
431
2/2
✓ Branch 0 taken 145169285 times.
✓ Branch 1 taken 116082092 times.
 261251377 if((fnow > enow) == (fnow > -enow)) {
432 145169285 two_sum(Q, enow, Qnew, hh);
433
1/2
✓ Branch 1 taken 145169285 times.
✗ Branch 2 not taken.
 145169285 enow = e[++eindex];
434 } else {
435 116082092 two_sum(Q, fnow, Qnew, hh);
436
1/2
✓ Branch 1 taken 116082092 times.
✗ Branch 2 not taken.
 116082092 fnow = f[++findex];
437 }
438 261251377 Q = Qnew;
439
2/2
✓ Branch 0 taken 124670272 times.
✓ Branch 1 taken 136581105 times.
 261251377 if(hh != 0.0) {
440
1/2
✓ Branch 1 taken 124670272 times.
✗ Branch 2 not taken.
 124670272 h[hindex++] = hh;
441 }
442 }
443 }
444
2/2
✓ Branch 0 taken 11026940 times.
✓ Branch 1 taken 43622481 times.
 54649421 while(eindex < elen) {
445 11026940 two_sum(Q, enow, Qnew, hh);
446
1/2
✓ Branch 1 taken 11026940 times.
✗ Branch 2 not taken.
 11026940 enow = e[++eindex];
447 11026940 Q = Qnew;
448
2/2
✓ Branch 0 taken 3661695 times.
✓ Branch 1 taken 7365245 times.
 11026940 if(hh != 0.0) {
449
1/2
✓ Branch 1 taken 3661695 times.
✗ Branch 2 not taken.
 3661695 h[hindex++] = hh;
450 }
451 }
452
2/2
✓ Branch 0 taken 63524363 times.
✓ Branch 1 taken 43622481 times.
 107146844 while(findex < flen) {
453 63524363 two_sum(Q, fnow, Qnew, hh);
454
1/2
✓ Branch 1 taken 63524363 times.
✗ Branch 2 not taken.
 63524363 fnow = f[++findex];
455 63524363 Q = Qnew;
456
2/2
✓ Branch 0 taken 23342067 times.
✓ Branch 1 taken 40182296 times.
 63524363 if(hh != 0.0) {
457
1/2
✓ Branch 1 taken 23342067 times.
✗ Branch 2 not taken.
 23342067 h[hindex++] = hh;
458 }
459 }
460
4/4
✓ Branch 0 taken 14775223 times.
✓ Branch 1 taken 28847258 times.
✓ Branch 2 taken 14728974 times.
✓ Branch 3 taken 46249 times.
 43622481 if((Q != 0.0) || (hindex == 0)) {
461
1/2
✓ Branch 1 taken 43576232 times.
✗ Branch 2 not taken.
 43576232 h[hindex++] = Q;
462 }
463
1/2
✓ Branch 1 taken 43622481 times.
✗ Branch 2 not taken.
 43622481 h.set_length(hindex);
464 43622481 }
465
466 39607365 void fast_expansion_diff_zeroelim(
467 const expansion& e, const expansion& f, expansion& h
468 ) {
469 double Q;
470 double Qnew;
471 double hh;
472 index_t eindex, findex, hindex;
473 double enow, fnow;
474 39607365 index_t elen = e.length();
475 39607365 index_t flen = f.length();
476
477 // sanity check: h cannot be e or f
478
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 39607365 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 39607365 geo_debug_assert(&h != &e);
479
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 39607365 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 39607365 geo_debug_assert(&h != &f);
480
481
1/2
✓ Branch 1 taken 39607365 times.
✗ Branch 2 not taken.
 39607365 enow = e[0];
482
1/2
✓ Branch 1 taken 39607365 times.
✗ Branch 2 not taken.
 39607365 fnow = -f[0];
483 39607365 eindex = findex = 0;
484
2/2
✓ Branch 0 taken 34746557 times.
✓ Branch 1 taken 4860808 times.
 39607365 if((fnow > enow) == (fnow > -enow)) {
485 34746557 Q = enow;
486
1/2
✓ Branch 1 taken 34746557 times.
✗ Branch 2 not taken.
 34746557 enow = e[++eindex];
487 } else {
488 4860808 Q = fnow;
489
1/2
✓ Branch 1 taken 4860808 times.
✗ Branch 2 not taken.
 4860808 fnow = -f[++findex];
490 }
491 39607365 hindex = 0;
492
4/4
✓ Branch 0 taken 37616029 times.
✓ Branch 1 taken 1991336 times.
✓ Branch 2 taken 36015347 times.
✓ Branch 3 taken 1600682 times.
 39607365 if((eindex < elen) && (findex < flen)) {
493
2/2
✓ Branch 0 taken 32567483 times.
✓ Branch 1 taken 3447864 times.
 36015347 if((fnow > enow) == (fnow > -enow)) {
494 32567483 fast_two_sum(enow, Q, Qnew, hh);
495
1/2
✓ Branch 1 taken 32567483 times.
✗ Branch 2 not taken.
 32567483 enow = e[++eindex];
496 } else {
497 3447864 fast_two_sum(fnow, Q, Qnew, hh);
498
1/2
✓ Branch 1 taken 3447864 times.
✗ Branch 2 not taken.
 3447864 fnow = -f[++findex];
499 }
500 36015347 Q = Qnew;
501
2/2
✓ Branch 0 taken 546911 times.
✓ Branch 1 taken 35468436 times.
 36015347 if(hh != 0.0) {
502
1/2
✓ Branch 1 taken 546911 times.
✗ Branch 2 not taken.
 546911 h[hindex++] = hh;
503 }
504
4/4
✓ Branch 0 taken 333686041 times.
✓ Branch 1 taken 24380799 times.
✓ Branch 2 taken 322051493 times.
✓ Branch 3 taken 11634548 times.
 358066840 while((eindex < elen) && (findex < flen)) {
505
2/2
✓ Branch 0 taken 191714854 times.
✓ Branch 1 taken 130336639 times.
 322051493 if((fnow > enow) == (fnow > -enow)) {
506 191714854 two_sum(Q, enow, Qnew, hh);
507
1/2
✓ Branch 1 taken 191714854 times.
✗ Branch 2 not taken.
 191714854 enow = e[++eindex];
508 } else {
509 130336639 two_sum(Q, fnow, Qnew, hh);
510
1/2
✓ Branch 1 taken 130336639 times.
✗ Branch 2 not taken.
 130336639 fnow = -f[++findex];
511 }
512 322051493 Q = Qnew;
513
2/2
✓ Branch 0 taken 33386493 times.
✓ Branch 1 taken 288665000 times.
 322051493 if(hh != 0.0) {
514
1/2
✓ Branch 1 taken 33386493 times.
✗ Branch 2 not taken.
 33386493 h[hindex++] = hh;
515 }
516 }
517 }
518
2/2
✓ Branch 0 taken 15275060 times.
✓ Branch 1 taken 39607365 times.
 54882425 while(eindex < elen) {
519 15275060 two_sum(Q, enow, Qnew, hh);
520
1/2
✓ Branch 1 taken 15275060 times.
✗ Branch 2 not taken.
 15275060 enow = e[++eindex];
521 15275060 Q = Qnew;
522
2/2
✓ Branch 0 taken 4880540 times.
✓ Branch 1 taken 10394520 times.
 15275060 if(hh != 0.0) {
523
1/2
✓ Branch 1 taken 4880540 times.
✗ Branch 2 not taken.
 4880540 h[hindex++] = hh;
524 }
525 }
526
2/2
✓ Branch 0 taken 135586327 times.
✓ Branch 1 taken 39607365 times.
 175193692 while(findex < flen) {
527 135586327 two_sum(Q, fnow, Qnew, hh);
528
1/2
✓ Branch 1 taken 135586327 times.
✗ Branch 2 not taken.
 135586327 fnow = -f[++findex];
529 135586327 Q = Qnew;
530
2/2
✓ Branch 0 taken 4658930 times.
✓ Branch 1 taken 130927397 times.
 135586327 if(hh != 0.0) {
531
1/2
✓ Branch 1 taken 4658930 times.
✗ Branch 2 not taken.
 4658930 h[hindex++] = hh;
532 }
533 }
534
4/4
✓ Branch 0 taken 16541966 times.
✓ Branch 1 taken 23065399 times.
✓ Branch 2 taken 16512757 times.
✓ Branch 3 taken 29209 times.
 39607365 if((Q != 0.0) || (hindex == 0)) {
535
1/2
✓ Branch 1 taken 39578156 times.
✗ Branch 2 not taken.
 39578156 h[hindex++] = Q;
536 }
537
1/2
✓ Branch 1 taken 39607365 times.
✗ Branch 2 not taken.
 39607365 h.set_length(hindex);
538 39607365 }
539
540 }
541
542 /****************************************************************************/
543
544 namespace GEO {
545
546 double expansion_splitter_;
547 double expansion_epsilon_;
548 bool expansion_initialized_ = false;
549
550 257 void expansion::initialize() {
551 // Taken from Jonathan Shewchuk's exactinit.
552 double half;
553 double check, lastcheck;
554 int every_other;
555
556 257 every_other = 1;
557 257 half = 0.5;
558 257 expansion_epsilon_ = 1.0;
559 257 expansion_splitter_ = 1.0;
560 257 check = 1.0;
561 // Repeatedly divide `epsilon' by two until it is too small to add to
562 // one without causing roundoff. (Also check if the sum is equal to
563 // the previous sum, for machines that round up instead of using exact
564 // rounding. Not that this library will work on such machines anyway.
565 do {
566 13621 lastcheck = check;
567 13621 expansion_epsilon_ *= half;
568
2/2
✓ Branch 0 taken 6939 times.
✓ Branch 1 taken 6682 times.
 13621 if(every_other) {
569 6939 expansion_splitter_ *= 2.0;
570 }
571 13621 every_other = !every_other;
572 13621 check = 1.0 + expansion_epsilon_;
573
3/4
✓ Branch 0 taken 13364 times.
✓ Branch 1 taken 257 times.
✓ Branch 2 taken 13364 times.
✗ Branch 3 not taken.
 13621 } while((check != 1.0) && (check != lastcheck));
574 257 expansion_splitter_ += 1.0;
575 257 expansion_initialized_ = true;
576 257 }
577
578 // ====== Initialization from expansion and double ===============
579
580 ✗ expansion& expansion::assign_sum(const expansion& a, double b) {
581 ✗ geo_debug_assert(capacity() >= sum_capacity(a, b));
582 ✗ grow_expansion_zeroelim(a, b, *this);
583 ✗ return *this;
584 }
585
586 ✗ expansion& expansion::assign_diff(const expansion& a, double b) {
587 ✗ geo_debug_assert(capacity() >= diff_capacity(a, b));
588 ✗ grow_expansion_zeroelim(a, -b, *this);
589 ✗ return *this;
590 }
591
592 29151582 expansion& expansion::assign_product(const expansion& a, double b) {
593 // TODO: implement special case where the double argument
594 // is a power of two.
595
1/6
✗ Branch 2 not taken.
✓ Branch 3 taken 29151582 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 29151582 geo_debug_assert(capacity() >= product_capacity(a, b));
596 29151582 scale_expansion_zeroelim(a, b, *this);
597 29151582 return *this;
598 }
599
600 // ============= expansion sum and difference =========================
601
602 43622481 expansion& expansion::assign_sum(
603 const expansion& a, const expansion& b
604 ) {
605
1/6
✗ Branch 2 not taken.
✓ Branch 3 taken 43622481 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 43622481 geo_debug_assert(capacity() >= sum_capacity(a, b));
606 43622481 fast_expansion_sum_zeroelim(a, b, *this);
607 43622481 return *this;
608 }
609
610 8015274 expansion& expansion::assign_sum(
611 const expansion& a, const expansion& b, const expansion& c
612 ) {
613
1/6
✗ Branch 2 not taken.
✓ Branch 3 taken 8015274 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 8015274 geo_debug_assert(capacity() >= sum_capacity(a, b, c));
614
2/6
✓ Branch 6 taken 8015274 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 8015274 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
 8015274 expansion& ab = expansion_sum(a, b);
615 8015274 this->assign_sum(ab, c);
616 8015274 return *this;
617 }
618
619 374418 expansion& expansion::assign_sum(
620 const expansion& a, const expansion& b,
621 const expansion& c, const expansion& d
622 ) {
623
1/6
✗ Branch 2 not taken.
✓ Branch 3 taken 374418 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 374418 geo_debug_assert(capacity() >= sum_capacity(a, b, c));
624
2/6
✓ Branch 6 taken 374418 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 374418 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
 374418 expansion& ab = expansion_sum(a, b);
625
2/6
✓ Branch 6 taken 374418 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 374418 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
 374418 expansion& cd = expansion_sum(c, d);
626 374418 this->assign_sum(ab, cd);
627 374418 return *this;
628 }
629
630 39607365 expansion& expansion::assign_diff(const expansion& a, const expansion& b) {
631
1/6
✗ Branch 2 not taken.
✓ Branch 3 taken 39607365 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 39607365 geo_debug_assert(capacity() >= diff_capacity(a, b));
632 39607365 fast_expansion_diff_zeroelim(a, b, *this);
633 39607365 return *this;
634 }
635
636 // ============= expansion product ==================================
637
638 // Recursive helper function for product implementation
639 67251 expansion& expansion::assign_sub_product(
640 const double* a, index_t a_length, const expansion& b
641 ) {
642
1/6
✗ Branch 3 not taken.
✓ Branch 4 taken 67251 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 67251 geo_debug_assert(
643 capacity() >= sub_product_capacity(a_length, b.length())
644 );
645
2/2
✓ Branch 0 taken 34513 times.
✓ Branch 1 taken 32738 times.
 67251 if(a_length == 1) {
646 34513 scale_expansion_zeroelim(b, a[0], *this);
647 } else {
648 // "Distillation" (see Shewchuk's paper) is computed recursively,
649 // by splitting the list of expansions to sum into two halves.
650
651 32738 const double* a1 = a;
652 32738 index_t a1_length = a_length / 2;
653 32738 const double* a2 = a1 + a1_length;
654 32738 index_t a2_length = a_length - a1_length;
655
656 // Allocate both halves on the stack or on the heap if too large
657 // (some platformes, e.g. MacOSX, have a small stack)
658
659 32738 index_t a1b_capa = sub_product_capacity(a1_length, b.length());
660 32738 index_t a2b_capa = sub_product_capacity(a2_length, b.length());
661
662 32738 bool a1b_on_heap = (a1b_capa > MAX_CAPACITY_ON_STACK);
663 32738 bool a2b_on_heap = (a2b_capa > MAX_CAPACITY_ON_STACK);
664
665 32738 expansion* a1b = a1b_on_heap ?
666 18 new_expansion_on_heap(a1b_capa) :
667
5/6
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 32720 times.
✓ Branch 5 taken 32720 times.
✓ Branch 6 taken 18 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 32720 times.
 32756 new_expansion_on_stack(a1b_capa);
668
669 32738 a1b->assign_sub_product(a1, a1_length, b);
670
671 32738 expansion* a2b = a2b_on_heap ?
672 25 new_expansion_on_heap(a2b_capa) :
673
5/6
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 32713 times.
✓ Branch 5 taken 32713 times.
✓ Branch 6 taken 25 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 32713 times.
 32763 new_expansion_on_stack(a2b_capa);
674
675 32738 a2b->assign_sub_product(a2, a2_length, b);
676
677 32738 this->assign_sum(*a1b, *a2b);
678
679
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 32720 times.
 32738 if(a1b_on_heap) {
680 18 delete_expansion_on_heap(a1b);
681 }
682
683
2/2
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 32713 times.
 32738 if(a2b_on_heap) {
684 25 delete_expansion_on_heap(a2b);
685 }
686 }
687 67251 return *this;
688 }
689
690 96295247 expansion& expansion::assign_product(
691 const expansion& a, const expansion& b
692 ) {
693
1/6
✗ Branch 2 not taken.
✓ Branch 3 taken 96295247 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 96295247 geo_debug_assert(capacity() >= product_capacity(a, b));
694
3/6
✓ Branch 1 taken 96295247 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 96295247 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 96295247 times.
 96295247 if(a.length() == 0 || b.length() == 0) {
695 ✗ x_[0] = 0.0;
696 ✗ set_length(0);
697
6/6
✓ Branch 1 taken 6550499 times.
✓ Branch 2 taken 89744748 times.
✓ Branch 4 taken 4571799 times.
✓ Branch 5 taken 1978700 times.
✓ Branch 6 taken 4571799 times.
✓ Branch 7 taken 91723448 times.
 96295247 } else if(a.length() == 1 && b.length() == 1) {
698 4571799 two_product(a[0], b[0], x_[1], x_[0]);
699 4571799 set_length(2);
700
2/2
✓ Branch 1 taken 1978700 times.
✓ Branch 2 taken 89744748 times.
 91723448 } else if(a.length() == 1) {
701 1978700 scale_expansion_zeroelim(b, a[0], *this);
702
2/2
✓ Branch 1 taken 14362336 times.
✓ Branch 2 taken 75382412 times.
 89744748 } else if(b.length() == 1) {
703 14362336 scale_expansion_zeroelim(a, b[0], *this);
704
6/6
✓ Branch 1 taken 68507715 times.
✓ Branch 2 taken 6874697 times.
✓ Branch 4 taken 64427559 times.
✓ Branch 5 taken 4080156 times.
✓ Branch 6 taken 64427559 times.
✓ Branch 7 taken 10954853 times.
 75382412 } else if(a.length() == 2 && b.length() == 2) {
705 64427559 two_two_product(a.data(), b.data(), x_);
706 64427559 set_length(8);
707 } else {
708
709
710 10954853 const expansion* pa = &a;
711 10954853 const expansion* pb = &b;
712
713
2/2
✓ Branch 2 taken 3270147 times.
✓ Branch 3 taken 7684706 times.
 10954853 if(pa->length() > pb->length()) {
714 3270147 std::swap(pa, pb);
715 }
716
717 // [Shewchuk 97]
718 // (https://people.eecs.berkeley.edu/~jrs/papers/robustr.pdf)
719 // Section 2.8: other operations
720 // Distillation: sum of k values.
721 // Worst case: 1/2*k*(k-1)
722 // But O(k log(k)) if the "summing tree" is well balanced
723 // and using fast_expansion_sum().
724 // Recommended way of computing a product:
725 // compute a1*b, a2*b ... ak*b using scale_expansion_zeroelim()
726 // sum them using a well-balanced tree
727 // However, there is an extra cost for the recursion (and more
728 // importantly, for allocating the intermediary sums, especially
729 // when they do not fit on the stack). So when there are less than
730 // 16 values to add, we simply accumulate them.
731
732 10954853 bool use_balanced_distillation = (pa->length() >= 16);
733
734
2/2
✓ Branch 0 taken 1775 times.
✓ Branch 1 taken 10953078 times.
 10954853 if(use_balanced_distillation) {
735 // assign_sub_product() is a recursive function that
736 // creates a balanced distillation tree on the stack.
737
1/2
✓ Branch 3 taken 1775 times.
✗ Branch 4 not taken.
 1775 assign_sub_product(pa->data(), pa->length(),*pb);
738 } else {
739 // trivial implementation: compute all the products
740 // P = ak*b and accumulate them into S
741
742
1/2
✓ Branch 1 taken 10953078 times.
✗ Branch 2 not taken.
 10953078 index_t P_capa = product_capacity(*pb, 3.0); // 3.0, or any
743 // number that is
744 // not a power of 2
745
746 10953078 index_t S_capa = capacity(); // same capacity as this,
747 // enough to store sum.
748
749 10953078 bool P_on_heap = (P_capa > MAX_CAPACITY_ON_STACK);
750 10953078 bool S_on_heap = (S_capa > MAX_CAPACITY_ON_STACK);
751
752 10953078 expansion* P = P_on_heap ?
753 ✗ new_expansion_on_heap(P_capa) :
754
3/6
✗ Branch 0 not taken.
✓ Branch 1 taken 10953078 times.
✓ Branch 5 taken 10953078 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 10953078 times.
 10953078 new_expansion_on_stack(P_capa);
755
756 10953078 expansion* S = S_on_heap ?
757 1 new_expansion_on_heap(S_capa) :
758
5/6
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 10953077 times.
✓ Branch 5 taken 10953077 times.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 10953077 times.
 10953079 new_expansion_on_stack(S_capa);
759
760 10953078 expansion* S1 = S;
761 10953078 expansion* S2 = this;
762
763
2/2
✓ Branch 1 taken 6782850 times.
✓ Branch 2 taken 4170228 times.
 10953078 if((pa->length()%2) == 0) {
764 6782850 std::swap(S1,S2);
765 }
766
767
2/2
✓ Branch 1 taken 27814956 times.
✓ Branch 2 taken 10953078 times.
 38768034 for(index_t i=0; i<pa->length(); ++i) {
768
2/2
✓ Branch 0 taken 10953078 times.
✓ Branch 1 taken 16861878 times.
 27814956 if(i == 0) {
769
2/4
✓ Branch 1 taken 10953078 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 10953078 times.
✗ Branch 5 not taken.
 10953078 S2->assign_product(*pb, (*pa)[i]);
770 } else {
771
2/4
✓ Branch 1 taken 16861878 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 16861878 times.
✗ Branch 5 not taken.
 16861878 P->assign_product(*pb, (*pa)[i]);
772
1/2
✓ Branch 1 taken 16861878 times.
✗ Branch 2 not taken.
 16861878 S2->assign_sum(*S1,*P);
773 }
774 27814956 std::swap(S1,S2);
775 }
776
777
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 10953078 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 10953078 geo_assert(S1 == this);
778
779
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 10953077 times.
 10953078 if(S_on_heap) {
780 1 delete_expansion_on_heap(S);
781 }
782
783
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10953078 times.
 10953078 if(P_on_heap) {
784 ✗ delete_expansion_on_heap(P);
785 }
786 }
787 }
788 96295247 return *this;
789 }
790
791 ✗ expansion& expansion::assign_product(
792 const expansion& a, const expansion& b, const expansion& c
793 ) {
794 ✗ const expansion& bc = expansion_product(b, c);
795 ✗ this->assign_product(a, bc);
796 ✗ return *this;
797 }
798
799 ✗ expansion& expansion::assign_square(const expansion& a) {
800 ✗ geo_debug_assert(capacity() >= square_capacity(a));
801 ✗ if(a.length() == 1) {
802 ✗ square(a[0], x_[1], x_[0]);
803 ✗ set_length(2);
804 ✗ } else if(a.length() == 2) {
805 ✗ two_square(a[1], a[0], x_);
806 ✗ set_length(6);
807 } else {
808 ✗ this->assign_product(a, a);
809 }
810 ✗ return *this;
811 }
812
813 // ============= determinants ==========================================
814
815 33163479 expansion& expansion::assign_det2x2(
816 const expansion& a11, const expansion& a12,
817 const expansion& a21, const expansion& a22
818 ) {
819
2/6
✓ Branch 6 taken 33163479 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 33163479 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
 33163479 const expansion& a11a22 = expansion_product(a11, a22);
820
2/6
✓ Branch 6 taken 33163479 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 33163479 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
 33163479 const expansion& a12a21 = expansion_product(a12, a21);
821 33163479 return this->assign_diff(a11a22, a12a21);
822 }
823
824 6003552 expansion& expansion::assign_det3x3(
825 const expansion& a11, const expansion& a12, const expansion& a13,
826 const expansion& a21, const expansion& a22, const expansion& a23,
827 const expansion& a31, const expansion& a32, const expansion& a33
828 ) {
829 // Development w.r.t. first row
830
2/6
✓ Branch 6 taken 6003552 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 6003552 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
 6003552 const expansion& c11 = expansion_det2x2(a22, a23, a32, a33);
831
2/6
✓ Branch 6 taken 6003552 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 6003552 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
 6003552 const expansion& c12 = expansion_det2x2(a23, a21, a33, a31);
832
2/6
✓ Branch 6 taken 6003552 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 6003552 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
 6003552 const expansion& c13 = expansion_det2x2(a21, a22, a31, a32);
833
2/6
✓ Branch 6 taken 6003552 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 6003552 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
 6003552 const expansion& a11c11 = expansion_product(a11, c11);
834
2/6
✓ Branch 6 taken 6003552 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 6003552 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
 6003552 const expansion& a12c12 = expansion_product(a12, c12);
835
2/6
✓ Branch 6 taken 6003552 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 6003552 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
 6003552 const expansion& a13c13 = expansion_product(a13, c13);
836 6003552 return this->assign_sum(a11c11, a12c12, a13c13);
837 }
838
839 ✗ expansion& expansion::assign_det_111_2x3(
840 const expansion& a21, const expansion& a22, const expansion& a23,
841 const expansion& a31, const expansion& a32, const expansion& a33
842 ) {
843 ✗ const expansion& c11 = expansion_det2x2(a22, a23, a32, a33);
844 ✗ const expansion& c12 = expansion_det2x2(a23, a21, a33, a31);
845 ✗ const expansion& c13 = expansion_det2x2(a21, a22, a31, a32);
846 ✗ return this->assign_sum(c11, c12, c13);
847 }
848
849 // ============= geometric operations ==================================
850
851 10088462 expansion& expansion::assign_sq_dist(
852 const double* p1, const double* p2, coord_index_t dim
853 ) {
854
1/6
✗ Branch 2 not taken.
✓ Branch 3 taken 10088462 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 10088462 geo_debug_assert(capacity() >= sq_dist_capacity(dim));
855
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 10088462 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 10088462 geo_debug_assert(dim > 0);
856
2/2
✓ Branch 0 taken 6053094 times.
✓ Branch 1 taken 4035368 times.
 10088462 if(dim == 1) {
857 double d0, d1;
858 6053094 two_diff(p1[0], p2[0], d1, d0);
859 6053094 two_square(d1, d0, x_);
860
1/2
✓ Branch 1 taken 6053094 times.
✗ Branch 2 not taken.
 6053094 set_length(6);
861 } else {
862 // "Distillation" (see Shewchuk's paper) is computed recursively,
863 // by splitting the list of expansions to sum into two halves.
864 4035368 coord_index_t dim1 = dim / 2;
865 4035368 coord_index_t dim2 = coord_index_t(dim - dim1);
866 4035368 const double* p1_2 = p1 + dim1;
867 4035368 const double* p2_2 = p2 + dim1;
868
2/6
✓ Branch 6 taken 4035368 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 4035368 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
 4035368 expansion& d1 = expansion_sq_dist(p1, p2, dim1);
869
2/6
✓ Branch 6 taken 4035368 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 4035368 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
 4035368 expansion& d2 = expansion_sq_dist(p1_2, p2_2, dim2);
870 4035368 this->assign_sum(d1, d2);
871 }
872 10088462 return *this;
873 }
874
875 10260911 expansion& expansion::assign_dot_at(
876 const double* p1, const double* p2, const double* p0,
877 coord_index_t dim
878 ) {
879
1/6
✗ Branch 2 not taken.
✓ Branch 3 taken 10260911 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 10260911 geo_debug_assert(capacity() >= dot_at_capacity(dim));
880
2/2
✓ Branch 0 taken 6156597 times.
✓ Branch 1 taken 4104314 times.
 10260911 if(dim == 1) {
881
882 double v[2];
883 6156597 two_diff(p1[0], p0[0], v[1], v[0]);
884 double w[2];
885 6156597 two_diff(p2[0], p0[0], w[1], w[0]);
886 6156597 two_two_product(v, w, x_);
887
1/2
✓ Branch 1 taken 6156597 times.
✗ Branch 2 not taken.
 6156597 set_length(8);
888 } else {
889 // "Distillation" (see Shewchuk's paper) is computed recursively,
890 // by splitting the list of expansions to sum into two halves.
891 4104314 coord_index_t dim1 = dim / 2;
892 4104314 coord_index_t dim2 = coord_index_t(dim - dim1);
893 4104314 const double* p1_2 = p1 + dim1;
894 4104314 const double* p2_2 = p2 + dim1;
895 4104314 const double* p0_2 = p0 + dim1;
896
2/6
✓ Branch 6 taken 4104314 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 4104314 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
 4104314 expansion& d1 = expansion_dot_at(p1, p2, p0, dim1);
897
2/6
✓ Branch 6 taken 4104314 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 4104314 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
 4104314 expansion& d2 = expansion_dot_at(p1_2, p2_2, p0_2, dim2);
898 4104314 this->assign_sum(d1, d2);
899 }
900 10260911 return *this;
901 }
902
903 ✗ expansion& expansion::assign_length2(
904 const expansion& x, const expansion& y, const expansion& z
905 ) {
906 ✗ const expansion& x2 = expansion_square(x);
907 ✗ const expansion& y2 = expansion_square(y);
908 ✗ const expansion& z2 = expansion_square(z);
909 ✗ this->assign_sum(x2,y2,z2);
910 ✗ return *this;
911 }
912
913 /************************************************************************/
914
915 1556938 bool expansion::is_same_as(const expansion& rhs) const {
916
2/2
✓ Branch 2 taken 403772 times.
✓ Branch 3 taken 1153166 times.
 1556938 if(length() != rhs.length()) {
917 403772 return false;
918 }
919
2/2
✓ Branch 1 taken 1387061 times.
✓ Branch 2 taken 745205 times.
 2132266 for(index_t i=0; i<length(); ++i) {
920
2/2
✓ Branch 0 taken 407961 times.
✓ Branch 1 taken 979100 times.
 1387061 if(x_[i] != rhs.x_[i]) {
921 407961 return false;
922 }
923 }
924 745205 return true;
925 }
926
927 ✗ bool expansion::is_same_as(double rhs) const {
928 ✗ if(length() != 1) {
929 ✗ return false;
930 }
931 ✗ return (x_[0] == rhs);
932 }
933
934 4225102 Sign expansion::compare(const expansion& rhs) const {
935 // Fast path: different signs or both zero
936 4225102 Sign s1 = sign();
937 4225102 Sign s2 = rhs.sign();
938
4/4
✓ Branch 0 taken 1514102 times.
✓ Branch 1 taken 2711000 times.
✓ Branch 2 taken 492588 times.
✓ Branch 3 taken 1021514 times.
 4225102 if(s1 == ZERO && s2 == ZERO) {
939 492588 return ZERO;
940 }
941
2/2
✓ Branch 0 taken 2175576 times.
✓ Branch 1 taken 1556938 times.
 3732514 if(s1 != s2) {
942
2/2
✓ Branch 0 taken 734057 times.
✓ Branch 1 taken 1441519 times.
 2175576 return (int(s1) > int(s2) ? POSITIVE : NEGATIVE);
943 }
944
945 // Fast path: same internal representation
946
2/2
✓ Branch 1 taken 745205 times.
✓ Branch 2 taken 811733 times.
 1556938 if(is_same_as(rhs)) {
947 745205 return ZERO;
948 }
949
950 // Compute difference and return sign of difference
951 811733 index_t capa = diff_capacity(*this, rhs);
952
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 811733 times.
 811733 if(capa > MAX_CAPACITY_ON_STACK) {
953 ✗ expansion* d = new_expansion_on_heap(capa);
954 ✗ d->assign_diff(*this, rhs);
955 ✗ Sign result = d->sign();
956 ✗ delete_expansion_on_heap(d);
957 ✗ return result;
958 }
959
2/6
✓ Branch 6 taken 811733 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 811733 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
 811733 const expansion& d = expansion_diff(*this, rhs);
960 811733 return d.sign();
961 }
962
963 ✗ Sign expansion::compare(double rhs) const {
964 // Fast path: different signs or both zero
965 ✗ Sign s1 = sign();
966 ✗ Sign s2 = geo_sgn(rhs);
967 ✗ if(s1 == ZERO && s2 == ZERO) {
968 ✗ return ZERO;
969 }
970 ✗ if(s1 != s2) {
971 ✗ return (int(s1) > int(s2) ? POSITIVE : NEGATIVE);
972 }
973
974 // Fast path: same internal representation
975 ✗ if(is_same_as(rhs)) {
976 ✗ return ZERO;
977 }
978
979 // Compute difference and return sign of difference
980 ✗ index_t capa = diff_capacity(*this, rhs);
981 ✗ if(capa > MAX_CAPACITY_ON_STACK) {
982 ✗ expansion* d = new_expansion_on_heap(capa);
983 ✗ d->assign_diff(*this, rhs);
984 ✗ Sign result = d->sign();
985 ✗ delete_expansion_on_heap(d);
986 ✗ return result;
987 }
988 ✗ const expansion& d = expansion_diff(*this, rhs);
989 ✗ return d.sign();
990 }
991
992
993 /************************************************************************/
994
995 ✗ void expansion::show_all_stats() {
996 #ifdef PCK_STATS
997 // Place holder: if we compute statistics for expansions,
998 // the code here will be called if sys:stats is specified
999 // on command line.
1000 #endif
1001 ✗ }
1002
1003 /************************************************************************/
1004
1005 ✗ Sign sign_of_expansion_determinant(
1006 const expansion& a00,const expansion& a01,
1007 const expansion& a10,const expansion& a11
1008 ) {
1009 ✗ const expansion& result = expansion_det2x2(a00, a01, a10, a11);
1010 ✗ return result.sign();
1011 }
1012
1013 ✗ Sign sign_of_expansion_determinant(
1014 const expansion& a00,const expansion& a01,const expansion& a02,
1015 const expansion& a10,const expansion& a11,const expansion& a12,
1016 const expansion& a20,const expansion& a21,const expansion& a22
1017 ) {
1018 // First compute the det2x2
1019 const expansion& m01 =
1020 ✗ expansion_det2x2(a00, a10, a01, a11);
1021 const expansion& m02 =
1022 ✗ expansion_det2x2(a00, a20, a01, a21);
1023 const expansion& m12 =
1024 ✗ expansion_det2x2(a10, a20, a11, a21);
1025
1026 // Now compute the minors of rank 3
1027 ✗ const expansion& z1 = expansion_product(m01,a22);
1028 ✗ const expansion& z2 = expansion_product(m02,a12).negate();
1029 ✗ const expansion& z3 = expansion_product(m12,a02);
1030
1031 ✗ const expansion& result = expansion_sum3(z1,z2,z3);
1032 ✗ return result.sign();
1033 }
1034
1035 ✗ Sign sign_of_expansion_determinant(
1036 const expansion& a00,const expansion& a01,
1037 const expansion& a02,const expansion& a03,
1038 const expansion& a10,const expansion& a11,
1039 const expansion& a12,const expansion& a13,
1040 const expansion& a20,const expansion& a21,
1041 const expansion& a22,const expansion& a23,
1042 const expansion& a30,const expansion& a31,
1043 const expansion& a32,const expansion& a33
1044 ) {
1045
1046 // First compute the det2x2
1047 const expansion& m01 =
1048 ✗ expansion_det2x2(a10,a00,a11,a01);
1049 const expansion& m02 =
1050 ✗ expansion_det2x2(a20,a00,a21,a01);
1051 const expansion& m03 =
1052 ✗ expansion_det2x2(a30,a00,a31,a01);
1053 const expansion& m12 =
1054 ✗ expansion_det2x2(a20,a10,a21,a11);
1055 const expansion& m13 =
1056 ✗ expansion_det2x2(a30,a10,a31,a11);
1057 const expansion& m23 =
1058 ✗ expansion_det2x2(a30,a20,a31,a21);
1059
1060 // Now compute the minors of rank 3
1061 ✗ const expansion& m012_1 = expansion_product(m12,a02);
1062 ✗ expansion& m012_2 = expansion_product(m02,a12); m012_2.negate();
1063 ✗ const expansion& m012_3 = expansion_product(m01,a22);
1064 ✗ const expansion& m012 = expansion_sum3(m012_1, m012_2, m012_3);
1065
1066 ✗ const expansion& m013_1 = expansion_product(m13,a02);
1067 ✗ expansion& m013_2 = expansion_product(m03,a12); m013_2.negate();
1068
1069 ✗ const expansion& m013_3 = expansion_product(m01,a32);
1070 ✗ const expansion& m013 = expansion_sum3(m013_1, m013_2, m013_3);
1071
1072 ✗ const expansion& m023_1 = expansion_product(m23,a02);
1073 ✗ expansion& m023_2 = expansion_product(m03,a22); m023_2.negate();
1074 ✗ const expansion& m023_3 = expansion_product(m02,a32);
1075 ✗ const expansion& m023 = expansion_sum3(m023_1, m023_2, m023_3);
1076
1077 ✗ const expansion& m123_1 = expansion_product(m23,a12);
1078 ✗ expansion& m123_2 = expansion_product(m13,a22); m123_2.negate();
1079 ✗ const expansion& m123_3 = expansion_product(m12,a32);
1080 ✗ const expansion& m123 = expansion_sum3(m123_1, m123_2, m123_3);
1081
1082 // Now compute the minors of rank 4
1083 ✗ const expansion& m0123_1 = expansion_product(m123,a03);
1084 ✗ const expansion& m0123_2 = expansion_product(m023,a13);
1085 ✗ const expansion& m0123_3 = expansion_product(m013,a23);
1086 ✗ const expansion& m0123_4 = expansion_product(m012,a33);
1087
1088 ✗ const expansion& z1 = expansion_sum(m0123_1, m0123_3);
1089 ✗ const expansion& z2 = expansion_sum(m0123_2, m0123_4);
1090
1091 ✗ const expansion& result = expansion_diff(z1,z2);
1092 ✗ return result.sign();
1093 }
1094
1095 /************************************************************************/
1096
1097 2288927 void expansion::optimize() {
1098 2288927 compress_expansion(*this);
1099 2288927 }
1100
1101 /************************************************************************/
1102
1103 }
1104