JCSBimp's Hexagonal Orthogonal

This won’t set any algorithmic speed records, but I am happy with it, for now. It comes in at 48 lines of Perl code. factor_it_4.pl is definitely faster than factor_it_3.pl, and routinely gets its answer in fewer than half the iterations of factor_it_2.pl.

Once again, I am not experienced with writing arbitrary-precision arithmetic scripts in Perl (I have used Magma for such purposes, but do not have a Magma license at the present time). Those who can program for arbitrarily large integers are welcome to have at it. Again, though, this is not to my knowledge one of the speedier algorithms like the modern “sieve” techniques. It simply uses the Ceiling Square and characteristic polynomial concepts I have worked out to good effect.

EDITED TO ADD: I corrected the upper loop bound, albeit a little sloppily.

Sample Run:

➜  Programs factor_it_4.pl 169350257651 
Factorization found: 169350257651 = 255859 * 661889.
Result found in 23677 iterations.

Program Code for factor_it_4.pl:

#!/usr/bin/perl
use strict;
use warnings;
use POSIX qw/ceil/;

my $m = $ARGV[0];
my $twopow = 0;
my ( $idx, $fidx, $ridx );
my $m_orig = $m;
while ( ( $m % 2 ) == 0 ) {
  $twopow++;
  $m /= 2;
}
if ( $twopow ) {
  print "$m_orig has a factor of 2 to the power of $twopow.\n";
  if ( $m == 1 ) {
    print "$m_orig has no other factors.\n";
    exit;
  }
  else {
    print "Proceeding with factorization of $m.\n";
  }
}
my $c0 = ceil( sqrt( $m ) ); # ceiling square of m
my $mm4 = $m % 4;
my $cc2 = $c0 % 2;
my $add1 = 0;
if ( ( ( $mm4 == 1 ) && ( $cc2 == 0 ) )
     || ( ( $mm4 == 3 ) && ( $cc2 == 1 ) ) ) {
  $add1 = 1;
}
my $r0 = $c0 * $c0 - $m;
my $notdone = 1;
my $n_iters = 1;
for ( $idx = $add1; ( $idx < $m ) && $notdone; $idx += 2 ) {
  $fidx = $idx * $idx + 2 * $c0 * $idx + $r0;
  $ridx = ceil( sqrt( $fidx ) );
  if ( ( $ridx * $ridx ) == $fidx ) {
    print "Factorization found: $m = ", $c0 + $idx - $ridx;
    print " * ", $c0 + $idx + $ridx, ".\n";
    print "Result found in $n_iters iterations.\n";
    $notdone = 0;
  }
  $n_iters++;
}
if ( $notdone ) { # We tried!
  print "Unable to factor $m.\n";
}