Ovid wrote:
Hi all,
I was doing a bit of work with math and realized I couldn't find a
simple, non-XS math module on the CPAN. I'm looking for something
which handles very simple functions such as factoring numbers, finding
highest common factors, lowest common multiples, etc. Are there any
pure Perl modules which handle this? The functions aren't too hard to
write, but I'm surprised they are not out there, so I assume I missed a
module.
Are you interested in working with Big Integers, or 32-bit types? I ask
because Math::BigInt has
bgcd() and blcm() functions.
As a corollary, many common math functions require efficiently listing
prime numbers (or determining if a given number is prime). Again, are
there any pure Perl modules which handle this (relatively) efficiently?
Also, is there any reasonably simple way of generating those numbers
which is faster than the Sieve of Atkins?
(http://en.wikipedia.org/wiki/Prime_numbers#Pseudocode_for_programs_to_find_primes,
or http://tinyurl.com/y5cws2). Wikipedia suggests there isn't, but I'd
rather be cautious.
Actually, Wikipedia merely says that Atkins is more efficient than
Eratosthenes, not that it's the
most efficient. With reason. It depends upon what range of integers
you want to factor. In fact,
in one of the math newsgroups that I read, its been stated that for
numbers in the 32-bit range,
brute force is actually the fastest. It isn't until you reach much
larger sizes that you have to
worry about Quadratic Sieves
(<http://en.wikipedia.org/wiki/Quadratic_Sieve>) and Number Field Sieves
(<http://en.wikipedia.org/wiki/General_number_field_sieve>).
-john
