/[dtapublic]/projs/dtats/trunk/projs/2018/20180707_cgi_web_tools/active/num_theory/euclid_gcd/euclid_gcd.php
ViewVC logotype

Contents of /projs/dtats/trunk/projs/2018/20180707_cgi_web_tools/active/num_theory/euclid_gcd/euclid_gcd.php

Parent Directory Parent Directory | Revision Log Revision Log


Revision 179 - (show annotations) (download)
Tue Jul 10 01:18:43 2018 UTC (6 years, 5 months ago) by dashley
File size: 17814 byte(s)
Move Euclid's GCD algorithm to active pages.
1 <?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>.&nbsp; 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. &nbsp;Only N2 was supplied. &nbsp;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. &nbsp;Only N1 was supplied. &nbsp;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. &nbsp;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. &nbsp;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. &nbsp;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).&nbsp; 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).&nbsp; 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).&nbsp; 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.&nbsp; 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: &nbsp;</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>. &nbsp;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 ?>

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25