Re: [MacPerl] BigInt sluggishness.

[David Steffen <steffen@biomedcomp.com>]

Brian Boucheron wrote:

>I am trying to create a program that, when given a list of classes and their
>meeting time, will sort through and output every possible combination where
>no classes overlap.
>...
>It's a zero if there's no class at that hour, one if there is
>
>Basketweaving 101: 1000000111000000000000000111000000000000000000000

I promised an example of how to do this using binary operators.  In 
the mean time, Jim Miner posted a solution using the Bit::Vector 
module that may well be better, but a promise is a promise so here is 
my (possibly wheel-reinventing) solution:

#! /usr/bin/perl
#
# The first line is not necessary for MacPerl, but since I move between
# ...platforms a lot, it is a habit of mine.
#
# binary_compare.plx
# by David Steffen, 2000
# Do with this as you like.
#
# Purpose: to illustrate an idea to the MacPerl mailing list
#
# The code below is a bit sloppy, I don't use any of the recommended
# ...perl error checking, for example.  In fact, there is virtually no
# ...error checking of any kind.  Do not do as I do :-)

# Input to the program will be sets of strings where each position in the
# ...string represents a time block (hour?) in which a course might be held,
# ...where time blocks used are indicated by the character '1', and those
# ...not used by the character '0'
# Strings are expected to be 72 characters long.  Error checking for strings
# ...in the wrong format should be added.
# In my hands, MacPerl cannot store 2**71 (or 2**72) as an integer, but
# ...converts it to an imprecise floating point number.  However, MacPerl
# ...does fine with 2**36, so I split the string in half and use each half
# ...to generate two integers.  Thus, the working data structure is an
# ...array of two integers, representing the number encoded in binary by
# ...the two halves of the string.

$a = 
"000101010101010100001011101011010101110101000001010101010101110101110 
001";
$b = 
"011000000000000000000000000000000000000000000000000000000000000000000 
000";

@a = &encode($a);
@b = &encode($b);
print &decode(@a), "\n";
print &decode(@b), "\n";

if( &test(@a, @b) ) {
     print "conflict!\n";
} else {
     print "courses fit.\n";
}

print "-----\n";

@c = &merge(@a, @b);
print &decode(@a), "\n";
print &decode(@c), "\n";

if( &test(@a, @c) ) {
     print "conflict!\n";
} else {
     print "course fits.\n";
}

# The program defines four functions:
#  * &encode($string) converts the input data into a working form.
#  * &decode(@array) does the reverse.
#  * &test(@array1, @array2) compares two datasets to see if there is 
an overlap
#  * &merge(@array1, @array2) is used to "accumulate" courses, to create a
#    master dataset indicated which time blocks have been used so far.
#
# I don't know if these are the functions needed, but I thought they 
illustrated
# ...my point.

sub encode {
     # &encode($string) takes one of the input strings
     # and converts it to a two element integer array, where
     # the first element in the array represents the numeric
     # equivalent of the first 36 characters in the string, and
     # the second element the last 36 characters.
     my @retval= unpack("a36a36", $_[0]);
     $retval[0] = unpack("N", pack("B36", substr("0" x 32 . $retval[0], -36)));
     $retval[1] = unpack("N", pack("B36", substr("0" x 32 . $retval[1], -36)));
     return @retval;
}

sub decode {
     # accepts the 2 element integer array internal data structure,
     # returns a 72 character string.
     return unpack("B36", pack("N", $_[0])) . unpack("B36", pack("N", $_[1]));
}

sub test {
     # Using the binary representation of the strings, determines if the
     # two timesets (a timeset either being an original course or an
     # accumulation of courses resulting from the &merge() function)
     # have any overlap.
     #
     # Use the passed parameter array, @_, as is with no error checking.
     # Note that everything passed to a function in perl is made into one
     # long list.  Thus, the two, two element arrays passed to the function
     # arrive as one 4 element array.
     return ($_[0] & $_[2]) && ($_[1] & $_[3]);
}

sub merge {
     # Using the binary representation of the input strings, merges them
     # into one dataset combining the hours used in both.
     #
     # Use the passed parameter array, @_, as is with no error checking.
     # Note that everything passed to a function in perl is made into one
     # long list.  Thus, the two, two element arrays passed to the function
     # arrive as one 4 element array.
     my @retval;
     $retval[0] = $_[0] | $_[2];
     $retval[1] = $_[1] | $_[3];
     return @retval;
}
__END__

HTH

-David-
David Steffen, Ph.D.
President, Biomedical Computing, Inc. <http://www.biomedcomp.com/>
Phone: (713) 610-9770 FAX: (713) 610-9769 E-mail: steffen@biomedcomp.com

# ===== Want to unsubscribe from this list?
# ===== Send mail with body "unsubscribe" to macperl-request@macperl.org