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 "
"; $Digit = (string)$Digit; //echo "Digit is: "; //echo $Digit; //echo "
"; //If the string has zero length, this is an error condition and return 0. $Length = strlen($Digit); //echo "Length is: "; //echo $Length; //echo "
"; 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 "
"; //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 " . "Euclid's classic algorithm."); } function do_footer(&$style) { $style->hrule_std(); echo "

This utility is powered by the "; echo ".  All source code is available "; echo "here.

\n"; $style->footer_std(); } function do_form($N1_refresh, $N2_refresh, $Buttontext, $max_gcd_digits) { echo "
\n"; echo "\n"; echo "\n"; echo " \n"; echo " \n"; echo " \n"; echo " \n"; echo " \n"; echo " \n"; echo " \n"; echo " \n"; echo " \n"; echo " \n"; echo "
\n"; echo "

N1 (" . number_format($max_gcd_digits) . "-digit maximum):

\n"; echo "

N2 (" . number_format($max_gcd_digits) . "-digit maximum):

\n"; echo "

\n"; echo "
\n"; } function do_err_msg($Err_msg) { echo "

"; echo $Err_msg; echo "

\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.  Only N2 was supplied.  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.  Only N1 was supplied.  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.  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.  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.  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).  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).  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).  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 . "
\n"; exec($cgi_command_string, $cgi_result); $cgi_result_nelem = count($cgi_result); //echo "Result is : " . $cgi_result_nelem . "
\n"; //for ($i=0; $i<$cgi_result_nelem; $i++) //{ // echo $cgi_result[$i] . "
\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.  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 "

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 ".

\n"; $style->hrule_std(); echo "

Notes on the algorithm:  \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 "Wolfram Research site \n"; echo "and also in Knuth's classic reference work, "; echo "The \n"; echo "Art Of Computer Programming.  Euclid's GCD algorithm ends with the GCD being the \n"; echo "last non-zero remainder (in yellow below unless a is a multiple of b).\n"; echo "

\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 "\n"; for ($i=0; $i <= ($cgi_result_nelem/5 - 1); $i++) { echo "\n"; echo " \n"; echo " \n"; echo " \n"; echo " \n"; if ($i > 0) euclid_gcd_commanate($cgi_result[$i*5+2]); echo " \n"; echo "\n"; } echo "
\n"; if ($i==0) { echo "

Round

\n"; } else { euclid_gcd_commanate($cgi_result[$i*5-2]); echo "

" . $cgi_result[$i*5-2] . "

\n"; } echo " 		\n"; if ($i==0) { echo "

a

\n"; } else { euclid_gcd_commanate($cgi_result[$i*5-1]); echo "

" . $cgi_result[$i*5-1] . "

\n"; } echo " 		\n"; if ($i==0) { echo "

b

\n"; } else { euclid_gcd_commanate($cgi_result[$i*5]); echo "

" . $cgi_result[$i*5] . "

\n"; } echo " 		\n"; if ($i==0) { echo "

a div b

\n"; } else { euclid_gcd_commanate($cgi_result[$i*5+1]); echo "

" . $cgi_result[$i*5+1] . "

\n"; } echo " 		0) && ($cgi_result[$i*5+2] == $cgi_result[$cgi_result_nelem - 2])) echo " bgcolor=\"#FFFF00\""; echo ">\n"; if ($i==0) { echo "

a mod b

\n"; } else { //euclid_gcd_commanate($cgi_result[$i*5+2]); echo "

" . $cgi_result[$i*5+2] . "

\n"; } echo "

\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); ?>