num_theory/euclid_gcd/euclid_gcd.php

<?php
if (!$STDNWPSTYLE_INCLUDED)
   {
   include("stdnwpstyle.inc");
   $STDNWPSTYLE_INCLUDED=1;
   }
?>
<?php
//
//********************************************************************************
//Copyright (C) 2003 David T. Ashley
//********************************************************************************
//This program or source file is free software; you can redistribute it and/or 
//modify it under the terms of the GNU General Public License as published by
//the Free Software Foundation; either version 2 of the License, or (at your 
//option) any later version.
//
//This program or source file is distributed in the hope that it will 
//be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
//MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//GNU General Public License for more details.
//
//You may have received a copy of the GNU General Public License
//along with this program; if not, write to the Free Software
//Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//********************************************************************************
//
//Returns TRUE if the passed argument is a digit, or FALSE otherwise.  If the
//passed string has length > 1, only the least significant digit is
//considered.
function euclid_gcd_isdigit($Digit)
   {
   $Digit = (string)$Digit;

   //If the string has zero length, this is an error condition and return 0.
   $Length = strlen($Digit);  

   if ($Length==0)
      {
      return(0);
      }

   //Obtain the trailing character of the string.
   $Trailing_char = Substr($Digit, $Length-1, 1);

   //Do a switch and return an integer based on the character.
   switch($Trailing_char)
      {
      case "9":
         return 1;
         break;
      case "8":
         return 1;
         break;
      case "7":
         return 1;
         break;
      case "6":
         return 1;
         break;
      case "5":
         return 1;
         break;
      case "4":
         return 1;
         break;
      case "3":
         return 1;
         break;
      case "2":
         return 1;
         break;
      case "1":
         return 1;
         break;
      case "0":
         return 1;
         break;
      default:
         return 0;
         break;
      }
   }
//
//
//Returns TRUE if the passed argument is a simple integer (no error   
//codes, no commas), or FALSE otherwise.
function euclid_gcd_issimpleint($Intnum)
   {
   $Intnum = (string)$Intnum;

   //If the string has zero length, this is an error condition and return 0.
   $Length = strlen($Intnum);  

   if ($Length==0)
      {
      return(0);
      }

   //If the first digit is "0", this must be the only character in the string,
   //otherwise there is a leading-zero violation.
   if (Substr($Intnum, 0, 1)=="0")
      {
      if ($Length==1)
         {
         return 1;
         }
      else
         {
         return 0;
         }
      }

   //If the first character is a "-" sign, it may not be the only character,
   //and it may not precede a "0" (which would again be a leading 0 violation).
   //If it is a "-", we can exclude "0" and parse as a positive.
   if (Substr($Intnum, 0, 1)=="-")
      {
      if ($Length==1)
         {
         return 0;
         }
      else
         {
         if (Substr($Intnum, 1, 1) == "0")
            {
            //This is illegal (a "-" followed by a "0").
            return 0;
            }
         else
            {
            //We can just remove the "-" and parse as a positive.
            $Intnum = Substr($Intnum, 1, $Length - 1);
            $Length--;
            }
         }
      }

   //It is known at this point that the length is at least 1 and the leading 
   //character is not zero.  All we need to do at this point is check that each 
   //and every character is a digit.
   for ($index=0; $index < $Length; $index++)
      {
      if (!euclid_gcd_isdigit(Substr($Intnum, $index, 1)))
         return 0;
      }

   return 1;
   }
//
//
//Returns the number of digits in the argument, which must be a valid simple
//integer.
function euclid_gcd_ndigits($Intnum)
   {
   $Intnum = (string)$Intnum;

   if (Substr($Intnum, 0, 1) == "-")
      {
      $rv = strlen($Intnum) - 1;
      }
   else
      {
      $rv = strlen($Intnum);
      }

   return($rv);
   }
