;SPMlt;!DOCTYPE HTML PUBLIC ;SPMquot;-//W3C//DTD HTML 3.2 Final//en;SPMquot;;SPMgt;

<P>
;SPMlt;!--Converted with LaTeX2HTML 2022 (Released January 1, 2022) --;SPMgt;
;SPMlt;HTML lang=;SPMquot;en;SPMquot;;SPMgt;
;SPMlt;HEAD;SPMgt;
;SPMlt;TITLE;SPMgt;Contents of References;SPMlt;/TITLE;SPMgt;

<P>
;SPMlt;META HTTP-EQUIV=;SPMquot;Content-Type;SPMquot; CONTENT=;SPMquot;text/html; charset=utf-8;SPMquot;;SPMgt;
;SPMlt;META NAME=;SPMquot;viewport;SPMquot; CONTENT=;SPMquot;width=device-width, initial-scale=1.0;SPMquot;;SPMgt;
;SPMlt;META NAME=;SPMquot;Generator;SPMquot; CONTENT=;SPMquot;LaTeX2HTML v2022;SPMquot;;SPMgt;

<P>
;SPMlt;LINK REL=;SPMquot;STYLESHEET;SPMquot; HREF=;SPMquot;picman.css;SPMquot;;SPMgt;

<P>
;SPMlt;LINK REL=;SPMquot;previous;SPMquot; HREF=;SPMquot;node15_mn.html;SPMquot;;SPMgt;
;SPMlt;LINK REL=;SPMquot;up;SPMquot; HREF=;SPMquot;picman_mn.html;SPMquot;;SPMgt;
;SPMlt;/HEAD;SPMgt;

<P>
;SPMlt;BODY bgcolor=;SPMquot;#ffffff;SPMquot; text=;SPMquot;#000000;SPMquot; link=;SPMquot;#9944EE;SPMquot; vlink=;SPMquot;#0000ff;SPMquot; alink=;SPMquot;#00ff00;SPMquot;;SPMgt;

<P>
;SPMlt;H2;SPMgt;;SPMlt;A ID=;SPMquot;SECTION00070000000000000000;SPMquot;;SPMgt;
References;SPMlt;/A;SPMgt;
;SPMlt;/H2;SPMgt;;SPMlt;DL class=;SPMquot;COMPACT;SPMquot;;SPMgt;
;SPMlt;DT;SPMgt;;SPMlt;A ID=;SPMquot;Knu;SPMquot;;SPMgt;1;SPMlt;/A;SPMgt;
;SPMlt;DD;SPMgt; D. E. Knuth, ``The T;SPMlt;SMALL;SPMgt;E;SPMlt;/SMALL;SPMgt;Xbook'', Addison-Wesley Publishing Co.,
1984.
;SPMlt;DT;SPMgt;;SPMlt;A ID=;SPMquot;Lam;SPMquot;;SPMgt;2;SPMlt;/A;SPMgt;
;SPMlt;DD;SPMgt; L. Lamport, ``L;SPMlt;SUP;SPMgt;;SPMlt;SMALL;SPMgt;A;SPMlt;/SMALL;SPMgt;;SPMlt;/SUP;SPMgt;T;SPMlt;SMALL;SPMgt;E;SPMlt;/SMALL;SPMgt;X: A Document Preparation System'',
Addison-Wesley Publishing Co., 1986.
;SPMlt;/DL;SPMgt;

<P>
;SPMlt;P;SPMgt;

<P>
;SPMlt;P;SPMgt;;SPMlt;BR;SPMgt;

<P>
;SPMlt;FONT SIZE=;SPMquot;+2;SPMquot;;SPMgt;;SPMlt;B;SPMgt;Appendix A   Estimating Pythagorean Square-root;SPMlt;/B;SPMgt;;SPMlt;/FONT;SPMgt;

<P>
;SPMlt;P;SPMgt;

<P>
;SPMlt;P;SPMgt;;SPMlt;BR;SPMgt;

<P>
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.
T;SPMlt;SMALL;SPMgt;E;SPMlt;/SMALL;SPMgt;X 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 T;SPMlt;SMALL;SPMgt;E;SPMlt;/SMALL;SPMgt;X for lack
of floating point calculations, and in particular, real division, since
calculation of such a square-root is needed very frequently.

<P>
;SPMlt;P;SPMgt;
A simple non-iterative formula for estimating the square-root is derived and
described below.

