After extensive study, and a great many discoveries which seemed exciting to me but that after investigation boiled down to properties of established concepts, I have been able to construct an algorithm that uses the difference between m and the smallest greater perfect square s to search for appropriate values of c and thus find p. Though this relates to the concept of the family of polynomials, they in themselves do not figure directly into this solution. I greatly doubt I have constructed an algorithm that is faster than, or even considerably different from, known approaches. However, the number of iterations in this algorithm is usually less than m, sometimes quite a bit less, and calculations are economically few. Considering the simplicity of the program code in terms of the number of calculations required, it may be an attractive and convenient algorithm for mathematicians to use.
The Factorization Program, in Perl
To run this on a terminal command line for Unix/Linux/MacOS/etc., save it as a Perl program with whatever name you like – in this example it is “factor_it.pl” – make it executable, and then type
factor_it.pl <the number you wish to factor>
The Perl code follows:
#!/usr/bin/perl
use strict;
use warnings;
use POSIX qw/floor/;
use POSIX qw/ceil/;
# Declare constants.
my $m = $ARGV[0];
my ( $r, $s, $rs, $c1, $n, $the_val );
my $s_even;
my $not_special = 1;
my $n_iters = 0;
my $not_done = 1;
# Initialize calculated values.
$s = ceil( sqrt( $m ) );
if ( ( $s % 2 ) == 0 ) {
$c1 = 1;
}
else {
$c1 = 2;
}
$r = $s * $s – $m;
$rs = floor( sqrt( $r ) );
# Handle the special cases where $m or $r are perfect squares.
if ( $r == 0 ) { # m is a perfect square
$not_done = 0;
$not_special = 0;
print “Done! Special case: $m is the square of $s.\n”;
}
if ( $r > 0 && $r == ( $rs * $rs ) ) { # r is a perfect square
$not_done = 0;
$not_special = 0;
print “Done! Special case: $m is the difference of perfect squares.\n”;
print ” $m = “, $s – $rs, ” * “, $s + $rs, “.\n”;
}
# Traverse the appropriate ceiling square line until you hit 0.
while ( ( $c1 < $s ) && $not_done ) {
if ( ( $m % ( $s – $c1 ) ) == 0 ) {
$not_done = 0;
}
if ( $not_done ) {
$c1 += 2;
$n_iters++;
}
}
if ( $not_special ) {
print “Done! m = $m = “, $s – $c1, ” * “, $m / ( $s – $c1 ), “.\n”;
print ” Completed in $n_iters iterations.\n”;
}
Leave a Reply Cancel reply