/[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 23 - (show annotations) (download)
Sat Oct 8 06:11:57 2016 UTC (8 years, 2 months ago) by dashley
Original Path: sf_code/esrgweba/htdocs/phpcgibin/pfact18digit.php
File size: 20220 byte(s)
Initial commit.
1 <?php
2 if (!$STDNWPSTYLE_INCLUDED)
3 {
4 include("stdnwpstyle.inc");
5 $STDNWPSTYLE_INCLUDED=1;
6 }
7 ?>
8 <?php
9 //********************************************************************************
10 //Copyright (C) 2003 David T. Ashley
11 //********************************************************************************
12 //This program or source file is free software; you can redistribute it and/or
13 //modify it under the terms of the GNU General Public License as published by
14 //the Free Software Foundation; either version 2 of the License, or (at your
15 //option) any later version.
16 //
17 //This program or source file is distributed in the hope that it will
18 //be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
19 //MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 //GNU General Public License for more details.
21 //
22 //You may have received a copy of the GNU General Public License
23 //along with this program; if not, write to the Free Software
24 //Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
25 //********************************************************************************
26 //
27 //Returns TRUE if the passed argument is a digit, or FALSE otherwise. If the
28 //passed string has length > 1, only the least significant digit is
29 //considered.
30 function pfact18_isdigit($Digit)
31 {
32 $Digit = (string)$Digit;
33
34 //If the string has zero length, this is an error condition and return 0.
35 $Length = strlen($Digit);
36
37 if ($Length==0)
38 {
39 return(0);
40 }
41
42 //Obtain the trailing character of the string.
43 $Trailing_char = Substr($Digit, $Length-1, 1);
44
45 //Do a switch and return an integer based on the character.
46 switch($Trailing_char)
47 {
48 case "9":
49 return 1;
50 break;
51 case "8":
52 return 1;
53 break;
54 case "7":
55 return 1;
56 break;
57 case "6":
58 return 1;
59 break;
60 case "5":
61 return 1;
62 break;
63 case "4":
64 return 1;
65 break;
66 case "3":
67 return 1;
68 break;
69 case "2":
70 return 1;
71 break;
72 case "1":
73 return 1;
74 break;
75 case "0":
76 return 1;
77 break;
78 default:
79 return 0;
80 break;
81 }
82 }
83 //
84 //
85 //Returns TRUE if the passed argument is a simple integer (no error
86 //codes, no commas), or FALSE otherwise.
87 function pfact18_issimpleint($Intnum)
88 {
89 $Intnum = (string)$Intnum;
90
91 //If the string has zero length, this is an error condition and return 0.
92 $Length = strlen($Intnum);
93
94 if ($Length==0)
95 {
96 return(0);
97 }
98
99 //If the first digit is "0", this must be the only character in the string,
100 //otherwise there is a leading-zero violation.
101 if (Substr($Intnum, 0, 1)=="0")
102 {
103 if ($Length==1)
104 {
105 return 1;
106 }
107 else
108 {
109 return 0;
110 }
111 }
112
113 //If the first character is a "-" sign, it may not be the only character,
114 //and it may not precede a "0" (which would again be a leading 0 violation).
115 //If it is a "-", we can exclude "0" and parse as a positive.
116 if (Substr($Intnum, 0, 1)=="-")
117 {
118 if ($Length==1)
119 {
120 return 0;
121 }
122 else
123 {
124 if (Substr($Intnum, 1, 1) == "0")
125 {
126 //This is illegal (a "-" followed by a "0").
127 return 0;
128 }
129 else
130 {
131 //We can just remove the "-" and parse as a positive.
132 $Intnum = Substr($Intnum, 1, $Length - 1);
133 $Length--;
134 }
135 }
136 }
137
138 //It is known at this point that the length is at least 1 and the leading
139 //character is not zero. All we need to do at this point is check that each
140 //and every character is a digit.
141 for ($index=0; $index < $Length; $index++)
142 {
143 if (!pfact18_isdigit(Substr($Intnum, $index, 1)))
144 return 0;
145 }
146
147 return 1;
148 }
149 //
150 //
151 //Returns the number of digits in the argument, which must be a valid simple
152 //integer.
153 function pfact18_ndigits($Intnum)
154 {
155 $Intnum = (string)$Intnum;
156
157 if (Substr($Intnum, 0, 1) == "-")
158 {
159 $rv = strlen($Intnum) - 1;
160 }
161 else
162 {
163 $rv = strlen($Intnum);
164 }
165
166 return($rv);
167 }
168 //
169 //
170 //Given a string, converts the final character to an integer. If the character
171 //is not a digit, returns 0.
172 function pfact18_digittoint($Digit)
173 {
174 //echo "Digit is: ";
175 //echo $Digit;
176 //echo "<br>";
177
178 $Digit = (string)$Digit;
179
180 //echo "Digit is: ";
181 //echo $Digit;
182 //echo "<br>";
183
184 //If the string has zero length, this is an error condition and return 0.
185 $Length = strlen($Digit);
186
187 //echo "Length is: ";
188 //echo $Length;
189 //echo "<br>";
190
191 if ($Length==0)
192 {
193 return(0);
194 }
195
196 //Obtain the trailing character of the string.
197 $Trailing_char = Substr($Digit, $Length-1, 1);
198
199 //echo "Trailing char is: ";
200 //echo $Trailing_char;
201 //echo "<br>";
202
203 //Do a switch and return an integer based on the character.
204 //The default case gives 0.
205
206 switch($Trailing_char)
207 {
208 case "9":
209 return 9;
210 break;
211 case "8":
212 return 8;
213 break;
214 case "7":
215 return 7;
216 break;
217 case "6":
218 return 6;
219 break;
220 case "5":
221 return 5;
222 break;
223 case "4":
224 return 4;
225 break;
226 case "3":
227 return 3;
228 break;
229 case "2":
230 return 2;
231 break;
232 case "1":
233 return 1;
234 break;
235 default:
236 return 0;
237 break;
238 }
239 }
240
241 //Decommanates an integer and removes all other crap without respect for
242 //whether the commas are in the right place or the integer is syntactically valid.
243 function pfact18_decommanate(&$arg)
244 {
245 $temp = "";
246
247 $len = strlen($arg);
248
249 for ($i=0; $i<$len; $i++)
250 {
251 $c = (string)Substr($arg, $i, 1);
252
253 if (pfact18_isdigit($c) || ($c == "-"))
254 $temp = $temp . $c;
255 }
256
257 $arg = (string)$temp;
258 }
259
260 //Commanates an integer which is assumed to by syntactically correct.
261 function pfact18_commanate(&$arg)
262 {
263 pfact18_decommanate($arg);
264
265 $temp = "";
266
267 $len = strlen($arg);
268
269 for ($i=0; $i<$len; $i++)
270 {
271 $c = (string)Substr($arg, $len - $i - 1, 1);
272
273 $temp = $c . $temp;
274
275 if ($i != ($len-1))
276 {
277 if (Substr($arg, $len-$i-2, 1) != "-")
278 {
279 if (($i % 3) == 2)
280 $temp = "," . $temp;
281 }
282 }
283 }
284
285 $arg = (string)$temp;
286 }
287
288 function do_header(&$style)
289 {
290 $style->header_title("[Attempted] Prime Factorization Of An Integer (18 Or Fewer Digits)",
291 "Prime Factorization Of An Integer (18 Or Fewer Digits)",
292 "This utility attempts to factor an integer of 18 or fewer digits into its " .
293 "prime components.");
294 }
295
296 function do_footer(&$style)
297 {
298 $style->hrule_std();
299 echo "<p align=\"center\">This utility is powered by the ";
300 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 ";
301 echo "<a href=\"../howtos/nth_web_gmp_src_code_dist/obtain_all_source.htm\">here</a>.</p>\n";
302 $style->footer_std();
303 }
304
305 function do_form($N_refresh, $Buttontext)
306 {
307 echo "<form method=get action=\"pfact18digit.php\" width=\"100%\">\n";
308 echo "<table align=\"center\">\n";
309 echo "<tr>\n";
310 echo " <td width=\"10%\">\n";
311 echo " <p align=\"right\"><b>N</b> (18-digit maximum):</td>\n";
312 echo " <td width=\"18%\"><p align=\"left\"><input type=\"text\" ";
313 if (strlen($N_refresh))
314 {
315 echo "value=\"" . $N_refresh . "\" ";
316 }
317 echo "name=\"N\" size=\"50\"></p></td>\n";
318 echo " </tr>\n";
319 echo " <tr>\n";
320 echo " <td width=\"20%\" colspan=\"2\">\n";
321 echo " <p align=\"center\"><input type=\"submit\" value=\"";
322 echo $Buttontext;
323 echo "\" name=\"B1\" style=\"margin-top: 12\"></td>\n";
324 echo " </tr>\n";
325 echo "</table>\n";
326 echo "</form>\n";
327 }
328
329 function do_err_msg($Err_msg)
330 {
331 echo "<p align=\"center\"><b><font color=\"#FF0000\">";
332 echo $Err_msg;
333 echo "</font></b></p>\n";
334 }
335
336 //Prints algorithm notes with no extraneous HTML (no horizontal lines, etc.)
337 //
338 function pfact18_algorithm_notes($cgi_max)
339 {
340 ?>
341 <p><b><u>Algorithm Notes:</u></b></p>
342 <ul>
343 <li>This web page uses trial division combined with the
344 <a href="http://mathworld.wolfram.com/EratosthenesSieve.html">Sieve of Eratosthenes</a>
345 with a sieve of 2,310 = 2 * 3 * 5 * 7 * 11 elements.&nbsp; The
346 sieve is automatically generated, automatically compacted into a
347 difference table containing 480 elements, and packaged as a C-language source
348 file containing a 480-element lookup table of
349 integers.&nbsp; The algorithm checks divisibility by increasing trial divisors,
350 but it does so with all multiples of 2, 3, 5, 7, and 11 omitted (this is the
351 role of the Sieve of Eratosthenes).</li>
352 <li>Although this web page does factor effectively,
353 it is strictly "parlor amusement" grade, and will answer questions
354 such as <i>Is the year I was born a prime number?</i> or <i>Is my street address
355 prime?</i>, but is inadequate for serious factoring.&nbsp; Because this CGI-BIN
356 application runs on a shared server, it protects itself by only allowing
357 <?php echo " " . $cgi_max . " "; ?>seconds to elapse while factoring.&nbsp; The busier
358 the server is, the less actual CPU time is represented by
359 <?php echo " " . $cgi_max . " "; ?>seconds of elapsed time.&nbsp; This means that
360 factoring operations may be less successful when the server is busy.</li>
361 <li>This utility uses the <a href="http://www.swox.com/gmp">GMP library</a>
362 for arithmetic.&nbsp; The limit of 18-digit integers is in place so that
363 machine-native integers can be used for the trial divisor (it is more
364 efficient that way, and the GMP provides special function calls
365 for small divisors).&nbsp; Since the trial divisor need only attain
366 the square root of the number to be factored, any trial divisor for
367 an 18-digit integer will fit in one machine-native integer.</li>
368 </ul>
369 <?php
370 }
371
372 function pfact18_print_tabular_results(&$style,
373 $cgi_result,
374 $cgi_result_nelem,
375 $mr_nrounds,
376 $mr_pcntprime,
377 $mr_recip,
378 $cgi_max)
379 {
380 //Add commas to the number to factor, the number of Miller-Rabin rounds, and
381 //the timeout.
382 pfact18_commanate($cgi_result[1]);
383 pfact18_commanate($cgi_result[2]);
384 pfact18_commanate($cgi_result[3]);
385
386 //Add commas to each prime factor and its multiplicity.
387 $nfactors = ($cgi_result_nelem - 6)/3;
388
389 for ($i=0; $i<$nfactors; $i++)
390 {
391 pfact18_commanate($cgi_result[$i * 3 + 5]);
392 pfact18_commanate($cgi_result[$i * 3 + 6]);
393 }
394
395 //echo "<br>" . $cgi_result_nelem . "<br>";
396
397 //Announce the overall result.
398 $print_table = 0;
399 echo "<p align=\"center\"><font size=\"4\">";
400 if (($cgi_result[$cgi_result_nelem - 5] == "P") && ($cgi_result_nelem == 9) && ($cgi_result[$cgi_result_nelem - 3] == "1"))
401 {
402 echo "The integer " . $cgi_result[1] . " is prime (with 100% certainty).";
403 }
404 elseif (($cgi_result[$cgi_result_nelem - 5] == "p") && ($cgi_result_nelem == 9))
405 {
406 echo "Based on " . $mr_nrounds . " applications of the Miller-Rabin test, the integer ";
407 echo $cgi_result[1] . " is probably (with " . $mr_pcntprime . "% probability) ";
408 echo "prime.&nbsp; (This means that there is no more than 1 chance ";
409 echo "in " . $mr_recip . " that this integer is composite.)";
410 }
411 elseif (($cgi_result[$cgi_result_nelem - 5] == "C") && ($cgi_result_nelem == 9))
412 {
413 echo "The integer " . $cgi_result[1] . " has been verified by the Miller-Rabin test ";
414 echo "to be composite.&nbsp; However, ";
415 echo "due to server CPU time restrictions (" . $cgi_max . " seconds of elapsed time), ";
416 echo "it was not possible to make any progress in factoring ";
417 echo "this integer.&nbsp; Please try again when the server is less active ";
418 echo "or try another factoring resource.";
419 }
420 elseif ($cgi_result[$cgi_result_nelem - 5] == "P")
421 {
422 echo "The composite integer " ;
423 echo $cgi_result[1] . " was successfully factored into its prime components with ";
424 echo "100% certainty.&nbsp; Its prime factors and their multiplicities are listed ";
425 echo "in the table below.";
426 $print_table = 1;
427 }
428 elseif ($cgi_result[$cgi_result_nelem - 5] == "p")
429 {
430 echo "The composite integer " ;
431 echo $cgi_result[1] . " was successfully factored into its prime components, ";
432 echo "and these prime components and their multiplicities are listed in the ";
433 echo "table below.&nbsp; ";
434 echo "The last component listed in the table was judged to be prime based on ";
435 echo $mr_nrounds . " applications of the Miller-Rabin test, meaning that it is ";
436 echo $mr_pcntprime . "% probable ";
437 echo "that this last component is prime (i.e. that there is no more than 1 chance ";
438 echo "in " . $mr_recip . " that it is composite).";
439 $print_table = 1;
440 }
441 elseif ($cgi_result[$cgi_result_nelem - 5] == "C")
442 {
443 echo "Due to server CPU time restrictions (" . $cgi_max . " seconds of elapsed time), ";
444 echo "the integer ";
445 echo $cgi_result[1] . " could only be partially factored.&nbsp; In the results below, note that ";
446 echo "the last component ";
447 echo "listed bears the category code <i>C</i> (for <u>c</u>omposite).&nbsp; Please ";
448 echo " try again when the server is less active ";
449 echo "or try another factoring resource.";
450 $print_table = 1;
451 }
452 echo "</p></font>";
453
454 //Print the table if demanded.
455 if ($print_table)
456 {
457 $style->hrule_std();
458
459 //Assign the table column widths. They are centralized here for easy change.
460 $width[0] = 10;
461 $width[1] = 10;
462 $width[2] = 10;
463 $width[3] = 10;
464
465 echo "<p><table align=\"center\" border=\"1\" width=\"90%\">\n";
466
467 for ($i=0; $i <= ($cgi_result_nelem/3 - 2); $i++)
468 {
469 //Factor number.
470 echo "<tr>\n";
471
472 echo " <td width=\"" . $width[0] . "%\">\n";
473 if ($i==0)
474 {
475 echo " <p align=\"center\"><b>Factor<br>Number</b></p>\n";
476 }
477 else
478 {
479 echo " <p align=\"center\">" . $i . "</p>\n";
480 }
481 echo " </td>\n";
482
483 //Prime Factor
484 echo " <td width=\"" . $width[1] . "%\">\n";
485 if ($i==0)
486 {
487 echo " <p align=\"center\"><b>Component<br>Factor</b></p>\n";
488 }
489 else
490 {
491 echo " <p align=\"center\">" . $cgi_result[$i * 3 + 2] . "</p>\n";
492 }
493 echo " </td>\n";
494
495 //Multiplicity.
496 echo " <td width=\"" . $width[2] . "%\">\n";
497 if ($i==0)
498 {
499 echo " <p align=\"center\"><b>Multiplicity</b></p>\n";
500 }
501 else
502 {
503 echo " <p align=\"center\">" . $cgi_result[$i * 3 + 3] . "</p>\n";
504 }
505 echo " </td>\n";
506
507 //Category code.
508 echo " <td width=\"" . $width[3] . "%\">\n";
509 if ($i==0)
510 {
511 echo " <p align=\"center\"><b>Category<br>Code</b></p>\n";
512 }
513 else
514 {
515 echo " <p align=\"center\">" . $cgi_result[$i * 3 + 1] . "</p>\n";
516 }
517 echo " </td>\n";
518
519
520 echo "</tr>\n";
521 }
522
523 echo "</table></p>\n";
524 echo "<p align=\"center\"><b>Table legend:</b>&nbsp; <b>P</b>=prime with absolute certainty, ";
525 echo "<b>p</b>=prime established by Miller-Rabin test with ";
526 echo $mr_pcntprime . "% certainty, and <b>C</b>=composite established by Miller-Rabin test ";
527 echo "with absolute certainty, but not factorable in the time allowed.</p>\n";
528
529 $style->hrule_std();
530 pfact18_algorithm_notes($cgi_max);
531 }
532 }
533 //
534 //Main script begins here.
535 //
536 //Let's agree on a number of rounds for the Miller-Rabin test. This influences the
537 //probabilities.
538 $miller_rabin_nrounds = 25;
539 //
540 //Let's agree how long the CGI may take to factor.
541 $max_cgi_time = 10;
542 //
543 //We need to establish the probability that a number which passes the rounds specified
544 //above is still in fact composite. This values need to be calculated by hand whenever
545 //the value above is changed.
546 $miller_rabin_p_real = "0.99999999999999911182";
547 $miller_rabin_p_percent = "99.999999999999911182";
548 $miller_rabin_residual_real = "0.00000000000000088818";
549 $miller_rabin_residual_percent = "0.000000000000088818";
550 $miller_rabin_residual_lt_reciprocal = "1,125,899,906,842,624";
551 //
552 $style = new Stdnwpstyle;
553 //Assign the current style in force. Also, starts the CPU
554 //usage clock.
555
556 //Do the header unconditionally. The header is always used on this page.
557 do_header($style);
558 //
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->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->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 = "./arith_large_cgi 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->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->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 ?>

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25