-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathbugs.html
606 lines (590 loc) · 23.7 KB
/
bugs.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
<html>
<head>
<link rel="stylesheet" type="text/css" href="regina.css">
<title>Regina - Past Important Bugs</title>
</head>
<body bgcolor="#FFFFFF" text="#000000"
link="#0000EE" vlink="#551A8B" alink="#FF0000">
<h1><a name="contents">Regina - Past Important Bugs</a></h1>
<p>
<table class="contentswrapper" cellspacing=0>
<tbody>
<tr><td valign="top">
<table class="contents" cellspacing=0><tbody>
<tr><td><a href="#surfacecomp">Splitting disconnected normal surfaces into
connected components (Jul 2023)</a></td></tr>
<tr><td><a href="#tritetlinks">Identifying normalised (but not
thin) triangle/tetrahedron linking surfaces (Jun 2023)</a></td></tr>
<tr><td><a href="#homgroup">Incorrect simplification of group
homomorphisms (Mar 2023)</a></td></tr>
<tr><td><a href="#bindings">Two Python binding errors (Oct 2022)</a></td></tr>
<tr><td><a href="#defaultalg">Normal surface enumeration ignores
arguments (Sep 2016)</a></td></tr>
<tr><td><a href="#mod">Mod and gcd broken for extremely large integers
(Nov 2013)</a></td></tr>
<tr><td><a href="index.html">Back to main page ...</a></td></tr>
</tbody></table>
</td></tr>
</tbody>
</table>
<p>
This page lists some important bugs that appeared in previous versions
of Regina, which might have affected your computations.
<p>
Please write to the developers if you need further information or
assistance.
<h2><a name="surfacecomp">Splitting disconnected normal surfaces into
connected components (Jul 2023)</a></h2>
<h3>Summary</h3>
<table cellspacing=0 border=0 class="data">
<tbody>
<tr>
<td class="topsubheading">Affected versions</td>
<td class="top">7.0–7.3</td>
<td class="top">Fixed in version 7.4 (expected late 2023)</td>
</tr>
<tr>
<td class="subheading">Main symptom</td>
<td> </td>
<td>In C++/Python, if the connectness of a normal surface <tt>s</tt> has
already been computed, then <tt>s.components()</tt> would return the entire
surface as a single component.</td>
</tr>
<tr>
<td class="subheading">Affected users</td>
<td>C++/Python programmers only</td>
<td>This only affected C++/Python users who called
<tt>NormalSurface::components()</tt> on a disconnected surface, <i>after</i>
some routine that computes connectedness for that same surface.</td>
</tr>
<tr>
<td class="subheading">Was I affected?</td>
<td> </td>
<td>Examine your code, and see if it calls <tt>s.components()</tt>
<i>after</i> any of <tt>s.isConnected()</tt>, <tt>s.isOrientable()</tt>,
<tt>s.isTwoSided()</tt> or <tt>s.components()</tt> for some
normal surface <tt>s</tt> which could be disconnected.</td>
</tr>
</table>
<p>
<h3>Details</h3>
<p>
Only C++/Python programmers were affected by this issue.
</p>
<p>
The bug did <i>not</i> affect:
<ul>
<li>the graphical user interface;</li>
<li>disjointness testing (which uses <tt>components()</tt> in its
implementation, but in a way that did not trigger this bug);</li>
<li>vertex and/or fundamental normal surfaces (which are always connected,
and therefore did not trigger this bug).</li>
</ul>
</p>
<p>
Essentially, to trigger this bug, you would have needed to create your own
normal surfaces in C++/Python code (e.g., by forming sums of vertex and/or
fundamental surfaces), and then call the specific routines in the specific
order as described above.
</p>
<p>
A workaround (if you are using Regina 7.0–7.3) is, instead of
calling <tt>s.components()</tt>, to call <tt>(s*1).components()</tt>.
This has the effect of creating a new surface whose connectedness is not yet
known (which means the bug is not triggered).
</p>
<p>
<i><a href="#contents">(Back to top...)</a></i>
<h2><a name="tritetlinks">Identifying normalised (but not thin)
triangle/tetrahedron linking surfaces (Jun 2023)</a></h2>
<h3>Summary</h3>
<table cellspacing=0 border=0 class="data">
<tbody>
<tr>
<td class="topsubheading">Affected versions</td>
<td class="top">7.1–7.3</td>
<td class="top">Fixed in version 7.4 (expected late 2023)</td>
</tr>
<tr>
<td class="subheading">Main symptom</td>
<td> </td>
<td>In C++/Python, calling <tt>isThinTriangleLink()</tt> before
<tt>isNormalTriangleLink()</tt> could make the latter routine answer
incorrectly; likewise for tetrahedron links.</td>
</tr>
<tr>
<td class="subheading">Affected users</td>
<td>C++/Python programmers only</td>
<td>This only affected C++/Python users who called
<tt>isThinTriangleLink()</tt> and <i>then</i>
<tt>isNormalTriangleLink()</tt>, or <tt>isThinTetrahedronLink()</tt> and
then <tt>isNormalTetrahedronLink()</tt>, on the same
normal surface/hypersurface.</td>
</tr>
<tr>
<td class="subheading">Was I affected?</td>
<td> </td>
<td>Examine your code, and see if it tests for <i>both</i>
thin and normalised triangle/tetrahedron links on the same
surface/hypersurface, with the thin test appearing first.</td>
</tr>
</table>
<p>
<h3>Details</h3>
<p>
Only C++/Python programmers were affected by this issue: the bug did not
appear in the graphical user interface.
</p>
<p>
The bug only affected (i) triangle links in normal surfaces, and
(ii) triangle and tetrahedron links in normal hypersurfaces.
It did not affect vertex or edge link tests at all.
</p>
<p>
The bug only affected surface/hypersurfaces <i>s</i> that are
normalised but <i>not thin</i> triangle/tetrahedron links:
</p>
<ul>
<li>The symptom was that, if the thin link test was performed on <i>s</i>
first, before the corresponding normalised link test had been performed,
then any subsequent call to the normalised test on <i>s</i> would return an
empty list (i.e., it would incorrectly report that <i>s</i> is <i>not</i> a
normalised triangle/tetrahedron link).</li>
<li>The cause was essentially an over-aggressive caching of results:
the thin link test would “remember” a boolean existence result,
and then reuse it for both the thin and normalised link tests.
However, a “no” for the thin test should not imply a
“no” for the corresponding normalised test.</li>
</ul>
</p>
<p>
A workaround (if you are using Regina 7.1–7.3) is to simply call
the normalised link test before the thin link test. Subsequent calls to
<i>either</i> test on the same surface will then return the correct results.
</p>
<p>
<i><a href="#contents">(Back to top...)</a></i>
<h2><a name="homgroup">Incorrect simplification of group
homomorphisms (Mar 2023)</a></h2>
<p>
There are two issues here: the first issue was the bug itself, and the
second issue was the only other place where the affected code was being used
within Regina.
</p>
<h3>Summary</h3>
<table cellspacing=0 border=0 class="data">
<tbody>
<tr><th colspan=3 class="first">Incorrect
<tt>HomGroupPresentation</tt> simplification routines</th></tr>
<tr>
<td class="subheading">Affected versions</td>
<td>4.96–7.2</td>
<td>Fixed in version 7.3</td>
</tr>
<tr>
<td class="subheading">Main symptom</td>
<td> </td>
<td>In C++ or Python, calling any of the three high-level
<tt>HomGroupPresentation</tt>
simplification routines could give incorrect results.</td>
</tr>
<tr>
<td class="subheading">Affected users</td>
<td>C++/Python programmers only</td>
<td>This affected programmers who called
<tt>intelligentSimplify()</tt>, <tt>intelligentNielsen()</tt> or
<tt>smallCancellation()</tt> on a <tt>HomGroupPresentation</tt>
object.</td>
</tr>
<tr>
<td class="subheading">Was I affected?</td>
<td>Easy to test</td>
<td>Check your C++/Python code to see if you are explicitly
working with group <i>homomorphisms</i> (i.e.,
<tt>HomGroupPresentation</tt> objects),
<i>and</i> calling one of the
simplification functions listed above.</td>
</tr>
<tr><th colspan=3 class="inner">Incorrect <tt>GroupPresentation</tt>
recognition for extensions over <i>Z</i></th></tr>
<tr>
<td class="subheading">Affected versions</td>
<td>4.96–7.2</td>
<td>Fixed in version 7.3</td>
</tr>
<tr>
<td class="subheading">Main symptom</td>
<td> </td>
<td>If a finitely presented group was an extension over <i>Z</i>, then
<tt>GroupPresentation::recogniseGroup()</tt> (which generates the plain
text “name” of a fundamental group / knot group in the
graphical user interface) might have described this extension
using the wrong monodromy.</td>
</tr>
<tr>
<td class="subheading">Affected users</td>
<td>All users</td>
<td> </td>
</tr>
<tr>
<td class="subheading">Was I affected?</td>
<td>Easy to test</td>
<td>Only if you relied on the human-readable group names in the
user interface or the string-based routine
<tt>GroupPresentation::recogniseGroup()</tt>, <i>and</i> you were
using the specific monodromies that were reported for extensions
over <i>Z</i>.</td>
</tr>
</table>
<p>
<h3>Details</h3>
<p>
The two issues above are related:
<ul>
<li>The issue with <tt>HomGroupPresentation</tt> simplification
was the root of the problem.</li>
<li>The issue with <tt>GroupPresentation::recogniseGroup()</tt> was
a consequence of this, and indeed the <i>only</i> consequence—this
was the only place where Regina was actually using the problematic
<tt>HomGroupPresentation</tt> simplification code.</li>
</ul>
Specifically, if <tt>GroupPresentation::recogniseGroup()</tt> identifies
a group as an extension over <i>Z</i>, it calls
<tt>HomGroupPresentation::intelligentSimplify()</tt> to help identify the
precise monodromy.
<p>
Although this was an old bug that affected all users, it is nevertheless
easily to isolate the scope of the bug.
<p>
In particular, you were <i>not</i> affected if:
<ul>
<li>you were just simplifying group presentations
(not homomorphisms); and/or</li>
<li>you were working with the group generators and relations directly
(not using the text-based <tt>recogniseGroup()</tt>,
i.e., the group “name”); and/or</li>
<li>you were using group names to identify other types of groups (e.g.,
the trivial group, or cyclic groups), not extensions over <i>Z</i>.</li>
</ul>
The root cause came from <tt>GroupPresentation::simplifyWord()</tt>,
which would not only simplify a word in a group, but potentially rotate
(i.e., conjugate) the word also.
The bug then appeared because the high-level <tt>HomGroupPresentation</tt>
simplification routines would use <tt>simplifyWord()</tt> to simplify images
and preimages of generators under a homomorphism.
<p>
To avoid simliar problems in the future,
<tt>GroupPresentation::simplifyWord()</tt>
has now been renamed to <tt>GroupPresentation::simplifyAndConjugate()</tt>,
in order to make its behaviour clearer.
<p>
<i><a href="#contents">(Back to top...)</a></i>
<h2><a name="bindings">Two Python binding errors (Oct 2022)</a></h2>
<h3>Summary</h3>
<table cellspacing=0 border=0 class="data">
<tbody>
<tr><th colspan=3 class="first">Incorrectly-bound <tt>swap()</tt> for
fixed-width bitmasks</th></tr>
<tr>
<td class="subheading">Affected versions</td>
<td>7.0–7.1</td>
<td>Fixed in version 7.2</td>
</tr>
<tr>
<td class="subheading">Main symptom</td>
<td> </td>
<td>In Python, calling <tt>regina.swap()</tt> with
fixed-width bitmasks (types <tt>Bitmask8</tt>, <tt>Bitmask16</tt>, ...,
<tt>Bitmask256</tt>) led to undefined behaviour.</td>
</tr>
<tr>
<td class="subheading">Affected users</td>
<td>Python programmers only</td>
<td>This only affected those rare Python programmers
who called one of the specialised swap functions above.</td>
</tr>
<tr>
<td class="subheading">Was I affected?</td>
<td>Unlikely</td>
<td>Just examine your Python code, and see if you are explicitly
creating objects of type <tt>Bitmask8</tt>, ..., or <tt>Bitmask256</tt>,
<em>and</em> explicitly swapping them via <tt>regina.swap()</tt>.</td>
</tr>
<tr><th colspan=3 class="inner">Incorrectly-bound
<tt>Cyclotomic.negate()</tt></th></tr>
<tr>
<td class="subheading">Affected versions</td>
<td>5.0–7.1</td>
<td>Fixed in version 7.2</td>
</tr>
<tr>
<td class="subheading">Main symptom</td>
<td> </td>
<td>In Python, calling <tt>Cyclotomic.negate()</tt> would in fact
perform a multiplicative inversion instead.</td>
</tr>
<tr>
<td class="subheading">Affected users</td>
<td>Python programmers only</td>
<td>This only affected Python programmers who did their own arithmetic
on cyclotomic field elements and called <tt>x.negate()</tt> instead
of the more natural <tt>-x</tt>.</td>
</tr>
<tr>
<td class="subheading">Was I affected?</td>
<td>Unlikely</td>
<td>Just examine your Python code, and see if you are
explicitly creating <tt>Cyclotomic</tt> objects and/or retrieving
them as Turaev-Viro invariants, <i>and</i>
explicitly calling <tt>negate()</tt> on these objects.</td>
</tr>
</table>
<p>
<h3>Details</h3>
<p>
Only Python programmers were affected by these issues:
any C++ code that worked with bitmasks and/or cyclotomic field elements
(including Regina's Turaev-Viro computations) was unaffected.
Moreover, to trigger these bugs, you had to do the following in
<i<>your own code</i>.
<p>
To trigger the <tt>swap()</tt> bug:
<ul>
<li>create fixed-width bitmasks of one of the types
<tt>Bitmask8</tt>, ..., <tt>Bitmask256</tt> (the main
<tt>Bitmask</tt> class was unaffected);</li>
<li>swap two of these bitmasks in Python via the global
<tt>regina.swap()</tt> function.</li>
</ul>
To trigger the <tt>Cyclotomic.negate()</tt> bug:
<ul>
<li>hold a <tt>Cyclotomic</tt> object <tt>x</tt>,
either by creating it yourself
or by fetching it from <tt>Triangulation3.turaevViro()</tt> and/or
<tt>Triangulation3.allCalculatedTuraevViro()</tt>;</li>
<li>explicitly negate <tt>x</tt> in Python by calling
<tt>x.negate()</tt> (the operator <tt>-x</tt> was unaffected).</li>
</ul>
<p>
It seems unlikely that anybody would have been affected by these issues:
<ul>
<li>The fixed-width bitmasks are specialised classes,
mainly used for optimisation in the C++ calculation engine.
They were only made accessible to Python with Regina 7.0.
Moreover, they are not returned by other Regina functions: you would
have had to explicitly create these bitmasks yourself.</li>
<li>The heavily overloaded <tt>regina::swap()</tt> function is mainly
for C++ users (as part of the shift in Regina 7.0 to value semantics).
Python users do not need such a function, since Python uses reference
semantics (not value semantics), and assignment operations are cheap.</li>
<li>The API documentation does not actually describe an overload of
<tt>regina::swap()</tt> for fixed-width bitmasks, since no such function
exists in Regina's C++ calculation engine. You would have had to
guess that this overload existed and tried to use it.</li>
<li>Cyclotomic field elements are only returned from Regina's
calculation engine when computing Turaev-Viro invariants.
As invariants, Python users might want to compute these, compare them
and/or hash them for fast lookup, but it seems unlikely that
typical users would need to manipulate them arithmetically.</li>
</ul>
<p>
The cause of the <tt>swap()</tt> problem was that, as noted above,
Regina's C++ calculation engine does not overload <tt>regina::swap()</tt>
for fixed-width bitmasks (since they are so small that a specialised
swap function is unnecessary).
The Python bindings incorrectly declared a <tt>regina.swap()</tt>
overload for fixed-width bitmasks, but forwarded this to the C++ function
that takes the more general <tt>Bitmask</tt> type instead.
In Regina 7.2, the Python bindings for heavily overloaded functions
such as <tt>regina::swap()</tt> have been rewritten to use typesafe
C++-casts instead of the old C-style casts to resolve the overloads,
thus preventing such an issue from occuring again.
<p>
The cause of the <tt>Cyclotomic.negate()</tt> function was much simpler:
the python name <tt>Cyclotomic.negate</tt> was accidentally bound to the
C++ method <tt>Cyclotomic::inverse()</tt> in the code that connects the
two languages.
<p>
<i><a href="#contents">(Back to top...)</a></i>
<h2><a name="defaultalg">Normal surface enumeration ignores arguments
(Sep 2016)</a></h2>
<h3>Summary</h3>
<table cellspacing=0 border=0 class="data"><tbody>
<tr>
<td class="topsubheading">Affected versions</td>
<td class="top">4.94–4.96</td>
<td class="top">Fixed in version 5.0.</td>
</tr>
<tr>
<td class="subheading">Main symptom</td>
<td> </td>
<td>Regina computed embedded vertex normal surfaces,
even if you asked for something else (e.g., fundamental surfaces, or
immersed/singular surfaces).</td>
</tr>
<tr>
<td class="subheading">Affected users</td>
<td>C++ programmers only</td>
<td>This only affected C++ programmers, and only those who called the
<tt>NNormalSurfaceList::enumerate()</tt> function in a certain way.</td>
</tr>
<tr>
<td class="subheading">Was I affected?</td>
<td>Easy to test</td>
<td>Just examine your C++ code and see if your calls to
<tt>enumerate()</tt> follow the pattern described below.</td>
</table>
<p>
<h3>Details</h3>
<p>
Only C++ programmers were affected by this issue.
If you only used Regina through Python or the graphical user interface,
then you were not affected.
<p>
The problem was triggered when the user called
<tt>NNormalSurfaceList::enumerate(tri, coords, which)</tt>, and:
<ul>
<li>the <tt>NormalList</tt> argument <tt>which</tt>
contained exactly one flag (e.g., only <tt>NS_FUNDAMENTAL</tt>,
or only <tt>NS_IMMERSED_SINGULAR</tt>, but not a combination such as
<tt>NS_FUNDAMENTAL | NS_EMBEDDED_ONLY</tt>); and</li>
<li>the optional <tt>NormalAlg</tt> argument (which
specifies an enumeration algorithm) was <i>not</i> passed.</li>
</ul>
If these conditions were met, then the flag passed in <tt>which</tt>
would be ignored. Instead:
<ul>
<li>if the flag you passed was <tt>NS_LIST_DEFAULT</tt>, then Regina
would compute immersed and/or singular vertex surfaces
(i.e., it assumed the flags <tt>NS_VERTEX | NS_IMMERSED_SINGULAR</tt>
instead);</li>
<li>if you passed any other flag, then Regina would compute
embedded vertex surfaces (i.e., it assumed the default flags
<tt>NS_VERTEX | NS_EMBEDDED_ONLY</tt> instead).
</ul>
<p>
The problem did <i>not</i> occur if:
<ul>
<li>you did not pass the <tt>which</tt> argument (which is also optional),
e.g., <tt>NNormalSurfaceList::enumerate(tri, coords)</tt>; or
<li>you passed multiple flags in the <tt>which</tt> argument, e.g.,
<tt>NNormalSurfaceList::enumerate(tri, coords,
NS_FUNDAMENTAL | NS_EMBEDDED_ONLY)</tt>; or</li>
<li>you passed an additional algorithm argument, e.g.,
<tt>NNormalSurfaceList::enumerate(tri, coords, NS_FUNDAMENTAL,
NS_ALG_DEFAULT)</tt>.</li>
</ul>
<p>
The cause of the problem was that versions 4.94–4.96 of Regina
contained <i>two</i> <tt>enumerate()</tt> functions: the modern function that
takes <tt>NormalList</tt> and <tt>NormalAlg</tt> flags, and an old deprecated
function that took a <tt>bool</tt> argument for whether to enumerate
embedded surfaces only.
If a single flag was passed (of the enum type <tt>NormalListFlag</tt>),
then the C++ priority rules for type conversions meant that this was
interpreted as a <tt>bool</tt> instead of implicitly calling the
<tt>NormalList(NormalListFlag)</tt> constructor.
Therefore the old function would be called instead.
<p>
This was fixed in Regina 5.0 by removing the old deprecated
function entirely.
<p>
It is easy to test whether you were affected by this issue:
<ul>
<li>You can examine your C++ code, to see if you were calling
<tt>NNormalSurface::enumerate()</tt> in the manner described above
(with exactly one <tt>NormalList</tt> flag, and without passing the
additional algorithm argument);</li>
<li>If you have saved your data to file, then you can see what enumeration
flags were actually used. You can see these flags in the
graphical user interface at the top of the normal surface viewer,
or you can call <tt>list.which()</tt> in Python or C++.</li>
</ul>
<i><a href="#contents">(Back to top...)</a></i>
<h2><a name="mod">Mod and gcd broken for extremely large integers
(Nov 2013)</a></h2>
<p>
<h3>Summary</h3>
<table cellspacing=0 border=0 class="data"><tbody>
<tr>
<td class="topsubheading">Affected versions</td>
<td class="top">4.94 only</td>
<td class="top">Fixed in version 4.95.</td>
</tr>
<tr>
<td class="subheading">Main symptom</td>
<td> </td>
<td>The <tt>mod</tt> and <tt>gcd</tt> operations gave incorrect results
in some rare scenarios when working with extremely large integers.</td>
</tr>
<tr>
<td class="subheading">Affected users</td>
<td>All users</td>
<td>This affected all users, but only in rare situations which are
unlikely to be seen in practice (described below).</td>
</tr>
<tr>
<td class="subheading">Was I affected?</td>
<td>Unlikely</td>
<td>The bug was quite difficult to trigger, and had relatively benign
impacts unless you were working with experimental code direct from
the repository. See below for details.</td>
</table>
<p>
<h3>Details</h3>
<p>
<p>
This issue only appeared where large integers were present, and only then in
certain rare scenarios. Here “large integer” means an
integer too large to fit into a native <tt>long</tt> type on a computer
(i.e., its absolute value is ≥ 2<sup>31</sup> on a typical 32-bit
machine, or ≥ 2<sup>63</sup> on a typical 64-bit machine).
<p>
There were in fact two bugs, both thankfully hard to trigger:
<ul>
<li>The operation (<i>x</i> mod <i>m</i>) was broken in the following
scenario:
<ul>
<li><i>x</i> was both negative and small enough to store as a
native <tt>long</tt> integer; and</li>
<li>the modulus <i>m</i> had at some stage been too large to fit
into a native <tt>long</tt>, it had subsequently been modified through
some arithmetic operations so that
it was now small enough to fit into a <tt>long</tt>, but the calculation
engine had not yet optimised its storage and was still using a large
integer representation of <i>m</i>; and</li>
<li>the modulus <i>m</i> was now small enough so that
|<i>m</i>| ≤ |<i>x</i>|.</li>
</ul>
If all of these conditions were met then the mod operation did nothing
(i.e., it just returned <i>x</i>).</li>
<li>The gcd operation was broken precisely when computing
gcd(<tt>LONG_MIN</tt>, 0) or gcd(0, <tt>LONG_MIN</tt>).
Here <tt>LONG_MIN</tt> represents the lowest integer that can be stored
as a native <tt>long</tt> (typically -2<sup>31</sup> on a 32-bit machine,
or -2<sup>63</sup> on a 64-bit machine).
In this case the gcd would be missing a factor of two (i.e., it would
return <tt>-LONG_MIN</tt>/2 instead of the correct answer
<tt>-LONG_MIN</tt>).</li>
</ul>
<p>
The <tt>mod</tt> error could in theory affect Regina's algebraic code (e.g.,
matrix computations related to homology). However, if you were simply calling
<tt>getHomologyH1()</tt> on 3-manifold triangluations, it is extremely
unlikely that you would encounter the bug. The more dangerous scenario
is if you were using experimental (and more complex) algebraic code from
the git repository (and in fact, this is how the bug was spotted).
<p>
The <tt>gcd</tt> error was extremely rare, in that there was only one
pair of integers that could trigger it. In theory this error could affect
normal surface enumeration, but here the symptom would have been both
mild and obvious: you would have seen vertex surfaces that were not
scaled down to their lowest integer multiple.
<p>
<i><a href="#contents">(Back to top...)</a></i>
<p class="return">
<a href="index.html"><img src="regina.svg" alt="Back to main page ..."
border="0" width="32" height="32" align="middle"></a>
<a href="index.html">Back to main page ...</a></p>
</body>
</html>