<P>
;SPMlt;P;SPMgt;

<P>
;SPMlt;P;SPMgt;;SPMlt;P;SPMgt;;SPMlt;BR;SPMgt;

<P>
;SPMlt;B;SPMgt;Problem: ;SPMlt;/B;SPMgt; Given ;SPMlt;I;SPMgt;a;SPMlt;/I;SPMgt; and ;SPMlt;I;SPMgt;b;SPMlt;/I;SPMgt;, to find ;SPMlt;I;SPMgt;c;SPMlt;/I;SPMgt; = ;SPMlt;!-- MATH
 <tex2html_verbatim_mark>#math1#<tex2html_image_mark>#tex2html_wrap_inline382#

 --;SPMgt;
;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img10.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math2#<tex2html_image_mark>#tex2html_wrap_inline384#
;SPMquot;;SPMgt; using
only operations in <#3#>+ , - ,*,/<#3#>.

<P>
;SPMlt;P;SPMgt;
We can get very tight bounds on the square-root as follows.
Without loss of generality, let ;SPMlt;I;SPMgt;a;SPMlt;/I;SPMgt;;SPMamp;#8805;;SPMlt;I;SPMgt;b;SPMlt;/I;SPMgt;. We seek a simple ;SPMlt;I;SPMgt;n;SPMlt;/I;SPMgt;
such that:
;SPMlt;P;SPMgt;;SPMlt;!-- MATH
 <P><tex2html_verbatim_mark>#math3#</P><DIV ALIGN="CENTER">
<tex2html_image_mark>#tex2html_wrap_indisplay386#
&#8805;<I>a</I> + <tex2html_image_mark>#tex2html_wrap_indisplay387#

</DIV><P></P>
 --;SPMgt;
;SPMlt;/P;SPMgt;;SPMlt;DIV ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;
;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img11.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math4#<tex2html_image_mark>#tex2html_wrap_indisplay389#
;SPMquot;;SPMgt;;SPMamp;#8805;;SPMlt;I;SPMgt;a;SPMlt;/I;SPMgt; + ;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img12.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math5#<tex2html_image_mark>#tex2html_wrap_indisplay391#
;SPMquot;;SPMgt;
;SPMlt;/DIV;SPMgt;;SPMlt;P;SPMgt;;SPMlt;/P;SPMgt;

<P>
;SPMlt;P;SPMgt;
Squaring both sides, we have
;SPMlt;P;SPMgt;;SPMlt;!-- MATH
 <P><tex2html_verbatim_mark>#math6#</P><DIV ALIGN="CENTER">
<TABLE>
<TR VALIGN="MIDDLE"><TD ALIGN="LEFT">&#8660;</TD>
<TD ALIGN="RIGHT"><I>a</I><SUP>2</SUP> + <I>b</I><SUP>2</SUP></TD>
<TD ALIGN="CENTER">&#8805;</TD>
<TD ALIGN="LEFT"><I>a</I><SUP>2</SUP> + <tex2html_image_mark>#tex2html_wrap_indisplay397#
 + <tex2html_image_mark>#tex2html_wrap_indisplay398#
</TD>
</TR>
<TR VALIGN="MIDDLE"><TD ALIGN="LEFT">&#8660;</TD>
<TD ALIGN="RIGHT">(1 - <tex2html_image_mark>#tex2html_wrap_indisplay401#
)<I>b</I><SUP>2</SUP></TD>
<TD ALIGN="CENTER">&#8805;</TD>
<TD ALIGN="LEFT"><tex2html_image_mark>#tex2html_wrap_indisplay404#
</TD>
</TR>
<TR VALIGN="MIDDLE"><TD ALIGN="LEFT">&#8660;</TD>
<TD ALIGN="RIGHT"><tex2html_image_mark>#tex2html_wrap_indisplay407#
</TD>
<TD ALIGN="CENTER">&#8805;</TD>
<TD ALIGN="LEFT"><tex2html_image_mark>#tex2html_wrap_indisplay410#
</TD>
</TR>
<TR VALIGN="MIDDLE"><TD ALIGN="LEFT"><#1#>or <#1#></TD>
<TD ALIGN="RIGHT">(<tex2html_image_mark>#tex2html_wrap_indisplay413#
)<I>n</I><SUP>2</SUP> -2<I>n</I> - (<tex2html_image_mark>#tex2html_wrap_indisplay414#
)</TD>
<TD ALIGN="CENTER">&#8805;</TD>
<TD ALIGN="LEFT">0</TD>
</TR>
</TABLE>
</DIV><P></P>
 --;SPMgt;
