htdocs/phpcgibin/brap.php

<?php
if (!$ARBINT_INCLUDED)
   {
   include("Arbint.inc");
   $ARBINT_INCLUDED=1;
   }
if (!$STDNWPSTYLE_INCLUDED)
   {
   include("Stdnwpstyle.inc");
   $STDNWPSTYLE_INCLUDED=1;
   }
?>
<?php
function do_header(&$style)
   {
   $style->header_title("GCD Calculator (Euclid's Algorithm)",
                          "GCD Calculator",
                          "This cgi-bin form calculates the greatest common divisor of two positive " .
                          "integers using " .
                          "<a href=\"http://mathworld.wolfram.com/EuclideanAlgorithm.html\">Euclid's classic algorithm</a>.");
   }  

function do_footer(&$style)
   {
   $style->footer_std();
   }

function do_form($N1_refresh, $N2_refresh, $Buttontext)
   {
   echo "<form method=get action=\"euclid_gcd.php\" width=\"100%\">\n";
   echo "<table align=\"center\">\n";
   echo "<tr>\n";
   echo "  <td width=\"10%\">\n";
   echo "   <p align=\"right\"><b>N1</b> (arbitrary length):</td>\n";
   echo "    <td width=\"18%\"><p align=\"left\"><input type=\"text\" ";
   if (strlen($N1_refresh))
     {
     echo "value=\"" . $N1_refresh . "\" ";
     }
   echo "name=\"N1\" size=\"50\"></p></td>\n";
   echo "  </tr>\n";
   echo "  <tr>\n";
   echo "    <td width=\"10%\">\n";
   echo "   <p align=\"right\"><b>N2</b> (arbitrary length):</td>\n";
   echo "    <td width=\"18%\"><p align=\"left\"><input type=\"text\" ";
   if (strlen($N2_refresh))
     {
     echo "value=\"" . $N2_refresh . "\" ";
     }
   echo "name=\"N2\" size=\"50\"></p></td>\n";
   echo "  </tr>\n";
   echo "  <tr>\n";
   echo "    <td width=\"20%\" colspan=\"2\">\n";
   echo "      <p align=\"center\"><input type=\"submit\" value=\"";
   echo $Buttontext;
   echo "\" name=\"B1\" style=\"margin-top: 12\"></td>\n";
   echo "  </tr>\n";
   echo "</table>\n";
   echo "</form>\n";
}

function do_err_msg($Err_msg)
   {
   echo "<p align=\"center\"><b><font color=\"#FF0000\">";
   echo $Err_msg;
   echo "</font></b></p>\n";
   }


//Main script begins here.
//
//
$style = new Stdnwpstyle;
//Assign the current style in force.  Also, starts the CPU
//usage clock.

//Do the header unconditionally.  The header is always used on this page.
do_header($style);
//
//
//If N1 was supplied, decommanate it and be sure it is a string.
if (isset($N1))
   Arbint_decommanate($N1);

//Same for N2.
if (isset($N2))
   Arbint_decommanate($N2);
//
//There are a few cases to break into here, and this affects the overall layout of the page.
//The header and footer are fixed, but the "guts" will change.
if (!isset($N1) && !isset($N2))
   {
   //In this case, we are probably visiting the form for the first time, and have not done a submit.
   //Just display the form itself.
   do_form("", "", "Calculate GCD");
   }
elseif (!isset($N1) && isset($N2))
   {
   //Only $N2 is supplied.
     do_err_msg("You must supply both N1 and N2 to calculate a GCD. &nbsp;Only N2 was supplied.  &nbsp;Please try again.");
     $style->hrule_std();
     Arbint_commanate($N2);  
     do_form("", $N2, "Calculate GCD");
   }  
elseif (isset($N1) && !isset($N2))
   {
   //Only $N1 is supplied.
     do_err_msg("You must supply both N1 and N2 to calculate a GCD. &nbsp;Only N1 was supplied.  &nbsp;Please try again.");
     $style->hrule_std();  
     Arbint_commanate($N1);
     do_form($N1, "", "Calculate GCD");
   }  
