A comparison of memory use for primality modules

Performance and memory use are two areas of concern for many libraries. Last December I made a number of changes in my Math::Prime::Util module to reduce memory use, and bulk88 helped really tweak some of the XS. I thought I'd pick a simple task and look at the speed and memory use of a number of solutions.

isprime from 1 to 10 million
Memory Time Solution
2096k 72.6s Perl trial division mod 6
2100k 124.8s Perl trial division
3652k 36.2s Math::GMP
3940k 14.8s Math::GMPz
4040k 1.9s Math::Prime::Util (no GMP backend)
4388k 1.9s Math::Prime::Util (with GMP backend)
4568k 1.4s Math::Prime::Util (GMP + precalc)
4888k 4.4s Math::Prime::XS
5316k 245.1s Math::Primality
5492k 29.8s Math::Pari
6260k 1.5s Math::Prime::FastSieve
~16MB >1 year regex

Math::Prime::Util, May update

Math::Prime::Util 0.41 was released, with new functions (valuation, invmod, vecsum, binomial, forpart), and the usual crop of performance improvements. In particular, primality testing on x86_64 got another big speedup.

Fun with binomials

I decided to add a binomial(n,k) function to Math::Prime::Util, and found some interesting things while doing it. Overflow detection and mitigation in C and Perl were the first thing. Next was looking at negative arguments, which led to finding some differences in various solutions as well as filing a bug report for Math::BigInt.

Math::Prime::Util, April update

Math::Prime::Util, and the optional Math::Prime::Util::GMP back end, are a set of modules for number theory in Perl, with a large overlap of functionality with PARI/GP. This is an update on some of the things that were new in the April release (0.40 of MPU, 0.19 of MPU::GMP).

The usual speed improvements in various areas, some approximation improvements, and new functions. Primality testing benchmarks also show Perl has state of the art solutions.

Factoring integers in Perl

Recently I've been working on factoring and primality proofs (with certificates) for Math::Prime::Util. I thought I'd give a brief summary and comparison of the modules I know of for factoring integers from Perl.

About Dana Jacobsen

user-pic I've been using Perl since 1991 (4.010 or so). At some point I realized that while I have used many languages, I enjoy using Perl more than any others.