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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 204 - (show annotations) (download)
Sun Jul 15 18:45:10 2018 UTC (5 years, 8 months ago) by dashley
File size: 20632 byte(s)
Add keyword expansion, native EOL.
1 <?php
2 require_once("style/std/stdwpstyle.inc");
3 //----------------------------------------------------------------------------------------------------
4 //Copyright (c) 2003, 2018 David T. Ashley.
5 //
6 //Permission is hereby granted, free of charge, to any person obtaining a copy
7 //of this software and associated documentation files (the "Software"), to deal
8 //in the Software without restriction, including without limitation the rights
9 //to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 //copies of the Software, and to permit persons to whom the Software is
11 //furnished to do so, subject to the following conditions:
12 //
13 //The above copyright notice and this permission notice shall be included in all
14 //copies or substantial portions of the Software.
15 //
16 //THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 //IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 //FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 //AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 //LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 //OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 //SOFTWARE.
23 //----------------------------------------------------------------------------------------------------
24 //
25 //Returns TRUE if the passed argument is a digit, or FALSE otherwise. If the
26 //passed string has length > 1, only the least significant digit is
27 //considered.
28 function pfact18_isdigit($Digit)
29 {
30 $Digit = (string)$Digit;
31
32 //If the string has zero length, this is an error condition and return 0.
33 $Length = strlen($Digit);
34
35 if ($Length==0)
36 {
37 return(0);
38 }
39
40 //Obtain the trailing character of the string.
41 $Trailing_char = Substr($Digit, $Length-1, 1);
42
43 //Do a switch and return an integer based on the character.
44 switch($Trailing_char)
45 {
46 case "9":
47 return 1;
48 break;
49 case "8":
50 return 1;
51 break;
52 case "7":
53 return 1;
54 break;
55 case "6":
56 return 1;
57 break;
58 case "5":
59 return 1;
60 break;
61 case "4":
62 return 1;
63 break;
64 case "3":
65 return 1;
66 break;
67 case "2":
68 return 1;
69 break;
70 case "1":
71 return 1;
72 break;
73 case "0":
74 return 1;
75 break;
76 default:
77 return 0;
78 break;
79 }
80 }
81 //
82 //
83 //Returns TRUE if the passed argument is a simple integer (no error
84 //codes, no commas), or FALSE otherwise.
85 function pfact18_issimpleint($Intnum)
86 {
87 $Intnum = (string)$Intnum;
88
89 //If the string has zero length, this is an error condition and return 0.
90 $Length = strlen($Intnum);
91
92 if ($Length==0)
93 {
94 return(0);
95 }
96
97 //If the first digit is "0", this must be the only character in the string,
98 //otherwise there is a leading-zero violation.
99 if (Substr($Intnum, 0, 1)=="0")
100 {
101 if ($Length==1)
102 {
103 return 1;
104 }
105 else
106 {
107 return 0;
108 }
109 }
110
111 //If the first character is a "-" sign, it may not be the only character,
112 //and it may not precede a "0" (which would again be a leading 0 violation).
113 //If it is a "-", we can exclude "0" and parse as a positive.
114 if (Substr($Intnum, 0, 1)=="-")
115 {
116 if ($Length==1)
117 {
118 return 0;
119 }
120 else
121 {
122 if (Substr($Intnum, 1, 1) == "0")
123 {
124 //This is illegal (a "-" followed by a "0").
125 return 0;
126 }
127 else
128 {
129 //We can just remove the "-" and parse as a positive.
130 $Intnum = Substr($Intnum, 1, $Length - 1);
131 $Length--;
132 }
133 }
134 }
135
136 //It is known at this point that the length is at least 1 and the leading
137 //character is not zero. All we need to do at this point is check that each
138 //and every character is a digit.
139 for ($index=0; $index < $Length; $index++)
140 {
141 if (!pfact18_isdigit(Substr($Intnum, $index, 1)))
142 return 0;
143 }
144
145 return 1;
146 }
147 //
148 //
149 //Returns the number of digits in the argument, which must be a valid simple
150 //integer.
151 function pfact18_ndigits($Intnum)
152 {
153 $Intnum = (string)$Intnum;
154
155 if (Substr($Intnum, 0, 1) == "-")
156 {
157 $rv = strlen($Intnum) - 1;
158 }
159 else
160 {
161 $rv = strlen($Intnum);
162 }
163
164 return($rv);
165 }
166 //
167 //
168 //Given a string, converts the final character to an integer. If the character
169 //is not a digit, returns 0.
170 function pfact18_digittoint($Digit)
171 {
172 //echo "Digit is: ";
173 //echo $Digit;
174 //echo "<br>";
175
176 $Digit = (string)$Digit;
177
178 //echo "Digit is: ";
179 //echo $Digit;
180 //echo "<br>";
181
182 //If the string has zero length, this is an error condition and return 0.
183 $Length = strlen($Digit);
184
185 //echo "Length is: ";
186 //echo $Length;
187 //echo "<br>";
188
189 if ($Length==0)
190 {
191 return(0);
192 }
193
194 //Obtain the trailing character of the string.
195 $Trailing_char = Substr($Digit, $Length-1, 1);
196
197 //echo "Trailing char is: ";
198 //echo $Trailing_char;
199 //echo "<br>";
200
201 //Do a switch and return an integer based on the character.
202 //The default case gives 0.
203
204 switch($Trailing_char)
205 {
206 case "9":
207 return 9;
208 break;
209 case "8":
210 return 8;
211 break;
212 case "7":
213 return 7;
214 break;
215 case "6":
216 return 6;
217 break;
218 case "5":
219 return 5;
220 break;
221 case "4":
222 return 4;
223 break;
224 case "3":
225 return 3;
226 break;
227 case "2":
228 return 2;
229 break;
230 case "1":
231 return 1;
232 break;
233 default:
234 return 0;
235 break;
236 }
237 }
238
239 //Decommanates an integer and removes all other crap without respect for
240 //whether the commas are in the right place or the integer is syntactically valid.
241 function pfact18_decommanate(&$arg)
242 {
243 $temp = "";
244
245 $len = strlen($arg);
246
247 for ($i=0; $i<$len; $i++)
248 {
249 $c = (string)Substr($arg, $i, 1);
250
251 if (pfact18_isdigit($c) || ($c == "-"))
252 $temp = $temp . $c;
253 }
254
255 $arg = (string)$temp;
256 }
257
258 //Commanates an integer which is assumed to by syntactically correct.
259 function pfact18_commanate(&$arg)
260 {
261 pfact18_decommanate($arg);
262
263 $temp = "";
264
265 $len = strlen($arg);
266
267 for ($i=0; $i<$len; $i++)
268 {
269 $c = (string)Substr($arg, $len - $i - 1, 1);
270
271 $temp = $c . $temp;
272
273 if ($i != ($len-1))
274 {
275 if (Substr($arg, $len-$i-2, 1) != "-")
276 {
277 if (($i % 3) == 2)
278 $temp = "," . $temp;
279 }
280 }
281 }
282
283 $arg = (string)$temp;
284 }
285
286 function do_header(&$style)
287 {
288 $style->static_page_header_title_std("[Attempted] Prime Factorization Of An Integer (18 Or Fewer Digits)",
289 "Prime Factorization Of An Integer (18 Or Fewer Digits)",
290 "This utility attempts to factor an integer of 18 or fewer digits into its " .
291 "prime components.");
292 }
293
294 function do_footer(&$style)
295 {
296 // $style->static_page_hrule_std();
297 // echo "<p align=\"center\">This utility is powered by the ";
298 // 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 ";
299 // echo "<a href=\"../howtos/nth_web_gmp_src_code_dist/obtain_all_source.htm\">here</a>.</p>\n";
300 $style->static_page_footer_std();
301 }
302
303 function do_form($N_refresh, $Buttontext)
304 {
305 echo "<form method=get action=\"index.php\" width=\"100%\">\n";
306 echo "<table align=\"center\">\n";
307 echo "<tr>\n";
308 echo " <td width=\"10%\">\n";
309 echo " <p align=\"right\"><b>N</b> (18-digit maximum):</td>\n";
310 echo " <td width=\"18%\"><p align=\"left\"><input type=\"text\" ";
311 if (strlen($N_refresh))
312 {
313 echo "value=\"" . $N_refresh . "\" ";
314 }
315 echo "name=\"N\" size=\"50\"></p></td>\n";
316 echo " </tr>\n";
317 echo " <tr>\n";
318 echo " <td width=\"20%\" colspan=\"2\">\n";
319 echo " <p align=\"center\"><input type=\"submit\" value=\"";
320 echo $Buttontext;
321 echo "\" name=\"B1\" style=\"margin-top: 12\"></td>\n";
322 echo " </tr>\n";
323 echo "</table>\n";
324 echo "</form>\n";
325 }
326
327 function do_err_msg($Err_msg)
328 {
329 echo "<p align=\"center\"><b><font color=\"#FF0000\">";
330 echo $Err_msg;
331 echo "</font></b></p>\n";
332 }
333
334 //Prints algorithm notes with no extraneous HTML (no horizontal lines, etc.)
335 //
336 function pfact18_algorithm_notes($cgi_max)
337 {
338 ?>
339 <p><b><u>Algorithm Notes:</u></b></p>
340 <ul>
341 <li>This web page uses trial division combined with the
342 <a href="http://mathworld.wolfram.com/EratosthenesSieve.html">Sieve of Eratosthenes</a>
343 with a sieve of 2,310 = 2 * 3 * 5 * 7 * 11 elements.&nbsp; The
344 sieve is automatically generated, automatically compacted into a
345 difference table containing 480 elements, and packaged as a C-language source
346 file containing a 480-element lookup table of
347 integers.&nbsp; The algorithm checks divisibility by increasing trial divisors,
348 but it does so with all multiples of 2, 3, 5, 7, and 11 omitted (this is the
349 role of the Sieve of Eratosthenes).</li>
350 <li>Although this web page does factor effectively,
351 it is strictly "parlor amusement" grade, and will answer questions
352 such as <i>Is the year I was born a prime number?</i> or <i>Is my street address
353 prime?</i>, but is inadequate for serious factoring.&nbsp; Because this CGI-BIN
354 application runs on a shared server, it protects itself by only allowing
355 <?php echo " " . $cgi_max . " "; ?>seconds to elapse while factoring.&nbsp; The busier
356 the server is, the less actual CPU time is represented by
357 <?php echo " " . $cgi_max . " "; ?>seconds of elapsed time.&nbsp; This means that
358 factoring operations may be less successful when the server is busy.</li>
359 <li>This utility uses the <a href="http://www.swox.com/gmp">GMP library</a>
360 for arithmetic.&nbsp; The limit of 18-digit integers is in place so that
361 machine-native integers can be used for the trial divisor (it is more
362 efficient that way, and the GMP provides special function calls
363 for small divisors).&nbsp; Since the trial divisor need only attain
364 the square root of the number to be factored, any trial divisor for
365 an 18-digit integer will fit in one machine-native integer.</li>
366 </ul>
367 <?php
368 }
369
370 function pfact18_print_tabular_results(&$style,
371 $cgi_result,
372 $cgi_result_nelem,
373 $mr_nrounds,
374 $mr_pcntprime,
375 $mr_recip,
376 $cgi_max)
377 {
378 //Add commas to the number to factor, the number of Miller-Rabin rounds, and
379 //the timeout.
380 pfact18_commanate($cgi_result[1]);
381 pfact18_commanate($cgi_result[2]);
382 pfact18_commanate($cgi_result[3]);
383
384 //Add commas to each prime factor and its multiplicity.
385 $nfactors = ($cgi_result_nelem - 6)/3;
386
387 for ($i=0; $i<$nfactors; $i++)
388 {
389 pfact18_commanate($cgi_result[$i * 3 + 5]);
390 pfact18_commanate($cgi_result[$i * 3 + 6]);
391 }
392
393 //echo "<br>" . $cgi_result_nelem . "<br>";
394
395 //Announce the overall result.
396 $print_table = 0;
397 echo "<p align=\"center\"><font size=\"4\">";
398 if (($cgi_result[$cgi_result_nelem - 5] == "P") && ($cgi_result_nelem == 9) && ($cgi_result[$cgi_result_nelem - 3] == "1"))
399 {
400 echo "The integer " . $cgi_result[1] . " is prime (with 100% certainty).";
401 }
402 elseif (($cgi_result[$cgi_result_nelem - 5] == "p") && ($cgi_result_nelem == 9))
403 {
404 echo "Based on " . $mr_nrounds . " applications of the Miller-Rabin test, the integer ";
405 echo $cgi_result[1] . " is probably (with " . $mr_pcntprime . "% probability) ";
406 echo "prime.&nbsp; (This means that there is no more than 1 chance ";
407 echo "in " . $mr_recip . " that this integer is composite.)";
408 }
409 elseif (($cgi_result[$cgi_result_nelem - 5] == "C") && ($cgi_result_nelem == 9))
410 {
411 echo "The integer " . $cgi_result[1] . " has been verified by the Miller-Rabin test ";
412 echo "to be composite.&nbsp; However, ";
413 echo "due to server CPU time restrictions (" . $cgi_max . " seconds of elapsed time), ";
414 echo "it was not possible to make any progress in factoring ";
415 echo "this integer.&nbsp; Please try again when the server is less active ";
416 echo "or try another factoring resource.";
417 }
418 elseif ($cgi_result[$cgi_result_nelem - 5] == "P")
419 {
420 echo "The composite integer " ;
421 echo $cgi_result[1] . " was successfully factored into its prime components with ";
422 echo "100% certainty.&nbsp; Its prime factors and their multiplicities are listed ";
423 echo "in the table below.";
424 $print_table = 1;
425 }
426 elseif ($cgi_result[$cgi_result_nelem - 5] == "p")
427 {
428 echo "The composite integer " ;
429 echo $cgi_result[1] . " was successfully factored into its prime components, ";
430 echo "and these prime components and their multiplicities are listed in the ";
431 echo "table below.&nbsp; ";
432 echo "The last component listed in the table was judged to be prime based on ";
433 echo $mr_nrounds . " applications of the Miller-Rabin test, meaning that it is ";
434 echo $mr_pcntprime . "% probable ";
435 echo "that this last component is prime (i.e. that there is no more than 1 chance ";
436 echo "in " . $mr_recip . " that it is composite).";
437 $print_table = 1;
438 }
439 elseif ($cgi_result[$cgi_result_nelem - 5] == "C")
440 {
441 echo "Due to server CPU time restrictions (" . $cgi_max . " seconds of elapsed time), ";
442 echo "the integer ";
443 echo $cgi_result[1] . " could only be partially factored.&nbsp; In the results below, note that ";
444 echo "the last component ";
445 echo "listed bears the category code <i>C</i> (for <u>c</u>omposite).&nbsp; Please ";
446 echo " try again when the server is less active ";
447 echo "or try another factoring resource.";
448 $print_table = 1;
449 }
450 echo "</p></font>";
451
452 //Print the table if demanded.
453 if ($print_table)
454 {
455 $style->static_page_hrule_std();
456
457 //Assign the table column widths. They are centralized here for easy change.
458 $width[0] = 10;
459 $width[1] = 10;
460 $width[2] = 10;
461 $width[3] = 10;
462
463 echo "<p><table align=\"center\" border=\"1\" width=\"90%\">\n";
464
465 for ($i=0; $i <= ($cgi_result_nelem/3 - 2); $i++)
466 {
467 //Factor number.
468 echo "<tr>\n";
469
470 echo " <td width=\"" . $width[0] . "%\">\n";
471 if ($i==0)
472 {
473 echo " <p align=\"center\"><b>Factor<br>Number</b></p>\n";
474 }
475 else
476 {
477 echo " <p align=\"center\">" . $i . "</p>\n";
478 }
479 echo " </td>\n";
480
481 //Prime Factor
482 echo " <td width=\"" . $width[1] . "%\">\n";
483 if ($i==0)
484 {
485 echo " <p align=\"center\"><b>Component<br>Factor</b></p>\n";
486 }
487 else
488 {
489 echo " <p align=\"center\">" . $cgi_result[$i * 3 + 2] . "</p>\n";
490 }
491 echo " </td>\n";
492
493 //Multiplicity.
494 echo " <td width=\"" . $width[2] . "%\">\n";
495 if ($i==0)
496 {
497 echo " <p align=\"center\"><b>Multiplicity</b></p>\n";
498 }
499 else
500 {
501 echo " <p align=\"center\">" . $cgi_result[$i * 3 + 3] . "</p>\n";
502 }
503 echo " </td>\n";
504
505 //Category code.
506 echo " <td width=\"" . $width[3] . "%\">\n";
507 if ($i==0)
508 {
509 echo " <p align=\"center\"><b>Category<br>Code</b></p>\n";
510 }
511 else
512 {
513 echo " <p align=\"center\">" . $cgi_result[$i * 3 + 1] . "</p>\n";
514 }
515 echo " </td>\n";
516
517
518 echo "</tr>\n";
519 }
520
521 echo "</table></p>\n";
522 echo "<p align=\"center\"><b>Table legend:</b>&nbsp; <b>P</b>=prime with absolute certainty, ";
523 echo "<b>p</b>=prime established by Miller-Rabin test with ";
524 echo $mr_pcntprime . "% certainty, and <b>C</b>=composite established by Miller-Rabin test ";
525 echo "with absolute certainty, but not factorable in the time allowed.</p>\n";
526
527 $style->static_page_hrule_std();
528 pfact18_algorithm_notes($cgi_max);
529 }
530 }
531 //
532 //Main script begins here.
533 //
534 //Let's agree on a number of rounds for the Miller-Rabin test. This influences the
535 //probabilities.
536 $miller_rabin_nrounds = 25;
537 //
538 //Let's agree how long the CGI may take to factor.
539 $max_cgi_time = 10;
540 //
541 //We need to establish the probability that a number which passes the rounds specified
542 //above is still in fact composite. This values need to be calculated by hand whenever
543 //the value above is changed.
544 $miller_rabin_p_real = "0.99999999999999911182";
545 $miller_rabin_p_percent = "99.999999999999911182";
546 $miller_rabin_residual_real = "0.00000000000000088818";
547 $miller_rabin_residual_percent = "0.000000000000088818";
548 $miller_rabin_residual_lt_reciprocal = "1,125,899,906,842,624";
549 //
550 $style = new StdWpStyle;
551 //Assign the current style in force. Also, starts the CPU
552 //usage clock.
553
554 //Do the header unconditionally. The header is always used on this page.
555 do_header($style);
556 //
557 if (isset($_GET['N']))
558 $N = $_GET['N'];
559 //
560 //If N was supplied, decommanate it and be sure it is a string.
561 if (isset($N))
562 pfact18_decommanate($N);
563 //
564 //There are a few cases to break into here, and this affects the overall layout of the page.
565 //The header and footer are fixed, but the "guts" will change.
566 if (!isset($N))
567 {
568 //In this case, we are probably visiting the form for the first time, and have not done a submit.
569 //Just display the form itself.
570 do_form("", "Attempt To Factor Integer");
571 }
572 elseif (!pfact18_issimpleint($N))
573 {
574 //N is supplied, but is malformed. Need to advise.
575 do_err_msg("N is a malformed integer. &nbsp;Choose a new value for N and try again.");
576 $style->static_page_hrule_std();
577 pfact18_commanate($N2);
578 do_form($N, "Attempt To Factor Integer");
579 }
580 elseif (strlen($N) > 18)
581 {
582 //N is supplied, but is too long. Need to advise.
583 do_err_msg("N is too long (the maximum is 18 digits). &nbsp;Choose a new value for N and try again.");
584 $style->static_page_hrule_std();
585 pfact18_commanate($N);
586 do_form($N, "Attempt To Factor Integer");
587 }
588 else
589 {
590 //N is supplied and seems to be a valid integer.
591 //
592 //If N is negative, make it positive.
593 if (Substr($N, 0, 1)=="-")
594 $N = Substr($N, 1, strlen($N)-1);
595
596 //If N is "0" or "1", make it "2".
597 if ($N=="0")
598 $N = (string)"1";
599 if ($N=="1")
600 $N = (string)"2";
601
602 //We can now run the external program to do the calculation.
603 $cgi_command_string = "/hl/cgibin/aux_progs/dtats_cgi_aux_arith_large pfact_18 " . $N . " " . $miller_rabin_nrounds . " " . $max_cgi_time;
604 //echo "CGI command string is : " . $cgi_command_string . "<br>\n";
605
606 exec($cgi_command_string, $cgi_result);
607 $cgi_result_nelem = count($cgi_result);
608
609 //echo "Result is : " . $cgi_result_nelem . "<br>\n";
610
611 //for ($i=0; $i<$cgi_result_nelem; $i++)
612 //{
613 // echo $cgi_result[$i] . "<br>\n";
614 //}
615
616 //We need to perform some sanity checks on the CGI output to be sure it
617 //is what we want. If it seems wrong, we need to generate an error message
618 //and not try to display the output.
619 $cgi_output_is_sane = 1;
620 if ($cgi_result_nelem < 9)
621 $cgi_output_is_sane = 0;
622 if ($cgi_result_nelem >= 9)
623 {
624 if (($cgi_result_nelem % 3) != 0)
625 $cgi_output_is_sane = 0;
626 if ($cgi_result[0] != "S")
627 $cgi_output_is_sane = 0;
628 if ($cgi_result[$cgi_result_nelem - 2] != "X")
629 $cgi_output_is_sane = 0;
630 if ($cgi_result[$cgi_result_nelem - 1] != "S")
631 $cgi_output_is_sane = 0;
632 }
633
634 if (!$cgi_output_is_sane)
635 {
636 do_err_msg("An unspecified error occurred when interacting with the CGI-BIN program.&nbsp; Please advise the webmaster.");
637 $style->static_page_hrule_std();
638 pfact18_commanate($N);
639 do_form($N, "Attempt To Factor Integer");
640 }
641 else
642 {
643 pfact18_print_tabular_results($style,
644 $cgi_result,
645 $cgi_result_nelem,
646 $miller_rabin_nrounds,
647 $miller_rabin_p_percent,
648 $miller_rabin_residual_lt_reciprocal,
649 $max_cgi_time);
650 $style->static_page_hrule_std();
651
652 pfact18_commanate($N);
653 do_form($N, "Attempt To Factor Another Integer");
654 }
655 }
656
657 //Now do the footer unconditionally. The footer is always used on this web page.
658 do_footer($style);
659 ?>

Properties

Name Value
svn:eol-style native
svn:keywords Header

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25