At (0, 0), (2ᵏ + 1, 2ᵏ), (2ᵏ, 2ᵏ − 1) the determinant is −1 for every k: the same right turn at every magnitude. In double arithmetic the two products collide once 2k passes 53 and the predicate reports collinear. The lab sweeps 29 magnitudes and counts the failures rather than warning about them, and the failure has a shape: the double test can lose a turn, and it cannot invent the opposite one.
Core ideas
One construction, one count, and one theorem about the shape of the failure. The theorem is the part worth carrying away, because it is stronger and more useful than the count.
Fix k and take a = (0, 0), b = (2ᵏ + 1, 2ᵏ) and c = (2ᵏ, 2ᵏ − 1). The determinant is (2ᵏ + 1)(2ᵏ − 1) − 2ᵏ·2ᵏ, which is 2²ᵏ − 1 − 2²ᵏ = −1, for every k with no exceptions. So sweeping k upward is not sweeping through harder and harder geometry; it is asking one question — is this a right turn — whose answer is fixed, at larger and larger magnitudes.
In double precision the two products are 2²ᵏ − 1 and 2²ᵏ. A double has 53 bits of significand, so once 2k exceeds 53 those two integers round to the SAME double, their difference is exactly 0, and the predicate says collinear. There is no drift and no accumulation of small errors: below the threshold the answer is exactly right, above it the answer is exactly 0, and the lab prints both columns so the step is visible as a step.
Every disagreement the lab finds is the double reporting 0 where the exact test reports a turn. It never reports the opposite turn. The coordinate differences here are integers below 2⁵³ and so are exact, and rounding to nearest is monotone, so the rounded product of the larger pair cannot fall below the rounded product of the smaller one — it can only tie. So a hull built with the double predicate can be missing a corner, and cannot have a corner in the wrong place, which is a much more specific defect to go looking for.
The material
The construction, the exact count, the threshold that is not an estimate, and the theorem that says how the failure can and cannot go.
For an integer k, the needle at 2ᵏ is the triple a = (0, 0), b = (2ᵏ + 1, 2ᵏ), c = (2ᵏ, 2ᵏ − 1). Its exact orientation determinant is −1 for every k, so every member of the family is the same right turn. The lab sweeps k from 20 to 48 and reports, for each one, the exact determinant, the double determinant, and whether the two signs agree.
The arithmetic is worth doing once by hand. With a at the origin the determinant is bx·cy − by·cx, which is (2ᵏ + 1)(2ᵏ − 1) − 2ᵏ·2ᵏ. The first product is a difference of squares, 2²ᵏ − 1, and the second is 2²ᵏ. Subtract and everything cancels but the −1.
In IEEE double precision the needle at 2ᵏ is evaluated correctly for k ≤ 26 and reports 0 for k ≥ 27. Over the 29 magnitudes from 20 to 48 the double predicate is therefore wrong on 22 of them, every one from 2²⁷ upward, and right on the seven below.
A double holds a significand of 53 bits, so every integer up to 2⁵³ is representable, and in the interval from 2ᵉ⁻¹ to 2ᵉ the representable numbers are spaced 2^(e − 53) apart.
The two products are 2²ᵏ − 1 and 2²ᵏ. For 2k ≤ 53 both are at most 2⁵³ and so are represented exactly, their difference is computed exactly, and the answer is −1. That is k ≤ 26.
For 2k ≥ 54, the representable numbers just below 2²ᵏ are spaced 2^(2k − 53) ≥ 2 apart, so 2²ᵏ − 1 is not one of them: its neighbours are 2²ᵏ − 2^(2k − 53) and 2²ᵏ, and it is at least as close to the second as to the first. Where 2k = 54 the two are equidistant and round-to-nearest breaks the tie towards the even significand, which is 2²ᵏ; where 2k > 54 the second is strictly nearer. Either way both products become the same double, their difference is exactly 0, and the subtraction introduces no further error. That is k ≥ 27. The sweep from 20 to 48 is 29 values, of which 27 through 48 is 22.
□
Nothing in that argument is an estimate and nothing in it is a rule of thumb. The lab does not quote the threshold either — it evaluates both routes at all 29 magnitudes and counts, and the count it reports is 22 with the first failure at 2²⁷. Move the slider to highlight a row and the corresponding triple appears in the upper table with all three routes beside one another.
At k = 26 the points are (0, 0), (67108865, 67108864), (67108864, 67108863). The products are 4503599627370495 and 4503599627370496, both under 2⁵³, both exact, and the difference is −1: the double agrees. At k = 27 the points are (0, 0), (134217729, 134217728), (134217728, 134217727). The products are 18014398509481983 and 18014398509481984, the first of which is not representable, and both become 18014398509481984. The double determinant is 0 and the predicate calls a right turn collinear. One power of two apart, and the answer changes from right to wrong.
That pair is the reason the preset list on this page has both of them in it. Switching between the two worked examples changes one bit of the input and flips the verdict of a predicate that most textbooks present without qualification, which is a more convincing argument than any amount of prose about machine epsilon.
Let a, b, c have integer coordinates whose pairwise differences are at most 2⁵³ in absolute value. If the double-precision evaluation of orient(a, b, c) disagrees in sign with the exact one, then the double-precision sign is 0. It is never the opposite nonzero sign.
The four differences bx − ax, cy − ay, by − ay, cx − ax are integers of magnitude at most 2⁵³, so each is represented exactly and the subtractions that produce them introduce no error at all. The only rounding happens in the two products and in the final subtraction.
Write the two exact products as P and Q, so the exact determinant is P − Q. IEEE multiplication returns the representable number nearest its exact result, and round-to-nearest is monotone: if P ≤ Q then fl(P) ≤ fl(Q). Suppose the exact determinant is negative, so P < Q; then fl(P) ≤ fl(Q), so fl(P) − fl(Q) ≤ 0, and the final subtraction of two doubles cannot change the sign of a nonpositive quantity. The computed determinant is therefore ≤ 0: it can be the right sign or it can be 0, and it cannot be positive. The case P > Q is the same argument with the inequalities reversed.
□
This is a theorem and not a measurement, but the lab supplies the measurement beside it: across the swept family every one of the 22 failures is the double reporting 0, and the arithmetic checker that runs over this kit throws thirty thousand random near-collinear triples at 2²⁶ and above at both routes. On those thirty thousand the two routes disagree 1,258 times, and not once does the double report the opposite turn.
The count is a measurement on one family. It says nothing about a triple chosen some other way, and in particular “22 of 29” is not a failure rate for double-precision geometry in general — the family was constructed to fail, which is the only honest way to find the threshold. What generalises is the theorem above it: the 53-bit argument applies to any integer input, and the one-sidedness applies to any input at all.
That distinction is the whole method of this path. A lab can run an algorithm on an input; it cannot quantify over inputs. Here the two happen to line up unusually well, because the threshold the sweep finds by measurement is the same 2k > 53 the proof gives, and a reader can check one against the other on the page.
Interactive
One determinant, computed exactly twice and approximately once
Method
Count the bits in the products, not the digits in the coordinates.
The determinant multiplies DIFFERENCES, so what matters is the spread of the point set, not its distance from the origin. Three points a millimetre apart on the far side of the world have small differences and behave well; the needle family is bad because the differences themselves are large.
If the differences fit in m bits then the products need about 2m, and a double holds 53. Below 2m = 53 every product is exact and so is the subtraction. Above it, two products that differ by a little can land on the same double. This is why the threshold here is 2²⁷ and not 2⁵³.
A predicate that collapses to zero is not harmless: a hull step reads zero as “not a left turn” and pops a real corner, and a segment test reads zero as “collinear” and takes a branch written for a different case. Find the branch the zero takes before deciding how bad the collapse is.
Since the double result can only lose a turn, a hull computed with it can be missing a vertex and cannot contain a point that is not on the true hull. That narrows a hunt for a bug from “something is wrong” to “a vertex is missing”, which the next lesson takes up.
Every row is the same right turn. The two columns in the middle are the exact determinant and the double one; the last two are the signs read off them.
Three things to notice. First, the transition is a step and not a slope: there is no row where the double is close but not exactly right. Either the products are both representable and the answer is −1, or they collide and the answer is 0.
Second, the threshold is where 2k passes 53 and not where k does. At k = 26 the coordinates are around 67 million, which is nowhere near the largest integer a double holds; it is the PRODUCTS, around 4.5 × 10¹⁵, that are up against the limit. A reader who checks the size of the inputs and concludes that everything is comfortable has checked the wrong quantity.
Third, every failing row fails the same way. For a faded rehearsal, predict what the table would look like if the family were c = (2ᵏ, 2ᵏ + 1) instead, which makes the exact determinant +1. The supplied first move is that the products become 2²ᵏ + 1 and 2²ᵏ, and 2²ᵏ + 1 rounds down to 2²ᵏ above the threshold for exactly the same reason. Say what the failing rows then report, and confirm that the one-sidedness theorem predicted it.
You should be able to derive 2k > 53 from the 53-bit significand, read the sweep's count off the page as a measurement rather than a rate, state the one-sidedness theorem and its monotonicity argument, and predict which defects a hull built on the double predicate can and cannot have.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.