;SPMlt;/P;SPMgt;;SPMlt;DIV ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;
;SPMlt;TABLE;SPMgt;
;SPMlt;TR VALIGN=;SPMquot;MIDDLE;SPMquot;;SPMgt;;SPMlt;TD ALIGN=;SPMquot;LEFT;SPMquot;;SPMgt;;SPMamp;#8660;;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;RIGHT;SPMquot;;SPMgt;;SPMlt;I;SPMgt;a;SPMlt;/I;SPMgt;;SPMlt;SUP;SPMgt;2;SPMlt;/SUP;SPMgt; + ;SPMlt;I;SPMgt;b;SPMlt;/I;SPMgt;;SPMlt;SUP;SPMgt;2;SPMlt;/SUP;SPMgt;;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;;SPMamp;#8805;;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;LEFT;SPMquot;;SPMgt;;SPMlt;I;SPMgt;a;SPMlt;/I;SPMgt;;SPMlt;SUP;SPMgt;2;SPMlt;/SUP;SPMgt; + ;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img13.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math7#<tex2html_image_mark>#tex2html_wrap_indisplay418#
;SPMquot;;SPMgt; + ;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img14.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math8#<tex2html_image_mark>#tex2html_wrap_indisplay420#
;SPMquot;;SPMgt;;SPMlt;/TD;SPMgt;
;SPMlt;/TR;SPMgt;
;SPMlt;TR VALIGN=;SPMquot;MIDDLE;SPMquot;;SPMgt;;SPMlt;TD ALIGN=;SPMquot;LEFT;SPMquot;;SPMgt;;SPMamp;#8660;;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;RIGHT;SPMquot;;SPMgt;(1 - ;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img15.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math9#<tex2html_image_mark>#tex2html_wrap_indisplay422#
;SPMquot;;SPMgt;);SPMlt;I;SPMgt;b;SPMlt;/I;SPMgt;;SPMlt;SUP;SPMgt;2;SPMlt;/SUP;SPMgt;;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;;SPMamp;#8805;;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;LEFT;SPMquot;;SPMgt;;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img14.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math10#<tex2html_image_mark>#tex2html_wrap_indisplay424#
;SPMquot;;SPMgt;;SPMlt;/TD;SPMgt;
;SPMlt;/TR;SPMgt;
;SPMlt;TR VALIGN=;SPMquot;MIDDLE;SPMquot;;SPMgt;;SPMlt;TD ALIGN=;SPMquot;LEFT;SPMquot;;SPMgt;;SPMamp;#8660;;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;RIGHT;SPMquot;;SPMgt;;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img16.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math11#<tex2html_image_mark>#tex2html_wrap_indisplay426#
;SPMquot;;SPMgt;;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;;SPMamp;#8805;;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;LEFT;SPMquot;;SPMgt;;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img17.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math12#<tex2html_image_mark>#tex2html_wrap_indisplay428#
;SPMquot;;SPMgt;;SPMlt;/TD;SPMgt;
;SPMlt;/TR;SPMgt;
;SPMlt;TR VALIGN=;SPMquot;MIDDLE;SPMquot;;SPMgt;;SPMlt;TD ALIGN=;SPMquot;LEFT;SPMquot;;SPMgt;or ;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;RIGHT;SPMquot;;SPMgt;(;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img16.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math13#<tex2html_image_mark>#tex2html_wrap_indisplay430#
;SPMquot;;SPMgt;);SPMlt;I;SPMgt;n;SPMlt;/I;SPMgt;;SPMlt;SUP;SPMgt;2;SPMlt;/SUP;SPMgt; -2;SPMlt;I;SPMgt;n;SPMlt;/I;SPMgt; - (;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img16.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math14#<tex2html_image_mark>#tex2html_wrap_indisplay432#
;SPMquot;;SPMgt;);SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;;SPMamp;#8805;;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;LEFT;SPMquot;;SPMgt;0;SPMlt;/TD;SPMgt;
;SPMlt;/TR;SPMgt;
;SPMlt;/TABLE;SPMgt;
;SPMlt;/DIV;SPMgt;;SPMlt;P;SPMgt;;SPMlt;/P;SPMgt;