elseif (!Arbint_issimpleint($N1) || !Arbint_issimpleint($N2))
   {
   //$N1 and $N2 are both supplied, but one or both is malformed.  Need to advise.
   if (!Arbint_issimpleint($N1) && !Arbint_issimpleint($N2))
      {
      do_err_msg("N1 and N2 are both malformed integers. &nbsp;Choose new values and try again.");
      $style->hrule_std();  
      do_form($N1, $N2, "Calculate GCD");
      }
   elseif (!Arbint_issimpleint($N1))
      {
      do_err_msg("N1 is a malformed integer. &nbsp;Choose a new value for N1 and try again.");
      $style->hrule_std();  
      Arbint_commanate($N2);
      do_form($N1, $N2, "Calculate GCD");
      }
   else
      {
      do_err_msg("N2 is a malformed integer. &nbsp;Choose a new value for N2 and try again.");
      $style->hrule_std();  
      Arbint_commanate($N1);
      do_form($N1, $N2, "Calculate GCD");
      } 
   }  
else
   {
   //N1 and N2 were both supplied and seem to be valid integers.
   //
   //If either integer is negative, make it positive.
   if (Substr($N1, 0, 1)=="-")
     $N1 = Substr($N1, 1, strlen($N1)-1);
   if (Substr($N2, 0, 1)=="-")
     $N2 = Substr($N2, 1, strlen($N2)-1);

   //If either is "0", make it "1".
   if ($N1=="0")
     $N1 = (string)"1";
   if ($N2=="0")
     $N2 = (string)"1";

   $cur_a   = new Arbint;
   $cur_b   = new Arbint;
   $cur_div = new Arbint;
   $cur_mod = new Arbint;

   $cur_a->assign($N1);
   $cur_b->assign($N2);

   //If b>a, then swap them.
   if (Arbint_cmp($cur_a, $cur_b) < 0)
      {
      $temp = $cur_a;
      $cur_a = $cur_b;
      $cur_b = $temp;
      }

   $round = 0;
   do
      {
      $round++;

      $cur_div->div($cur_a, $cur_b);
      $cur_mod->mod($cur_a, $cur_b);

      $a[$round]     = $cur_a->get_digits();
      Arbint_commanate($a[$round]);
      $b[$round]     = $cur_b->get_digits();
      Arbint_commanate($b[$round]);
      $adivb[$round] = $cur_div->get_digits();
      Arbint_commanate($adivb[$round]);
      $amodb[$round] = $cur_mod->get_digits();
      Arbint_commanate($amodb[$round]);

      $cur_a = $cur_b;
      $cur_b = $cur_mod;      
      }
   while($amodb[$round] != 0);

   echo "<p align=\"center\"><font size=\"4\">The greatest common divisor of ";
   echo $a[1];
   echo " and ";
   echo $b[1];
   echo " is ";
   if ($round == 1)
      echo $b[1];
   else
      echo $amodb[$round - 1];
   echo ".</font></p>\n";

   $style->hrule_std();  

   echo "<p align=\"left\"><b>Notes on the algorithm: &nbsp;</b>\n";
   echo "Euclid's classic GCD algorithm was known no later than about 200 B.C. and is documented \n";
   echo "at the \n";
   echo "<a href=\"http://mathworld.wolfram.com/EuclideanAlgorithm.html\">Wolfram Research site</a> \n";
   echo "and also in Knuth's classic reference work, ";
   echo "<a href=\"http://www.amazon.com/exec/obidos/tg/detail/-/0201896842/qid=1041826693/sr=8-2/ref=sr_8_2/102-1371170-8580943?v=glance&s=books&n=507846\"><i>The \n";
   echo "Art Of Computer Programming</i></a>. &nbsp;Euclid's GCD algorithm ends with the GCD being the \n";
   echo "last non-zero remainder (in yellow below unless <i>a</i> is a multiple of <i>b</i>).\n";
   echo "</p>\n";

   //Assign the table column widths.  They are centralized here for easy change.
   $width[0] = 5;
   $width[1] = 10;
   $width[2] = 10;
   $width[3] = 10;
   $width[4] = 10;

   echo "<table align=\"center\" border=\"1\" width=\"90%\">\n";

   for ($i=0; $i<=$round; $i++)
      {
      echo "<tr>\n";

      echo "   <td width=\"" . $width[0] . "%\">\n";
      if ($i==0)
        {
        echo "      <p align=\"center\"><b>Round</b></p>\n";
        }
      else
        {
        echo "      <p align=\"center\">" . $i . "</p>\n";
        }
      echo "   </td>\n";

      echo "   <td width=\"" . $width[1] . "%\">\n";
      if ($i==0)
        {
        echo "      <p align=\"center\"><b>a</b></p>\n";
        }
      else
        {
        echo "      <p align=\"right\">" . $a[$i] . "</p>\n";
        }
      echo "   </td>\n";

      echo "   <td width=\"" . $width[2] . "%\">\n";
      if ($i==0)
        {
        echo "      <p align=\"center\"><b>b</b></p>\n";
        }
      else
        {
        echo "      <p align=\"right\">" . $b[$i] . "</p>\n";
        }
      echo "   </td>\n";

      echo "   <td width=\"" . $width[3] . "%\">\n";
      if ($i==0)
        {
        echo "      <p align=\"center\"><b>a <i>div</i> b</b></p>\n";
        }
      else
        {
        echo "      <p align=\"right\">" . $adivb[$i] . "</p>\n";
        }
      echo "   </td>\n";

      echo "   <td width=\"" . $width[4] . "%\"";
      if ($round > 1 && ($i == ($round-1)))
         echo " bgcolor=\"#FFFF00\"";      
      echo ">\n";
      if ($i==0)
        {
        echo "      <p align=\"center\"><b>a <i>mod</i> b</b></p>\n";
        }
      else
        {
        echo "      <p align=\"right\">" . $amodb[$i] . "</p>\n";
        }
      echo "   </td>\n";

      echo "</tr>\n";
      }

   echo "</table><br>\n";
   $style->hrule_std();  

   Arbint_commanate($N1);
   Arbint_commanate($N2);
   do_form($N1, $N2, "Calculate Another GCD");
   }