//
//
//Given a string, converts the final character to an integer.  If the character
//is not a digit, returns 0.
function euclid_gcd_digittoint($Digit)
   {
   //echo "Digit is: ";
   //echo $Digit;
   //echo "<br>";

   $Digit = (string)$Digit;

   //echo "Digit is: ";
   //echo $Digit;
   //echo "<br>";
   
   //If the string has zero length, this is an error condition and return 0.
   $Length = strlen($Digit);  

   //echo "Length is: ";
   //echo $Length;
   //echo "<br>";

   if ($Length==0)
      {
      return(0);
      }

   //Obtain the trailing character of the string.
   $Trailing_char = Substr($Digit, $Length-1, 1);

   //echo "Trailing char is: ";
   //echo $Trailing_char;
   //echo "<br>";

   //Do a switch and return an integer based on the character.
   //The default case gives 0.

   switch($Trailing_char)
      {
      case "9":
         return 9;
         break;
      case "8":
         return 8;
         break;
      case "7":
         return 7;
         break;
      case "6":
         return 6;
         break;
      case "5":
         return 5;
         break;
      case "4":
         return 4;
         break;
      case "3":
         return 3;
         break;
      case "2":
         return 2;
         break;
      case "1":
         return 1;
         break;
      default:
         return 0;
         break;
      }
   }

//Decommanates an integer and removes all other crap without respect for 
//whether the commas are in the right place or the integer is syntactically valid.
function euclid_gcd_decommanate(&$arg)
   {
   $temp = "";

   $len = strlen($arg);

   for ($i=0; $i<$len; $i++)
      {
      $c = (string)Substr($arg, $i, 1);
   
      if (euclid_gcd_isdigit($c) || ($c == "-"))
         $temp = $temp . $c;
      }

   $arg = (string)$temp;
   } 

//Commanates an integer which is assumed to by syntactically correct.
function euclid_gcd_commanate(&$arg)
   {
   euclid_gcd_decommanate($arg);
 
   $temp = "";
  
   $len = strlen($arg);

   for ($i=0; $i<$len; $i++)
      {
      $c = (string)Substr($arg, $len - $i - 1, 1);

      $temp = $c . $temp;
      
      if ($i != ($len-1))
         {
         if (Substr($arg, $len-$i-2, 1) != "-")
            {
            if (($i % 3) == 2)
               $temp = "," . $temp;
            }
         }
      }

   $arg = (string)$temp;
   } 

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->hrule_std();
   echo "<p align=\"center\">This utility is powered by the ";
   echo "<a href=\"http://www.swox.com/gmp\"><img hspace=\"5\" vspace=\"5\" src=\"../genimages/gmplogo1.png\" width=\"232\" height=\"104\" align=\"absmiddle\"></a>.&nbsp; All source code is available ";
   echo "<a href=\"../howtos/nth_web_gmp_src_code_dist/obtain_all_source.htm\">here</a>.</p>\n";
   $style->footer_std();
   }

function do_form($N1_refresh, $N2_refresh, $Buttontext, $max_gcd_digits)
   {
   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> (" . number_format($max_gcd_digits) . "-digit maximum):</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> (" . number_format($max_gcd_digits) . "-digit maximum):</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.
//
//
//Let's agree on a maximum for number of digits in either
//of the two arguments.  This has been checked out and seems
//to be within operational parameters (script won't time out).
$max_gcd_digits = 200;
//
$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))
   euclid_gcd_decommanate($N1);

//Same for N2.
if (isset($N2))
   euclid_gcd_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", $max_gcd_digits);
   }
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();
     euclid_gcd_commanate($N2);  
     do_form("", $N2, "Calculate GCD", $max_gcd_digits);
   }  
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();  
     euclid_gcd_commanate($N1);
     do_form($N1, "", "Calculate GCD", $max_gcd_digits);
   }  
elseif (!euclid_gcd_issimpleint($N1) || !euclid_gcd_issimpleint($N2))
   {
   //$N1 and $N2 are both supplied, but one or both is malformed.  Need to advise.
   if (!euclid_gcd_issimpleint($N1) && !euclid_gcd_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", $max_gcd_digits);
      }
   elseif (!euclid_gcd_issimpleint($N1))
      {
      do_err_msg("N1 is a malformed integer. &nbsp;Choose a new value for N1 and try again.");
      $style->hrule_std();  
      euclid_gcd_commanate($N2);
      do_form($N1, $N2, "Calculate GCD", $max_gcd_digits);
      }
   else
      {
      do_err_msg("N2 is a malformed integer. &nbsp;Choose a new value for N2 and try again.");
      $style->hrule_std();  
      euclid_gcd_commanate($N1);
      do_form($N1, $N2, "Calculate GCD", $max_gcd_digits);
      } 
   }  
