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

Annotation 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 - (hide 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 dashley 23 <?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