//Now do the footer unconditionally.  The footer is always used on this web page.
do_footer($style);  
?>
1	dashley	23	<?php
2			if (!$ARBINT_INCLUDED)
3			{
4			include("Arbint.inc");
5			$ARBINT_INCLUDED=1;
6			}
7			if (!$STDNWPSTYLE_INCLUDED)
8			{
9			include("Stdnwpstyle.inc");
10			$STDNWPSTYLE_INCLUDED=1;
11			}
12			?>
13			<?php
14			function do_header(&$style)
15			{
16			$style->header_title("GCD Calculator (Euclid's Algorithm)",
17			"GCD Calculator",
18			"This cgi-bin form calculates the greatest common divisor of two positive " .
19			"integers using " .
20			"<a href=\"http://mathworld.wolfram.com/EuclideanAlgorithm.html\">Euclid's classic algorithm</a>.");
21			}
22
23			function do_footer(&$style)
24			{
25			$style->footer_std();
26			}
27
28			function do_form($N1_refresh, $N2_refresh, $Buttontext)
29			{
30			echo "<form method=get action=\"euclid_gcd.php\" width=\"100%\">\n";
31			echo "<table align=\"center\">\n";
32			echo "<tr>\n";
33			echo " <td width=\"10%\">\n";
34			echo " <p align=\"right\"><b>N1</b> (arbitrary length):</td>\n";
35			echo " <td width=\"18%\"><p align=\"left\"><input type=\"text\" ";
36			if (strlen($N1_refresh))
37			{
38			echo "value=\"" . $N1_refresh . "\" ";
39			}
40			echo "name=\"N1\" size=\"50\"></p></td>\n";
41			echo " </tr>\n";
42			echo " <tr>\n";
43			echo " <td width=\"10%\">\n";
44			echo " <p align=\"right\"><b>N2</b> (arbitrary length):</td>\n";
45			echo " <td width=\"18%\"><p align=\"left\"><input type=\"text\" ";
46			if (strlen($N2_refresh))
47			{
48			echo "value=\"" . $N2_refresh . "\" ";
49			}
50			echo "name=\"N2\" size=\"50\"></p></td>\n";
51			echo " </tr>\n";
52			echo " <tr>\n";
53			echo " <td width=\"20%\" colspan=\"2\">\n";
54			echo " <p align=\"center\"><input type=\"submit\" value=\"";
55			echo $Buttontext;
56			echo "\" name=\"B1\" style=\"margin-top: 12\"></td>\n";
57			echo " </tr>\n";
58			echo "</table>\n";
59			echo "</form>\n";
60			}
61
62			function do_err_msg($Err_msg)
63			{
64			echo "<p align=\"center\"><b><font color=\"#FF0000\">";
65			echo $Err_msg;
66			echo "</font></b></p>\n";
67			}
68
69
70			//Main script begins here.
71			//
72			//
73			$style = new Stdnwpstyle;
74			//Assign the current style in force. Also, starts the CPU
75			//usage clock.
76
77			//Do the header unconditionally. The header is always used on this page.
78			do_header($style);
79			//
80			//
81			//If N1 was supplied, decommanate it and be sure it is a string.
82			if (isset($N1))
83			Arbint_decommanate($N1);
84
85			//Same for N2.
86			if (isset($N2))
87			Arbint_decommanate($N2);
88			//
89			//There are a few cases to break into here, and this affects the overall layout of the page.
90			//The header and footer are fixed, but the "guts" will change.
91			if (!isset($N1) && !isset($N2))
92			{
93			//In this case, we are probably visiting the form for the first time, and have not done a submit.
94			//Just display the form itself.
95			do_form("", "", "Calculate GCD");
96			}
97			elseif (!isset($N1) && isset($N2))
98			{
99			//Only $N2 is supplied.
100			do_err_msg("You must supply both N1 and N2 to calculate a GCD.  Only N2 was supplied.  Please try again.");
101			$style->hrule_std();
102			Arbint_commanate($N2);
103			do_form("", $N2, "Calculate GCD");
104			}
105			elseif (isset($N1) && !isset($N2))
106			{
107			//Only $N1 is supplied.
108			do_err_msg("You must supply both N1 and N2 to calculate a GCD.  Only N1 was supplied.  Please try again.");
109			$style->hrule_std();
110			Arbint_commanate($N1);
111			do_form($N1, "", "Calculate GCD");
112			}
113			elseif (!Arbint_issimpleint($N1) \|\| !Arbint_issimpleint($N2))
114			{
115			//$N1 and $N2 are both supplied, but one or both is malformed. Need to advise.
116			if (!Arbint_issimpleint($N1) && !Arbint_issimpleint($N2))
117			{
118			do_err_msg("N1 and N2 are both malformed integers.  Choose new values and try again.");
119			$style->hrule_std();
120			do_form($N1, $N2, "Calculate GCD");
121			}
122			elseif (!Arbint_issimpleint($N1))
123			{
124			do_err_msg("N1 is a malformed integer.  Choose a new value for N1 and try again.");
125			$style->hrule_std();
126			Arbint_commanate($N2);
127			do_form($N1, $N2, "Calculate GCD");
128			}
129			else
130			{
131			do_err_msg("N2 is a malformed integer.  Choose a new value for N2 and try again.");
132			$style->hrule_std();
133			Arbint_commanate($N1);
134			do_form($N1, $N2, "Calculate GCD");
135			}
136			}
137			else
138			{
139			//N1 and N2 were both supplied and seem to be valid integers.
140			//
141			//If either integer is negative, make it positive.
142			if (Substr($N1, 0, 1)=="-")
143			$N1 = Substr($N1, 1, strlen($N1)-1);
144			if (Substr($N2, 0, 1)=="-")
145			$N2 = Substr($N2, 1, strlen($N2)-1);
146
147			//If either is "0", make it "1".
148			if ($N1=="0")
149			$N1 = (string)"1";
150			if ($N2=="0")
151			$N2 = (string)"1";
152
153			$cur_a = new Arbint;
154			$cur_b = new Arbint;
155			$cur_div = new Arbint;
156			$cur_mod = new Arbint;
157
158			$cur_a->assign($N1);
159			$cur_b->assign($N2);
160
161			//If b>a, then swap them.
162			if (Arbint_cmp($cur_a, $cur_b) < 0)
163			{
164			$temp = $cur_a;
165			$cur_a = $cur_b;
166			$cur_b = $temp;
167			}
168
169			$round = 0;
170			do
171			{
172			$round++;
173
174			$cur_div->div($cur_a, $cur_b);
175			$cur_mod->mod($cur_a, $cur_b);
176
177			$a[$round] = $cur_a->get_digits();
178			Arbint_commanate($a[$round]);
179			$b[$round] = $cur_b->get_digits();
180			Arbint_commanate($b[$round]);
181			$adivb[$round] = $cur_div->get_digits();
182			Arbint_commanate($adivb[$round]);
183			$amodb[$round] = $cur_mod->get_digits();
184			Arbint_commanate($amodb[$round]);
185
186			$cur_a = $cur_b;
187			$cur_b = $cur_mod;
188			}
189			while($amodb[$round] != 0);
190
191			echo "<p align=\"center\"><font size=\"4\">The greatest common divisor of ";
192			echo $a[1];
193			echo " and ";
194			echo $b[1];
195			echo " is ";
196			if ($round == 1)
197			echo $b[1];
198			else
199			echo $amodb[$round - 1];
200			echo ".</font></p>\n";
201
202			$style->hrule_std();
203
204			echo "<p align=\"left\"><b>Notes on the algorithm:  </b>\n";
205			echo "Euclid's classic GCD algorithm was known no later than about 200 B.C. and is documented \n";
206			echo "at the \n";
207			echo "<a href=\"http://mathworld.wolfram.com/EuclideanAlgorithm.html\">Wolfram Research site</a> \n";
208			echo "and also in Knuth's classic reference work, ";
209			echo "<a href=\"http://www.amazon.com/exec/obidos/tg/detail/-/0201896842/qid=1041826693/sr=8-2/ref=sr_8_2/102-1371170-8580943?v=glance&s=books&n=507846\"><i>The \n";
210			echo "Art Of Computer Programming</i></a>.  Euclid's GCD algorithm ends with the GCD being the \n";
211			echo "last non-zero remainder (in yellow below unless <i>a</i> is a multiple of <i>b</i>).\n";
212			echo "</p>\n";
213
214			//Assign the table column widths. They are centralized here for easy change.
215			$width[0] = 5;
216			$width[1] = 10;
217			$width[2] = 10;
218			$width[3] = 10;
219			$width[4] = 10;
220
221			echo "<table align=\"center\" border=\"1\" width=\"90%\">\n";
222
223			for ($i=0; $i<=$round; $i++)
224			{
225			echo "<tr>\n";
226
227			echo " <td width=\"" . $width[0] . "%\">\n";
228			if ($i==0)
229			{
230			echo " <p align=\"center\"><b>Round</b></p>\n";
231			}
232			else
233			{
234			echo " <p align=\"center\">" . $i . "</p>\n";
235			}
236			echo " </td>\n";
237
238			echo " <td width=\"" . $width[1] . "%\">\n";
239			if ($i==0)
240			{
241			echo " <p align=\"center\"><b>a</b></p>\n";
242			}
243			else
244			{
245			echo " <p align=\"right\">" . $a[$i] . "</p>\n";
246			}
247			echo " </td>\n";
248
249			echo " <td width=\"" . $width[2] . "%\">\n";
250			if ($i==0)
251			{
252			echo " <p align=\"center\"><b>b</b></p>\n";
253			}
254			else
255			{
256			echo " <p align=\"right\">" . $b[$i] . "</p>\n";
257			}
258			echo " </td>\n";
259
260			echo " <td width=\"" . $width[3] . "%\">\n";
261			if ($i==0)
262			{
263			echo " <p align=\"center\"><b>a <i>div</i> b</b></p>\n";
264			}
265			else
266			{
267			echo " <p align=\"right\">" . $adivb[$i] . "</p>\n";
268			}
269			echo " </td>\n";
270
271			echo " <td width=\"" . $width[4] . "%\"";
272			if ($round > 1 && ($i == ($round-1)))
273			echo " bgcolor=\"#FFFF00\"";
274			echo ">\n";
275			if ($i==0)
276			{
277			echo " <p align=\"center\"><b>a <i>mod</i> b</b></p>\n";
278			}
279			else
280			{
281			echo " <p align=\"right\">" . $amodb[$i] . "</p>\n";
282			}
283			echo " </td>\n";
284
285			echo "</tr>\n";
286			}
287
288			echo "</table><br>\n";
289			$style->hrule_std();
290
291			Arbint_commanate($N1);
292			Arbint_commanate($N2);
293			do_form($N1, $N2, "Calculate Another GCD");
294			}
295
296			//Now do the footer unconditionally. The footer is always used on this web page.
297			do_footer($style);
298			?>