Re: [MacPerl] BigInt sluggishness.

[David Steffen <steffen@biomedcomp.com>]

>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. My problem is in how I'm trying to represent the class
>times. I have a 71 digit number, each digit representing an hour of the week
>during which classes can meet. It's a zero if there's no class at that hour,
>one if there is (plus a one at the beginning or else it thinks i'm trying an
>octal number?):
>
>Basketweaving 101: 1000000111000000000000000111000000000000000000000
>
>My problem is, quite simply, it's a 71 digit number, which gets chopped down
>to 15 digits without Math::BigInt, and Math::BigInt is far too slow. A large
>schedule can require 15,000+ iterations to check all the classes (I don't
>mind waiting myself, but this may end up on a server eventually). When I
>benchmarked BigInt vs. normal addition (with smaller numbers) it was over
>ten times slower. Is there a better alternative?

I don't have time to put together a test script right this second, 
but it seems to me that doing this using a binary representation 
(e.g. 00100 = 4) and the binary "&" operator might be faster and 
better.

Note the following preliminary thoughts:

1) How you represent the input is independent of how you do the 
calculation; the Perl Cookbook has a nice method for converting your 
representation, above, into its equivalent in binary.

2) Even given the compression implicit in the use of a binary 
equivalent, 71 digits is probably too big.  In that case, you can 
divide it into three numbers, which means you will have to do three & 
operations instead of one, but I bet it will still be much faster 
than what you are doing.

I'll try to put this together as an example tomorrow.

-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