elseif ((strlen($N1) > $max_gcd_digits) || (strlen($N2) > $max_gcd_digits))
   {
   if ((strlen($N1) > $max_gcd_digits) && (strlen($N2) > $max_gcd_digits))
      {
      do_err_msg("N1 and N2 are both too long (a " . number_format($max_gcd_digits) . "-digit maximum is " .
                 "in effect).&nbsp; Choose shorter values and try again.");
      $style->hrule_std();  
      euclid_gcd_commanate($N1);
      euclid_gcd_commanate($N2);
      do_form($N1, $N2, "Calculate GCD", $max_gcd_digits);
      }
   elseif (strlen($N1) > $max_gcd_digits)
      {
      do_err_msg("N1 is too long (a " . number_format($max_gcd_digits) . "-digit maximum is " .
                 "in effect).&nbsp; Choose a shorter value and try again.");
      $style->hrule_std();  
      euclid_gcd_commanate($N1);
      euclid_gcd_commanate($N2);
      do_form($N1, $N2, "Calculate GCD", $max_gcd_digits);
      }
   else
      {
      do_err_msg("N2 is too long (a " . number_format($max_gcd_digits) . "-digit maximum is " .
                 "in effect).&nbsp; Choose a shorter value and try again.");
      $style->hrule_std();  
      euclid_gcd_commanate($N1);
      euclid_gcd_commanate($N2);
      do_form($N1, $N2, "Calculate GCD", $max_gcd_digits);
      }
   }
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";

   //We can now run the external program to do the calculation.
   $cgi_command_string = "./arith_large_cgi gcd " . $N1 . " " . $N2;
   //echo "CGI command string is : " . $cgi_command_string . "<br>\n";

   exec($cgi_command_string, $cgi_result);
   $cgi_result_nelem = count($cgi_result);

   //echo "Result is : " . $cgi_result_nelem . "<br>\n";

   //for ($i=0; $i<$cgi_result_nelem; $i++)
   //{
   //  echo $cgi_result[$i] . "<br>\n";
   //}

   //We need to perform some sanity checks on the CGI output to be sure it
   //is what we want.  If it seems wrong, we need to generate an error message
   //and not try to display the output.
   $cgi_output_is_sane = 1;
   if ($cgi_result_nelem == 0)
      $cgi_output_is_sane = 0;
   if ($cgi_result_nelem > 0)
      {
      if (($cgi_result_nelem % 5) != 0)
         $cgi_output_is_sane = 0;
      if ($cgi_result[0] != "S")
         $cgi_output_is_sane = 0;
      if ($cgi_result[$cgi_result_nelem - 1] != "S")
         $cgi_output_is_sane = 0;
      }

   if (!$cgi_output_is_sane)
      {
      do_err_msg("An unspecified error occurred when interacting with the CGI-BIN program.&nbsp; Please advise the webmaster.");
      $style->hrule_std();  
      euclid_gcd_commanate($N1);
      euclid_gcd_commanate($N2);
      do_form($N1, $N2, "Calculate GCD", $max_gcd_digits);
      }
   else
      {
      euclid_gcd_commanate($cgi_result[1]);
      euclid_gcd_commanate($cgi_result[2]);
      euclid_gcd_commanate($cgi_result[$cgi_result_nelem - 2]);

      echo "<p align=\"center\"><font size=\"4\">The greatest common divisor of ";
      echo $cgi_result[1];
      echo " and ";
      echo $cgi_result[2];
      echo " is ";
      echo $cgi_result[$cgi_result_nelem - 2];
      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 <= ($cgi_result_nelem/5 - 1); $i++)
         {
         echo "<tr>\n";

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

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

         echo "   <td width=\"" . $width[2] . "%\">\n";
         if ($i==0)
            {
            echo "      <p align=\"center\"><b>b</b></p>\n";
            }
         else
            {
            euclid_gcd_commanate($cgi_result[$i*5]);
            echo "      <p align=\"right\">" . $cgi_result[$i*5] . "</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
            {
            euclid_gcd_commanate($cgi_result[$i*5+1]);
            echo "      <p align=\"right\">" . $cgi_result[$i*5+1] . "</p>\n";
            }
         echo "   </td>\n";

         if ($i > 0)
            euclid_gcd_commanate($cgi_result[$i*5+2]);
         echo "   <td width=\"" . $width[4] . "%\"";
         if (($i > 0) && ($cgi_result[$i*5+2] == $cgi_result[$cgi_result_nelem - 2]))
            echo " bgcolor=\"#FFFF00\"";      
         echo ">\n";
         if ($i==0)
            {
            echo "      <p align=\"center\"><b>a <i>mod</i> b</b></p>\n";
            }
         else
            {
            //euclid_gcd_commanate($cgi_result[$i*5+2]);
            echo "      <p align=\"right\">" . $cgi_result[$i*5+2] . "</p>\n";
            }
         echo "   </td>\n";

         echo "</tr>\n";
         }

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

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

//Now do the footer unconditionally.  The footer is always used on this web page.
do_footer($style);  
?>
1	dashley	23	<?php
2			if (!$STDNWPSTYLE_INCLUDED)
3			{
4			include("stdnwpstyle.inc");
5			$STDNWPSTYLE_INCLUDED=1;
6			}
7			?>
8			<?php
9			//
10			//********************************************************************************
11			//Copyright (C) 2003 David T. Ashley
12			//********************************************************************************
13			//This program or source file is free software; you can redistribute it and/or
14			//modify it under the terms of the GNU General Public License as published by
15			//the Free Software Foundation; either version 2 of the License, or (at your
16			//option) any later version.
17			//
18			//This program or source file is distributed in the hope that it will
19			//be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
20			//MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21			//GNU General Public License for more details.
22			//
23			//You may have received a copy of the GNU General Public License
24			//along with this program; if not, write to the Free Software
25			//Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
26			//********************************************************************************
27			//
28			//Returns TRUE if the passed argument is a digit, or FALSE otherwise. If the
29			//passed string has length > 1, only the least significant digit is
30			//considered.
31			function euclid_gcd_isdigit($Digit)
32			{
33			$Digit = (string)$Digit;
34
35			//If the string has zero length, this is an error condition and return 0.
36			$Length = strlen($Digit);
37
38			if ($Length==0)
39			{
40			return(0);
41			}
42
43			//Obtain the trailing character of the string.
44			$Trailing_char = Substr($Digit, $Length-1, 1);
45
46			//Do a switch and return an integer based on the character.
47			switch($Trailing_char)
48			{
49			case "9":
50			return 1;
51			break;
52			case "8":
53			return 1;
54			break;
55			case "7":
56			return 1;
57			break;
58			case "6":
59			return 1;
60			break;
61			case "5":
62			return 1;
63			break;
64			case "4":
65			return 1;
66			break;
67			case "3":
68			return 1;
69			break;
70			case "2":
71			return 1;
72			break;
73			case "1":
74			return 1;
75			break;
76			case "0":
77			return 1;
78			break;
79			default:
80			return 0;
81			break;
82			}
83			}
84			//
85			//
86			//Returns TRUE if the passed argument is a simple integer (no error
87			//codes, no commas), or FALSE otherwise.
88			function euclid_gcd_issimpleint($Intnum)
89			{
90			$Intnum = (string)$Intnum;
91
92			//If the string has zero length, this is an error condition and return 0.
93			$Length = strlen($Intnum);
94
95			if ($Length==0)
96			{
97			return(0);
98			}
99
100			//If the first digit is "0", this must be the only character in the string,
101			//otherwise there is a leading-zero violation.
102			if (Substr($Intnum, 0, 1)=="0")
103			{
104			if ($Length==1)
105			{
106			return 1;
107			}
108			else
109			{
110			return 0;
111			}
112			}
113
114			//If the first character is a "-" sign, it may not be the only character,
115			//and it may not precede a "0" (which would again be a leading 0 violation).
116			//If it is a "-", we can exclude "0" and parse as a positive.
117			if (Substr($Intnum, 0, 1)=="-")
118			{
119			if ($Length==1)
120			{
121			return 0;
122			}
123			else
124			{
125			if (Substr($Intnum, 1, 1) == "0")
126			{
127			//This is illegal (a "-" followed by a "0").
128			return 0;
129			}
130			else
131			{
132			//We can just remove the "-" and parse as a positive.
133			$Intnum = Substr($Intnum, 1, $Length - 1);
134			$Length--;
135			}
136			}
137			}
138
139			//It is known at this point that the length is at least 1 and the leading
140			//character is not zero. All we need to do at this point is check that each
141			//and every character is a digit.
142			for ($index=0; $index < $Length; $index++)
143			{
144			if (!euclid_gcd_isdigit(Substr($Intnum, $index, 1)))
145			return 0;
146			}
147
148			return 1;
149			}
150			//
151			//
152			//Returns the number of digits in the argument, which must be a valid simple
153			//integer.
154			function euclid_gcd_ndigits($Intnum)
155			{
156			$Intnum = (string)$Intnum;
157
158			if (Substr($Intnum, 0, 1) == "-")
159			{
160			$rv = strlen($Intnum) - 1;
161			}
162			else
163			{
164			$rv = strlen($Intnum);
165			}
166
167			return($rv);
168			}
169			//
170			//
171			//Given a string, converts the final character to an integer. If the character
172			//is not a digit, returns 0.
173			function euclid_gcd_digittoint($Digit)
174			{
175			//echo "Digit is: ";
176			//echo $Digit;
177			//echo "<br>";
178
179			$Digit = (string)$Digit;
180
181			//echo "Digit is: ";
182			//echo $Digit;
183			//echo "<br>";
184
185			//If the string has zero length, this is an error condition and return 0.
186			$Length = strlen($Digit);
187
188			//echo "Length is: ";
189			//echo $Length;
190			//echo "<br>";
191
192			if ($Length==0)
193			{
194			return(0);
195			}
196
197			//Obtain the trailing character of the string.
198			$Trailing_char = Substr($Digit, $Length-1, 1);
199
200			//echo "Trailing char is: ";
201			//echo $Trailing_char;
202			//echo "<br>";
203
204			//Do a switch and return an integer based on the character.
205			//The default case gives 0.
206
207			switch($Trailing_char)
208			{
209			case "9":
210			return 9;
211			break;
212			case "8":
213			return 8;
214			break;
215			case "7":
216			return 7;
217			break;
218			case "6":
219			return 6;
220			break;
221			case "5":
222			return 5;
223			break;
224			case "4":
225			return 4;
226			break;
227			case "3":
228			return 3;
229			break;
230			case "2":
231			return 2;
232			break;
233			case "1":
234			return 1;
235			break;
236			default:
237			return 0;
238			break;
239			}
240			}
241
242			//Decommanates an integer and removes all other crap without respect for
243			//whether the commas are in the right place or the integer is syntactically valid.
244			function euclid_gcd_decommanate(&$arg)
245			{
246			$temp = "";
247
248			$len = strlen($arg);
249
250			for ($i=0; $i<$len; $i++)
251			{
252			$c = (string)Substr($arg, $i, 1);
253
254			if (euclid_gcd_isdigit($c) \|\| ($c == "-"))
255			$temp = $temp . $c;
256			}
257
258			$arg = (string)$temp;
259			}
260
261			//Commanates an integer which is assumed to by syntactically correct.
262			function euclid_gcd_commanate(&$arg)
263			{
264			euclid_gcd_decommanate($arg);
265
266			$temp = "";
267
268			$len = strlen($arg);
269
270			for ($i=0; $i<$len; $i++)
271			{
272			$c = (string)Substr($arg, $len - $i - 1, 1);
273
274			$temp = $c . $temp;
275
276			if ($i != ($len-1))
277			{
278			if (Substr($arg, $len-$i-2, 1) != "-")
279			{
280			if (($i % 3) == 2)
281			$temp = "," . $temp;
282			}
283			}
284			}
285
286			$arg = (string)$temp;
287			}
288
289			function do_header(&$style)
290			{
291			$style->header_title("GCD Calculator (Euclid's Algorithm)",
292			"GCD Calculator",
293			"This cgi-bin form calculates the greatest common divisor of two positive " .
294			"integers using " .
295			"<a href=\"http://mathworld.wolfram.com/EuclideanAlgorithm.html\">Euclid's classic algorithm</a>.");
296			}
297
298			function do_footer(&$style)
299			{
300			$style->hrule_std();
301			echo "<p align=\"center\">This utility is powered by the ";
302			echo "<a href=\"http://www.swox.com/gmp\"><img hspace=\"5\" vspace=\"5\" src=\"../genimages/gmplogo1.png\" width=\"232\" height=\"104\" align=\"absmiddle\"></a>.  All source code is available ";
303			echo "<a href=\"../howtos/nth_web_gmp_src_code_dist/obtain_all_source.htm\">here</a>.</p>\n";
304			$style->footer_std();
305			}
306
307			function do_form($N1_refresh, $N2_refresh, $Buttontext, $max_gcd_digits)
308			{
309			echo "<form method=get action=\"euclid_gcd.php\" width=\"100%\">\n";
310			echo "<table align=\"center\">\n";
311			echo "<tr>\n";
312			echo " <td width=\"10%\">\n";
313			echo " <p align=\"right\"><b>N1</b> (" . number_format($max_gcd_digits) . "-digit maximum):</td>\n";
314			echo " <td width=\"18%\"><p align=\"left\"><input type=\"text\" ";
315			if (strlen($N1_refresh))
316			{
317			echo "value=\"" . $N1_refresh . "\" ";
318			}
319			echo "name=\"N1\" size=\"50\"></p></td>\n";
320			echo " </tr>\n";
321			echo " <tr>\n";
322			echo " <td width=\"10%\">\n";
323			echo " <p align=\"right\"><b>N2</b> (" . number_format($max_gcd_digits) . "-digit maximum):</td>\n";
324			echo " <td width=\"18%\"><p align=\"left\"><input type=\"text\" ";
325			if (strlen($N2_refresh))
326			{
327			echo "value=\"" . $N2_refresh . "\" ";
328			}
329			echo "name=\"N2\" size=\"50\"></p></td>\n";
330			echo " </tr>\n";
331			echo " <tr>\n";
332			echo " <td width=\"20%\" colspan=\"2\">\n";
333			echo " <p align=\"center\"><input type=\"submit\" value=\"";
334			echo $Buttontext;
335			echo "\" name=\"B1\" style=\"margin-top: 12\"></td>\n";
336			echo " </tr>\n";
337			echo "</table>\n";
338			echo "</form>\n";
339			}
340
341			function do_err_msg($Err_msg)
342			{
343			echo "<p align=\"center\"><b><font color=\"#FF0000\">";
344			echo $Err_msg;
345			echo "</font></b></p>\n";
346			}
347
348
349			//Main script begins here.
350			//
351			//
352			//Let's agree on a maximum for number of digits in either
353			//of the two arguments. This has been checked out and seems
354			//to be within operational parameters (script won't time out).
355			$max_gcd_digits = 200;
356			//
357			$style = new Stdnwpstyle;
358			//Assign the current style in force. Also, starts the CPU
359			//usage clock.
360
361			//Do the header unconditionally. The header is always used on this page.
362			do_header($style);
363			//
364			//
365			//If N1 was supplied, decommanate it and be sure it is a string.
366			if (isset($N1))
367			euclid_gcd_decommanate($N1);
368
369			//Same for N2.
370			if (isset($N2))
371			euclid_gcd_decommanate($N2);
372			//
373			//There are a few cases to break into here, and this affects the overall layout of the page.
374			//The header and footer are fixed, but the "guts" will change.
375			if (!isset($N1) && !isset($N2))
376			{
377			//In this case, we are probably visiting the form for the first time, and have not done a submit.
378			//Just display the form itself.
379			do_form("", "", "Calculate GCD", $max_gcd_digits);
380			}
381			elseif (!isset($N1) && isset($N2))
382			{
383			//Only $N2 is supplied.
384			do_err_msg("You must supply both N1 and N2 to calculate a GCD.  Only N2 was supplied.  Please try again.");
385			$style->hrule_std();
386			euclid_gcd_commanate($N2);
387			do_form("", $N2, "Calculate GCD", $max_gcd_digits);
388			}
389			elseif (isset($N1) && !isset($N2))
390			{
391			//Only $N1 is supplied.
392			do_err_msg("You must supply both N1 and N2 to calculate a GCD.  Only N1 was supplied.  Please try again.");
393			$style->hrule_std();
394			euclid_gcd_commanate($N1);
395			do_form($N1, "", "Calculate GCD", $max_gcd_digits);
396			}
397			elseif (!euclid_gcd_issimpleint($N1) \|\| !euclid_gcd_issimpleint($N2))
398			{
399			//$N1 and $N2 are both supplied, but one or both is malformed. Need to advise.
400			if (!euclid_gcd_issimpleint($N1) && !euclid_gcd_issimpleint($N2))
401			{
402			do_err_msg("N1 and N2 are both malformed integers.  Choose new values and try again.");
403			$style->hrule_std();
404			do_form($N1, $N2, "Calculate GCD", $max_gcd_digits);
405			}
406			elseif (!euclid_gcd_issimpleint($N1))
407			{
408			do_err_msg("N1 is a malformed integer.  Choose a new value for N1 and try again.");
409			$style->hrule_std();
410			euclid_gcd_commanate($N2);
411			do_form($N1, $N2, "Calculate GCD", $max_gcd_digits);
412			}
413			else
414			{
415			do_err_msg("N2 is a malformed integer.  Choose a new value for N2 and try again.");
416			$style->hrule_std();
417			euclid_gcd_commanate($N1);
418			do_form($N1, $N2, "Calculate GCD", $max_gcd_digits);
419			}
420			}
421			elseif ((strlen($N1) > $max_gcd_digits) \|\| (strlen($N2) > $max_gcd_digits))
422			{
423			if ((strlen($N1) > $max_gcd_digits) && (strlen($N2) > $max_gcd_digits))
424			{
425			do_err_msg("N1 and N2 are both too long (a " . number_format($max_gcd_digits) . "-digit maximum is " .
426			"in effect).  Choose shorter values and try again.");
427			$style->hrule_std();
428			euclid_gcd_commanate($N1);
429			euclid_gcd_commanate($N2);
430			do_form($N1, $N2, "Calculate GCD", $max_gcd_digits);
431			}
432			elseif (strlen($N1) > $max_gcd_digits)
433			{
434			do_err_msg("N1 is too long (a " . number_format($max_gcd_digits) . "-digit maximum is " .
435			"in effect).  Choose a shorter value and try again.");
436			$style->hrule_std();
437			euclid_gcd_commanate($N1);
438			euclid_gcd_commanate($N2);
439			do_form($N1, $N2, "Calculate GCD", $max_gcd_digits);
440			}
441			else
442			{
443			do_err_msg("N2 is too long (a " . number_format($max_gcd_digits) . "-digit maximum is " .
444			"in effect).  Choose a shorter value and try again.");
445			$style->hrule_std();
446			euclid_gcd_commanate($N1);
447			euclid_gcd_commanate($N2);
448			do_form($N1, $N2, "Calculate GCD", $max_gcd_digits);
449			}
450			}
451			else
452			{
453			//N1 and N2 were both supplied and seem to be valid integers.
454			//
455			//If either integer is negative, make it positive.
456			if (Substr($N1, 0, 1)=="-")
457			$N1 = Substr($N1, 1, strlen($N1)-1);
458			if (Substr($N2, 0, 1)=="-")
459			$N2 = Substr($N2, 1, strlen($N2)-1);
460
461			//If either is "0", make it "1".
462			if ($N1=="0")
463			$N1 = (string)"1";
464			if ($N2=="0")
465			$N2 = (string)"1";
466
467			//We can now run the external program to do the calculation.
468			$cgi_command_string = "./arith_large_cgi gcd " . $N1 . " " . $N2;
469			//echo "CGI command string is : " . $cgi_command_string . "<br>\n";
470
471			exec($cgi_command_string, $cgi_result);
472			$cgi_result_nelem = count($cgi_result);
473
474			//echo "Result is : " . $cgi_result_nelem . "<br>\n";
475
476			//for ($i=0; $i<$cgi_result_nelem; $i++)
477			//{
478			// echo $cgi_result[$i] . "<br>\n";
479			//}
480
481			//We need to perform some sanity checks on the CGI output to be sure it
482			//is what we want. If it seems wrong, we need to generate an error message
483			//and not try to display the output.
484			$cgi_output_is_sane = 1;
485			if ($cgi_result_nelem == 0)
486			$cgi_output_is_sane = 0;
487			if ($cgi_result_nelem > 0)
488			{
489			if (($cgi_result_nelem % 5) != 0)
490			$cgi_output_is_sane = 0;
491			if ($cgi_result[0] != "S")
492			$cgi_output_is_sane = 0;
493			if ($cgi_result[$cgi_result_nelem - 1] != "S")
494			$cgi_output_is_sane = 0;
495			}
496
497			if (!$cgi_output_is_sane)
498			{
499			do_err_msg("An unspecified error occurred when interacting with the CGI-BIN program.  Please advise the webmaster.");
500			$style->hrule_std();
501			euclid_gcd_commanate($N1);
502			euclid_gcd_commanate($N2);
503			do_form($N1, $N2, "Calculate GCD", $max_gcd_digits);
504			}
505			else
506			{
507			euclid_gcd_commanate($cgi_result[1]);
508			euclid_gcd_commanate($cgi_result[2]);
509			euclid_gcd_commanate($cgi_result[$cgi_result_nelem - 2]);
510
511			echo "<p align=\"center\"><font size=\"4\">The greatest common divisor of ";
512			echo $cgi_result[1];
513			echo " and ";
514			echo $cgi_result[2];
515			echo " is ";
516			echo $cgi_result[$cgi_result_nelem - 2];
517			echo ".</font></p>\n";
518
519			$style->hrule_std();
520
521			echo "<p align=\"left\"><b>Notes on the algorithm:  </b>\n";
522			echo "Euclid's classic GCD algorithm was known no later than about 200 B.C. and is documented \n";
523			echo "at the \n";
524			echo "<a href=\"http://mathworld.wolfram.com/EuclideanAlgorithm.html\">Wolfram Research site</a> \n";
525			echo "and also in Knuth's classic reference work, ";
526			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";
527			echo "Art Of Computer Programming</i></a>.  Euclid's GCD algorithm ends with the GCD being the \n";
528			echo "last non-zero remainder (in yellow below unless <i>a</i> is a multiple of <i>b</i>).\n";
529			echo "</p>\n";
530
531			//Assign the table column widths. They are centralized here for easy change.
532			$width[0] = 5;
533			$width[1] = 10;
534			$width[2] = 10;
535			$width[3] = 10;
536			$width[4] = 10;
537
538			echo "<table align=\"center\" border=\"1\" width=\"90%\">\n";
539
540			for ($i=0; $i <= ($cgi_result_nelem/5 - 1); $i++)
541			{
542			echo "<tr>\n";
543
544			echo " <td width=\"" . $width[0] . "%\">\n";
545			if ($i==0)
546			{
547			echo " <p align=\"center\"><b>Round</b></p>\n";
548			}
549			else
550			{
551			euclid_gcd_commanate($cgi_result[$i*5-2]);
552			echo " <p align=\"center\">" . $cgi_result[$i*5-2] . "</p>\n";
553			}
554			echo " </td>\n";
555
556			echo " <td width=\"" . $width[1] . "%\">\n";
557			if ($i==0)
558			{
559			echo " <p align=\"center\"><b>a</b></p>\n";
560			}
561			else
562			{
563			euclid_gcd_commanate($cgi_result[$i*5-1]);
564			echo " <p align=\"right\">" . $cgi_result[$i*5-1] . "</p>\n";
565			}
566			echo " </td>\n";
567
568			echo " <td width=\"" . $width[2] . "%\">\n";
569			if ($i==0)
570			{
571			echo " <p align=\"center\"><b>b</b></p>\n";
572			}
573			else
574			{
575			euclid_gcd_commanate($cgi_result[$i*5]);
576			echo " <p align=\"right\">" . $cgi_result[$i*5] . "</p>\n";
577			}
578			echo " </td>\n";
579
580			echo " <td width=\"" . $width[3] . "%\">\n";
581			if ($i==0)
582			{
583			echo " <p align=\"center\"><b>a <i>div</i> b</b></p>\n";
584			}
585			else
586			{
587			euclid_gcd_commanate($cgi_result[$i*5+1]);
588			echo " <p align=\"right\">" . $cgi_result[$i*5+1] . "</p>\n";
589			}
590			echo " </td>\n";
591
592			if ($i > 0)
593			euclid_gcd_commanate($cgi_result[$i*5+2]);
594			echo " <td width=\"" . $width[4] . "%\"";
595			if (($i > 0) && ($cgi_result[$i*5+2] == $cgi_result[$cgi_result_nelem - 2]))
596			echo " bgcolor=\"#FFFF00\"";
597			echo ">\n";
598			if ($i==0)
599			{
600			echo " <p align=\"center\"><b>a <i>mod</i> b</b></p>\n";
601			}
602			else
603			{
604			//euclid_gcd_commanate($cgi_result[$i*5+2]);
605			echo " <p align=\"right\">" . $cgi_result[$i*5+2] . "</p>\n";
606			}
607			echo " </td>\n";
608
609			echo "</tr>\n";
610			}
611
612			echo "</table><br>\n";
613			$style->hrule_std();
614
615			euclid_gcd_commanate($N1);
616			euclid_gcd_commanate($N2);
617			do_form($N1, $N2, "Calculate Another GCD", $max_gcd_digits);
618			}
619			}
620
621			//Now do the footer unconditionally. The footer is always used on this web page.
622			do_footer($style);
623			?>