Integer Factorization: Series of Ceiling Squares, Take 3 (or 4)

Advertisements

I embarrassed myself twice this week, having to take down insufficiently debugged algorithms and Perl code for not testing thoroughly enough. However, I now have an algorithm I’ve once again tested, and will test some more (yes, opening the possibility that a bug will require me to correct/retract), and this one has a symmetric quality that my previous strategy lacked. The error – and the asymmetry – was in how I handled the case of remainders that were multiples of 4.

The algorithm:

Here are instructions to derive the Ceiling Square for a positive integer m
in such a way that a Series of Ceiling Squares formed from successive remainders
will terminate.

If m is a perfect square, it is equal to its Ceiling Square.

Otherwise:

m = c^2 - r, where

c is either ceil(sqrt(m)) or ceil(sqrt(m))+1 as follows:

Case 1: m is odd.

Choose c to be the even or odd one of those two choices when (m+1/2) is even or odd,
 respectively.

This corresponds to whether m is congruent to 3 or 1 modulo 4.

m is congruent to 3 modulo 4:
 c is even, c^2 is congruent to 0 modulo 4, and therefore
 r will be congruent to 1 modulo 4.

m is congruent to 1 modulo 4:
 c is odd, c^2 is congruent to 1 modulo 4, and therefore
 r will be congruent to 0 modulo 4.

Case 2: m is even.

c is either ceil(sqrt(m)) or ceil(sqrt(m))+1 as follows:

Select which value of c as follows, according to whether m is congruent to 0 or 2 modulo 4.

m is congruent to 0 modulo 4:
  c is always ceil(sqrt(m)).

m is congruent to 2 modulo 4:
  If c is even, add 1 to make c odd.

The Perl script:

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

my $remain = $ARGV[0];
my ( $croot, $csquare );

print "The Series of Ceiling Roots of $remain:\n  ";
while ( $remain > 0 ) {
  $croot = ceiling_root( $remain );
  print "$croot ";
  $csquare = $croot * $croot;
  $remain = $csquare - $remain;
}
print "$remain\n";

sub ceiling_root {
  my $the_int = $_[0];
  my ( $the_root, $crit_bit );

  if ( ( $the_int % 2 ) == 1 ) {
    $the_root = ceil( sqrt( $the_int ) );
    $crit_bit = ( ( $the_int + 1 ) / 2 ) % 2;
    if ( ( $the_root % 2 ) != $crit_bit ) {
      $the_root++;
    }
  }
  else {
    $the_root = ceil( sqrt( $the_int ) );
    if ( ( $the_int % 4 ) != 0 ) {
      if ( ( $the_root % 2 ) == 0 ) {
        $the_root++;
      }
    }
  }
  return $the_root;
}

Leave a ReplyCancel reply