<P>
;SPMlt;P;SPMgt;
;SPMamp;gt;From the quadratic equation above, we finally get an expression for ;SPMlt;I;SPMgt;n;SPMlt;/I;SPMgt;,
;SPMlt;P;SPMgt;;SPMlt;!-- MATH
 <P><tex2html_verbatim_mark>#math15#</P><DIV ALIGN="CENTER">
<I>n</I> &nbsp; = &nbsp;<tex2html_image_mark>#tex2html_wrap_indisplay434#
 &nbsp; = &nbsp;<tex2html_image_mark>#tex2html_wrap_indisplay435#

</DIV><P></P>
 --;SPMgt;
;SPMlt;/P;SPMgt;;SPMlt;DIV ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;
;SPMlt;I;SPMgt;n;SPMlt;/I;SPMgt; ;SPMamp;nbsp; = ;SPMamp;nbsp;;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img18.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math16#<tex2html_image_mark>#tex2html_wrap_indisplay437#
;SPMquot;;SPMgt; ;SPMamp;nbsp; = ;SPMamp;nbsp;;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img19.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math17#<tex2html_image_mark>#tex2html_wrap_indisplay439#
;SPMquot;;SPMgt;
;SPMlt;/DIV;SPMgt;;SPMlt;P;SPMgt;;SPMlt;/P;SPMgt;

