1, only the least significant digit is
//considered.
function pfact18_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 pfact18_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 (!pfact18_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 pfact18_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 pfact18_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 pfact18_decommanate(&$arg)
{
$temp = "";
$len = strlen($arg);
for ($i=0; $i<$len; $i++)
{
$c = (string)Substr($arg, $i, 1);
if (pfact18_isdigit($c) || ($c == "-"))
$temp = $temp . $c;
}
$arg = (string)$temp;
}
//Commanates an integer which is assumed to by syntactically correct.
function pfact18_commanate(&$arg)
{
pfact18_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("[Attempted] Prime Factorization Of An Integer (18 Or Fewer Digits)",
"Prime Factorization Of An Integer (18 Or Fewer Digits)",
"This utility attempts to factor an integer of 18 or fewer digits into its " .
"prime components.");
}
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($N_refresh, $Buttontext) { echo "\n"; } function do_err_msg($Err_msg) { echo ""; echo $Err_msg; echo "
\n"; } //Prints algorithm notes with no extraneous HTML (no horizontal lines, etc.) // function pfact18_algorithm_notes($cgi_max) { ?>Algorithm Notes:
"; if (($cgi_result[$cgi_result_nelem - 5] == "P") && ($cgi_result_nelem == 9) && ($cgi_result[$cgi_result_nelem - 3] == "1")) { echo "The integer " . $cgi_result[1] . " is prime (with 100% certainty)."; } elseif (($cgi_result[$cgi_result_nelem - 5] == "p") && ($cgi_result_nelem == 9)) { echo "Based on " . $mr_nrounds . " applications of the Miller-Rabin test, the integer "; echo $cgi_result[1] . " is probably (with " . $mr_pcntprime . "% probability) "; echo "prime. (This means that there is no more than 1 chance "; echo "in " . $mr_recip . " that this integer is composite.)"; } elseif (($cgi_result[$cgi_result_nelem - 5] == "C") && ($cgi_result_nelem == 9)) { echo "The integer " . $cgi_result[1] . " has been verified by the Miller-Rabin test "; echo "to be composite. However, "; echo "due to server CPU time restrictions (" . $cgi_max . " seconds of elapsed time), "; echo "it was not possible to make any progress in factoring "; echo "this integer. Please try again when the server is less active "; echo "or try another factoring resource."; } elseif ($cgi_result[$cgi_result_nelem - 5] == "P") { echo "The composite integer " ; echo $cgi_result[1] . " was successfully factored into its prime components with "; echo "100% certainty. Its prime factors and their multiplicities are listed "; echo "in the table below."; $print_table = 1; } elseif ($cgi_result[$cgi_result_nelem - 5] == "p") { echo "The composite integer " ; echo $cgi_result[1] . " was successfully factored into its prime components, "; echo "and these prime components and their multiplicities are listed in the "; echo "table below. "; echo "The last component listed in the table was judged to be prime based on "; echo $mr_nrounds . " applications of the Miller-Rabin test, meaning that it is "; echo $mr_pcntprime . "% probable "; echo "that this last component is prime (i.e. that there is no more than 1 chance "; echo "in " . $mr_recip . " that it is composite)."; $print_table = 1; } elseif ($cgi_result[$cgi_result_nelem - 5] == "C") { echo "Due to server CPU time restrictions (" . $cgi_max . " seconds of elapsed time), "; echo "the integer "; echo $cgi_result[1] . " could only be partially factored. In the results below, note that "; echo "the last component "; echo "listed bears the category code C (for composite). Please "; echo " try again when the server is less active "; echo "or try another factoring resource."; $print_table = 1; } echo "
"; //Print the table if demanded. if ($print_table) { $style->hrule_std(); //Assign the table column widths. They are centralized here for easy change. $width[0] = 10; $width[1] = 10; $width[2] = 10; $width[3] = 10; echo "\n";
if ($i==0)
{
echo " Factor " . $i . " \n"; } echo " | \n";
//Prime Factor
echo " \n";
if ($i==0)
{
echo " Component " . $cgi_result[$i * 3 + 2] . " \n"; } echo " | \n";
//Multiplicity.
echo " \n";
if ($i==0)
{
echo " Multiplicity \n"; } else { echo "" . $cgi_result[$i * 3 + 3] . " \n"; } echo " | \n";
//Category code.
echo " \n";
if ($i==0)
{
echo " Category " . $cgi_result[$i * 3 + 1] . " \n"; } echo " | \n";
echo "
Table legend: P=prime with absolute certainty, "; echo "p=prime established by Miller-Rabin test with "; echo $mr_pcntprime . "% certainty, and C=composite established by Miller-Rabin test "; echo "with absolute certainty, but not factorable in the time allowed.
\n"; $style->hrule_std(); pfact18_algorithm_notes($cgi_max); } } // //Main script begins here. // //Let's agree on a number of rounds for the Miller-Rabin test. This influences the //probabilities. $miller_rabin_nrounds = 25; // //Let's agree how long the CGI may take to factor. $max_cgi_time = 10; // //We need to establish the probability that a number which passes the rounds specified //above is still in fact composite. This values need to be calculated by hand whenever //the value above is changed. $miller_rabin_p_real = "0.99999999999999911182"; $miller_rabin_p_percent = "99.999999999999911182"; $miller_rabin_residual_real = "0.00000000000000088818"; $miller_rabin_residual_percent = "0.000000000000088818"; $miller_rabin_residual_lt_reciprocal = "1,125,899,906,842,624"; // $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 N was supplied, decommanate it and be sure it is a string. if (isset($N)) pfact18_decommanate($N); // //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($N)) { //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("", "Attempt To Factor Integer"); } elseif (!pfact18_issimpleint($N)) { //N is supplied, but is malformed. Need to advise. do_err_msg("N is a malformed integer. Choose a new value for N and try again."); $style->hrule_std(); pfact18_commanate($N2); do_form($N, "Attempt To Factor Integer"); } elseif (strlen($N) > 18) { //N is supplied, but is too long. Need to advise. do_err_msg("N is too long (the maximum is 18 digits). Choose a new value for N and try again."); $style->hrule_std(); pfact18_commanate($N); do_form($N, "Attempt To Factor Integer"); } else { //N is supplied and seems to be a valid integer. // //If N is negative, make it positive. if (Substr($N, 0, 1)=="-") $N = Substr($N, 1, strlen($N)-1); //If N is "0" or "1", make it "2". if ($N=="0") $N = (string)"1"; if ($N=="1") $N = (string)"2"; //We can now run the external program to do the calculation. $cgi_command_string = "./arith_large_cgi pfact_18 " . $N . " " . $miller_rabin_nrounds . " " . $max_cgi_time; //echo "CGI command string is : " . $cgi_command_string . "