Appendix A Estimating Pythagorean Square-root


For the line drawing commands described in the main sections of this document, we need to estimate the Pythagorean square-root in order to determine the length of the line (along its slope). More precisely, we need to estimate the number of segments of a given length needed to draw a line. TEX does not provide for floating point calculations, and thus there are no direct means of calculating the above square-root. Most standard numerical techniques are iterative and would be too slow when used with TEX for lack of floating point calculations, and in particular, real division, since calculation of such a square-root is needed very frequently.

A simple non-iterative formula for estimating the square-root is derived and described below.


Problem: Given a and b, to find c = $\sqrt{{a^2 + b^2}}$ using only operations in {+ , - ,*,/}.

We can get very tight bounds on the square-root as follows. Without loss of generality, let a≥b. We seek a simple n such that:

$\displaystyle \sqrt{{a^2 + b^2}}$≥a + $\displaystyle {\frac{{b}}{{n}}}$

Squaring both sides, we have

⇔ a2 + b2 ≥ a2 + $\displaystyle {\frac{{b^2}}{{n^2}}}$ + $\displaystyle {\frac{{2ab}}{{n}}}$
⇔ (1 - $\displaystyle {\frac{{1}}{{n^2}}}$)b2 ≥ $\displaystyle {\frac{{2ab}}{{n}}}$
⇔ $\displaystyle {\frac{{b}}{{a}}}$ ≥ $\displaystyle {\frac{{2n}}{{(n^2 -1)}}}$
or ($\displaystyle {\frac{{b}}{{a}}}$)n2 -2n - ($\displaystyle {\frac{{b}}{{a}}}$) ≥ 0

>From the quadratic equation above, we finally get an expression for n,

n   =  $\displaystyle {\frac{{2 \pm \sqrt{4 + 4(\frac{b}{a})^2}}}{{\frac{2b}{a}}}}$   =  $\displaystyle {\frac{{1 \pm \sqrt{1 + (\frac{b}{a})^2}}}{{\frac{b}{a}}}}$

Only the +ve root interests us since n has to be positive. Note that the term under the root is bounded above and below (since ${\frac{{b}}{{a}}}$≤1):

1  ≤  $\displaystyle \sqrt{{1 + (\frac{b}{a})^2}}$  ≤  $\displaystyle \sqrt{{2}}$

Hence, we have two values for n,

nl   =  $\displaystyle {\frac{{1+1}}{{\frac{b}{a}}}}$   =  $\displaystyle {\frac{{2a}}{{b}}}$;                    nu   =  $\displaystyle {\frac{{1+ \sqrt{2}}}{{\frac{b}{a}}}}$   =  $\displaystyle {\frac{{(1+ \sqrt{2})a}}{{b}}}$

which finally gives us a lower and an upper bound for c, the Pythagorean square-root,

a + $\displaystyle {\frac{{b^2}}{{(1+ \sqrt{2})a}}}$  ≤  c  ≤  a + $\displaystyle {\frac{{b^2}}{{2a}}}$

These are very tight bounds. Denoting the lower bound as cl and upper one cu, below are some numerical results (c = exact square-root):

a b c cl cu
100.0 100.0 141.4213 141.4213 150.0
100.0  80.0 128.0642 126.5096 132.0
 30.0  20.0  36.0555 35.5228 36.6667

With the above bounds, one can do a linear interpolation to get exact values. In our case, since it is not required to be extremely accurate, for estimating the square-root in the line drawing commands, we simply take the midpoint of the two bounds. For small numbers, which is expected to be the case most of the time, the error is very small.

With some algebra, we get the mid-point estimate of c,

c = $\displaystyle {\frac{{c_l+c_u}}{{2}}}$ = a + $\displaystyle {\frac{{b^2 * (3 + \sqrt{2})}}{{a*4*(1 + \sqrt{2})}}}$ = a + $\displaystyle {\frac{{0.457\: b^2}}{{a}}}$        (a≥b)

The macro \sqrtandstuff uses the above formula for estimating the number of points (for \dottedline macro) and number of segments (for \dashline macro). The \sqrtandstuff macro, instead of calculating the length of the line, directly calculates the number of segments of a given length. For example, to draw a dotted line from (x1, y1) to (x2, y2) with the inter-dot-gap as d, we estimate the number of dots n using the following expression,

n = $\displaystyle {\frac{{\Delta x}}{{d}}}$ + $\displaystyle {\frac{{0.457\:(\frac{\Delta y}{d})^2}}{{\frac{\Delta x}{d}}}}$              Δx = | x2 - x1| and Δy = | y2 - y1|

assuming Δx≥Δy (otherwise they may be inter-changed).

Note that since divisions in TEX are integer-divisions, it is simpler to deal in ``number of segments'' rather than actual lengths (e.g. in the expression above, ${\frac{{\Delta x}}{{d}}}$ = number of segments along X-axis).

Caveat: The approach presented here for estimation of Pythagorean square-root is an independent effort by the author. It may already exist in the literature — the author is neither aware of it nor has he made any serious attempts at uncovering it.