<P>
;SPMlt;P;SPMgt;
Only the +ve root interests us since ;SPMlt;I;SPMgt;n;SPMlt;/I;SPMgt; has to be positive.
Note that the term under the root is  bounded above and below (since
;SPMlt;!-- MATH
 <tex2html_verbatim_mark>#math18#<tex2html_image_mark>#tex2html_wrap_inline441#
&#8804;1
 --;SPMgt;
;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img20.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math19#<tex2html_image_mark>#tex2html_wrap_inline443#
;SPMquot;;SPMgt;;SPMamp;#8804;1):
;SPMlt;P;SPMgt;;SPMlt;!-- MATH
 <P><tex2html_verbatim_mark>#math20#</P><DIV ALIGN="CENTER">
1 &nbsp;&#8804; &nbsp;<tex2html_image_mark>#tex2html_wrap_indisplay445#
 &nbsp;&#8804; &nbsp;<tex2html_image_mark>#tex2html_wrap_indisplay446#

</DIV><P></P>
 --;SPMgt;
;SPMlt;/P;SPMgt;;SPMlt;DIV ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;
1 ;SPMamp;nbsp;;SPMamp;#8804; ;SPMamp;nbsp;;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img21.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math21#<tex2html_image_mark>#tex2html_wrap_indisplay448#
;SPMquot;;SPMgt; ;SPMamp;nbsp;;SPMamp;#8804; ;SPMamp;nbsp;;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img22.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math22#<tex2html_image_mark>#tex2html_wrap_indisplay450#
;SPMquot;;SPMgt;
;SPMlt;/DIV;SPMgt;;SPMlt;P;SPMgt;;SPMlt;/P;SPMgt;

<P>
;SPMlt;P;SPMgt;
Hence, we have two values for ;SPMlt;I;SPMgt;n;SPMlt;/I;SPMgt;,
;SPMlt;P;SPMgt;;SPMlt;!-- MATH
 <P><tex2html_verbatim_mark>#math23#</P><DIV ALIGN="CENTER">
<I>n</I><SUB>l</SUB> &nbsp; = &nbsp;<tex2html_image_mark>#tex2html_wrap_indisplay452#
 &nbsp; = &nbsp;<tex2html_image_mark>#tex2html_wrap_indisplay453#
; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<I>n</I><SUB>u</SUB> &nbsp; = &nbsp;<tex2html_image_mark>#tex2html_wrap_indisplay454#
 &nbsp; = &nbsp;<tex2html_image_mark>#tex2html_wrap_indisplay455#

</DIV><P></P>
 --;SPMgt;
;SPMlt;/P;SPMgt;;SPMlt;DIV ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;
;SPMlt;I;SPMgt;n;SPMlt;/I;SPMgt;;SPMlt;SUB;SPMgt;l;SPMlt;/SUB;SPMgt; ;SPMamp;nbsp; = ;SPMamp;nbsp;;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img23.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math24#<tex2html_image_mark>#tex2html_wrap_indisplay457#
;SPMquot;;SPMgt; ;SPMamp;nbsp; = ;SPMamp;nbsp;;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img24.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math25#<tex2html_image_mark>#tex2html_wrap_indisplay459#
;SPMquot;;SPMgt;; ;SPMamp;nbsp; ;SPMamp;nbsp; ;SPMamp;nbsp; ;SPMamp;nbsp; ;SPMamp;nbsp; ;SPMamp;nbsp; ;SPMamp;nbsp; ;SPMamp;nbsp; ;SPMamp;nbsp; ;SPMamp;nbsp;;SPMlt;I;SPMgt;n;SPMlt;/I;SPMgt;;SPMlt;SUB;SPMgt;u;SPMlt;/SUB;SPMgt; ;SPMamp;nbsp; = ;SPMamp;nbsp;;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img25.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math26#<tex2html_image_mark>#tex2html_wrap_indisplay461#
;SPMquot;;SPMgt; ;SPMamp;nbsp; = ;SPMamp;nbsp;;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img26.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math27#<tex2html_image_mark>#tex2html_wrap_indisplay463#
;SPMquot;;SPMgt;
;SPMlt;/DIV;SPMgt;;SPMlt;P;SPMgt;;SPMlt;/P;SPMgt;
which finally gives us a lower and an upper bound for ;SPMlt;I;SPMgt;c;SPMlt;/I;SPMgt;, the Pythagorean
square-root,
;SPMlt;P;SPMgt;;SPMlt;!-- MATH
 <P><tex2html_verbatim_mark>#math28#</P><DIV ALIGN="CENTER">
<I>a</I> + <tex2html_image_mark>#tex2html_wrap_indisplay465#
 &nbsp;&#8804; &nbsp;<I>c</I> &nbsp;&#8804; &nbsp;<I>a</I> + <tex2html_image_mark>#tex2html_wrap_indisplay466#

</DIV><P></P>
 --;SPMgt;
;SPMlt;/P;SPMgt;;SPMlt;DIV ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;
;SPMlt;I;SPMgt;a;SPMlt;/I;SPMgt; + ;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img27.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math29#<tex2html_image_mark>#tex2html_wrap_indisplay468#
;SPMquot;;SPMgt; ;SPMamp;nbsp;;SPMamp;#8804; ;SPMamp;nbsp;;SPMlt;I;SPMgt;c;SPMlt;/I;SPMgt; ;SPMamp;nbsp;;SPMamp;#8804; ;SPMamp;nbsp;;SPMlt;I;SPMgt;a;SPMlt;/I;SPMgt; + ;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img28.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math30#<tex2html_image_mark>#tex2html_wrap_indisplay470#
;SPMquot;;SPMgt;
;SPMlt;/DIV;SPMgt;;SPMlt;P;SPMgt;;SPMlt;/P;SPMgt;

<P>
;SPMlt;P;SPMgt;
These are very tight bounds. Denoting the lower bound as ;SPMlt;I;SPMgt;c;SPMlt;/I;SPMgt;;SPMlt;SUB;SPMgt;l;SPMlt;/SUB;SPMgt; and upper
one ;SPMlt;I;SPMgt;c;SPMlt;/I;SPMgt;;SPMlt;SUB;SPMgt;u;SPMlt;/SUB;SPMgt;, below are some numerical results (;SPMlt;I;SPMgt;c;SPMlt;/I;SPMgt; = exact square-root):

<P>
;SPMlt;P;SPMgt;
;SPMlt;DIV class=;SPMquot;CENTER;SPMquot;;SPMgt;
;SPMlt;TABLE CELLPADDING=3 BORDER=;SPMquot;1;SPMquot;;SPMgt;
;SPMlt;TR;SPMgt;;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;a;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;b;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;c;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;;SPMlt;I;SPMgt;c;SPMlt;/I;SPMgt;;SPMlt;SUB;SPMgt;l;SPMlt;/SUB;SPMgt;;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;;SPMlt;I;SPMgt;c;SPMlt;/I;SPMgt;;SPMlt;SUB;SPMgt;u;SPMlt;/SUB;SPMgt;;SPMlt;/TD;SPMgt;
;SPMlt;/TR;SPMgt;
;SPMlt;TR;SPMgt;;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;100.0;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;100.0;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;141.4213;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;141.4213;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;150.0;SPMlt;/TD;SPMgt;
;SPMlt;/TR;SPMgt;
;SPMlt;TR;SPMgt;;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;100.0;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;;SPMamp;nbsp;80.0;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;128.0642;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;126.5096;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;132.0;SPMlt;/TD;SPMgt;
;SPMlt;/TR;SPMgt;
;SPMlt;TR;SPMgt;;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;;SPMamp;nbsp;30.0;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;;SPMamp;nbsp;20.0;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;;SPMamp;nbsp;36.0555;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;35.5228;SPMlt;/TD;SPMgt;
;SPMlt;TD ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;36.6667;SPMlt;/TD;SPMgt;
;SPMlt;/TR;SPMgt;
;SPMlt;/TABLE;SPMgt;
;SPMlt;/DIV;SPMgt;

<P>
;SPMlt;P;SPMgt;
With the above bounds, one can do a linear interpolation to get exact values.
In our case, since it is not required to be ;SPMlt;I;SPMgt;extremely;SPMlt;/I;SPMgt; 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.

<P>
;SPMlt;P;SPMgt;
With some algebra, we get the mid-point estimate of ;SPMlt;I;SPMgt;c;SPMlt;/I;SPMgt;,
;SPMlt;P;SPMgt;;SPMlt;!-- MATH
 <P><tex2html_verbatim_mark>#math31#</P><DIV ALIGN="CENTER">
<I>c</I> = <tex2html_image_mark>#tex2html_wrap_indisplay472#
 = <I>a</I> + <tex2html_image_mark>#tex2html_wrap_indisplay473#
 = <I>a</I> + <tex2html_image_mark>#tex2html_wrap_indisplay474#
 &nbsp; &nbsp; &nbsp; &nbsp;(<I>a</I>&#8805;<I>b</I>)
</DIV><P></P>
 --;SPMgt;
;SPMlt;/P;SPMgt;;SPMlt;DIV ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;
;SPMlt;I;SPMgt;c;SPMlt;/I;SPMgt; = ;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img29.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math32#<tex2html_image_mark>#tex2html_wrap_indisplay476#
;SPMquot;;SPMgt; = ;SPMlt;I;SPMgt;a;SPMlt;/I;SPMgt; + ;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img30.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math33#<tex2html_image_mark>#tex2html_wrap_indisplay478#
;SPMquot;;SPMgt; = ;SPMlt;I;SPMgt;a;SPMlt;/I;SPMgt; + ;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img31.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math34#<tex2html_image_mark>#tex2html_wrap_indisplay480#
;SPMquot;;SPMgt; ;SPMamp;nbsp; ;SPMamp;nbsp; ;SPMamp;nbsp; ;SPMamp;nbsp;(;SPMlt;I;SPMgt;a;SPMlt;/I;SPMgt;;SPMamp;#8805;;SPMlt;I;SPMgt;b;SPMlt;/I;SPMgt;)
;SPMlt;/DIV;SPMgt;;SPMlt;P;SPMgt;;SPMlt;/P;SPMgt;

<P>
;SPMlt;P;SPMgt;
The macro ;SPMlt;code;SPMgt;;SPMlt;/code;SPMgt; uses the above formula for estimating the
number of points (for ;SPMlt;code;SPMgt;;SPMlt;/code;SPMgt; macro) and number of segments (for
;SPMlt;code;SPMgt;;SPMlt;/code;SPMgt; macro). The ;SPMlt;code;SPMgt;;SPMlt;/code;SPMgt; macro, instead of
calculating the length of the line, directly calculates the ;SPMlt;I;SPMgt;number;SPMlt;/I;SPMgt; of
segments of a given length. For example, to draw a dotted line from
(;SPMlt;I;SPMgt;x;SPMlt;/I;SPMgt;;SPMlt;SUB;SPMgt;1;SPMlt;/SUB;SPMgt;, ;SPMlt;I;SPMgt;y;SPMlt;/I;SPMgt;;SPMlt;SUB;SPMgt;1;SPMlt;/SUB;SPMgt;) to (;SPMlt;I;SPMgt;x;SPMlt;/I;SPMgt;;SPMlt;SUB;SPMgt;2;SPMlt;/SUB;SPMgt;, ;SPMlt;I;SPMgt;y;SPMlt;/I;SPMgt;;SPMlt;SUB;SPMgt;2;SPMlt;/SUB;SPMgt;) with the inter-dot-gap as ;SPMlt;I;SPMgt;d;SPMlt;/I;SPMgt;, we estimate the
number of dots ;SPMlt;I;SPMgt;n;SPMlt;/I;SPMgt; using the following expression,
;SPMlt;P;SPMgt;;SPMlt;!-- MATH
 <P><tex2html_verbatim_mark>#math35#</P><DIV ALIGN="CENTER">
<I>n</I> = <tex2html_image_mark>#tex2html_wrap_indisplay482#
 + <tex2html_image_mark>#tex2html_wrap_indisplay483#
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<I>&#916;x</I> = | <I>x</I><SUB>2</SUB> - <I>x</I><SUB>1</SUB>|<#1#> and <#1#><I>&#916;y</I> = | <I>y</I><SUB>2</SUB> - <I>y</I><SUB>1</SUB>|
</DIV><P></P>
 --;SPMgt;
;SPMlt;/P;SPMgt;;SPMlt;DIV ALIGN=;SPMquot;CENTER;SPMquot;;SPMgt;
;SPMlt;I;SPMgt;n;SPMlt;/I;SPMgt; = ;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img32.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math36#<tex2html_image_mark>#tex2html_wrap_indisplay485#
;SPMquot;;SPMgt; + ;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img33.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math37#<tex2html_image_mark>#tex2html_wrap_indisplay487#
;SPMquot;;SPMgt; ;SPMamp;nbsp; ;SPMamp;nbsp; ;SPMamp;nbsp; ;SPMamp;nbsp; ;SPMamp;nbsp; ;SPMamp;nbsp; ;SPMamp;nbsp;;SPMlt;I;SPMgt;;SPMamp;#916;x;SPMlt;/I;SPMgt; = | ;SPMlt;I;SPMgt;x;SPMlt;/I;SPMgt;;SPMlt;SUB;SPMgt;2;SPMlt;/SUB;SPMgt; - ;SPMlt;I;SPMgt;x;SPMlt;/I;SPMgt;;SPMlt;SUB;SPMgt;1;SPMlt;/SUB;SPMgt;| and ;SPMlt;I;SPMgt;;SPMamp;#916;y;SPMlt;/I;SPMgt; = | ;SPMlt;I;SPMgt;y;SPMlt;/I;SPMgt;;SPMlt;SUB;SPMgt;2;SPMlt;/SUB;SPMgt; - ;SPMlt;I;SPMgt;y;SPMlt;/I;SPMgt;;SPMlt;SUB;SPMgt;1;SPMlt;/SUB;SPMgt;|
;SPMlt;/DIV;SPMgt;;SPMlt;P;SPMgt;;SPMlt;/P;SPMgt;
assuming ;SPMlt;!-- MATH
 <tex2html_verbatim_mark>#math38#<I>&#916;x</I>&#8805;<I>&#916;y</I>
 --;SPMgt;
;SPMlt;I;SPMgt;;SPMamp;#916;x;SPMlt;/I;SPMgt;;SPMamp;#8805;;SPMlt;I;SPMgt;;SPMamp;#916;y;SPMlt;/I;SPMgt; (otherwise they may be inter-changed).

<P>
;SPMlt;P;SPMgt;
Note that since divisions in T;SPMlt;SMALL;SPMgt;E;SPMlt;/SMALL;SPMgt;X are integer-divisions, it is simpler to
deal in ``number of segments'' rather than actual lengths
(e.g. in the expression above, ;SPMlt;!-- MATH
 <tex2html_verbatim_mark>#math39#<tex2html_image_mark>#tex2html_wrap_inline490#
 =
 --;SPMgt;
;SPMlt;IMG
 STYLE=;SPMquot;;SPMquot; SRC=;SPMquot;img34.png;SPMquot;
 ALT=;SPMquot;<tex2html_verbatim_mark>#math40#<tex2html_image_mark>#tex2html_wrap_inline492#
;SPMquot;;SPMgt; = number of segments
along X-axis).

<P>
;SPMlt;P;SPMgt;

<P>
;SPMlt;B;SPMgt;Caveat:;SPMlt;/B;SPMgt; The approach presented here for estimation of
Pythagorean square-root is an independent effort by the author. It may
already exist in the literature ;SPMamp;mdash; the author is neither aware of it nor has
he made any serious attempts at uncovering it.

<P>
;SPMlt;P;SPMgt;

<P>
;SPMlt;HR;SPMgt;

<P>
;SPMlt;/BODY;SPMgt;
;SPMlt;/HTML;SPMgt;