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