Return to Answer

Let $a/b \ge 1$ be the slope of the primary bounding ray, with $a \ge b \gt 0$ taken directly from the input equations. Let $q,r$ be the quotient and remainder of dividing $a$ by $b$. That is, $q=\mathrm{floor}(a/b), r=a-qb, a \ge b \gt r \ge 0$.

Apply to the problem geometry the shear that leaves the $y$ axis fixed and takes $(1,q)$ to $(1,0)$; in other words, the linear transformation that leaves $(0,1)$ fixed and takes $(1,0)$ to $(1,-q)$. Maintain the designation "primary" on the image of the primary bounding ray. This shear transformation decreases the primary ray's slope to r/b, either keeping its direction into the first quadrant, or (if r=0) parallel to the x axis.

In the transformed problem, the primary bounding ray has slope $r/b$ with $b > r > 0$ so its slope is $< 1$; therefore as we start analysis of the transformed problem as before, we'll swap the coords so that its slope $b/r > 1$. Notice that what we've done so far is perform one iteration of the euclidean algorithm; that is, $a$ has been replaced by $b$, and $b$ has been replaced by the remainder of $a$ divided by $b$.

So how expensive is an iteration? Each iteration consists of a small constant number of arithmetic operations, each of which is at most $O(M(\mathrm{num\ digits\ in\ operands}))$ where M stands for the cost of one multiplication (see the wikipedia article "Computational cost of mathematical operations"). But how many digits is that?

Let $a/b \ge 1$ be the slope of the primary bounding ray, with $a \ge b \gt 0$ taken directly from the input equations. Let $q,r$ be the quotient and remainder of dividing $a$ by $b$. That is, $q=\mathrm{floor}(a/b), r=a-q b, a \ge b \gt r \ge 0$.

Apply to the problem geometry the shear that leaves the $y$ axis fixed and takes $(1,q)$ to $(1,0)$; in other words, the linear transformation that leaves $(0,1)$ fixed and takes $(1,0)$ to $(1,-q)$. Maintain the designation "primary" on the image of the primary bounding ray. This shear transformation decreases the primary ray's slope to r/b, either keeping its direction into the first quadrant (if $r>0$), or parallel to the $x$ axis (if $r=0$).

In the transformed problem, the primary bounding ray has slope $r/b$ with $b > r > 0$ (still in Case 1 here) so its slope is $< 1$; therefore as we start analysis of the transformed problem as before, we'll swap the coords so that its slope $b/r > 1$. Notice that what we've done so far is perform one iteration of the euclidean algorithm; that is, $a$ has been replaced by $b$, and $b$ has been replaced by the remainder of $a$ divided by $b$.

So how expensive is an iteration? Each iteration consists of a small constant number of arithmetic operations, each of which is at most $O(M(\mathrm{num\ digits\ in\ operands}))$ where $M$ stands for the cost of one multiplication (see the wikipedia article "Computational cost of mathematical operations"). But how many digits is that?

Apply to the problem geometry the shear that leaves the $y$ axis fixed and takes $(1,q)$ to $(1,0)$; in other words, the linear transformation that leaves $(0,1)$ fixed and takes $(1,0)$ to $(1,-q)$. Maintain the designation "primary" on the image of the primary bounding ray.

Case 3: The shear leaves the primary bounding ray direction in the interior of the first quadrant, but it takes the secondary bounding ray dir out of the interior of the first quadrant: that is, to either the $x$ axis or the fourth quadrant.

Apply to the problem geometry the shear that leaves the $y$ axis fixed and takes $(1,q)$ to $(1,0)$; in other words, the linear transformation that leaves $(0,1)$ fixed and takes $(1,0)$ to $(1,-q)$. Maintain the designation "primary" on the image of the primary bounding ray. This shear transformation decreases the primary ray's slope to r/b, either keeping its direction into the first quadrant, or (if r=0) parallel to the x axis.

Case 3: The shear takes the secondary bounding ray direction out of the interior of the first quadrant, to either the $x$ axis or the fourth quadrant. (This is regardless of whether the primary bounding ray direction became horizontal or stayed in the first quadrant).

Let $n$ be the input size, i.e. the log of the max magnitude of any of the input numbers.

Repeat as often as we find ourselves in Case 1. Since the $a,b$ values are following the euclidean algorithm starting with two of the original input numbers, well-known analysis of the euclidean algorithm tells us Case 1 can happen at most $O(n)$ times: that is, if we get all the way to the end of the euclidean algorithm, $b$ will become 0 which will take us out of Case 1 (if we haven't already left it before that).

Let $n$ be the input size, i.e. the number of input digits in some base, or the sum or max of the logs of the magnitudes of the input numbers-- these are all equivalent for the purposes of big-O.

Repeat as often as we find ourselves in Case 1 (keeping the "primary" designation on the same one of the two rays even as they get transformed). Since the $a,b$ values are following the euclidean algorithm starting with two of the original input numbers, well-known analysis of the euclidean algorithm tells us Case 1 can happen at most $O(n)$ times: that is, if we get all the way to the end of the euclidean algorithm, $b$ will become 0 which will take us out of Case 1 (if we haven't already left it before that).