Base conversion

Earlier this year I added some commands to the ntheory module, inspired by Pari/GP and Mathematica, to split numbers into digits and put them together again. Of course this isn't terribly exciting by itself since Perl has split and join, but with optional bases it gets more interesting.

I recently took a look at the various modules that do base conversion (at least 9 modules, plus various standalone subroutines). Each has slightly different features and interfaces, and the performance at the extremes differs by over 10,000x. I've made some internal changes to ntheory based on my tests, which should show up in the next release.

Add: This is for Perl 5. Perl6 has native support for base conversions for bases 2-36 and seamless Bigint support. It Just Works. For larger bases or alternate encodings, bbkr's TinyID module can be used.

Short survey of modules for combinations and permutations

This is a short look at some modules for generating combinations and permutations. There are likely more modules that aren't listed. RosettaCode has examples of writing the combinations and permutations functions by hand.

Combinations and Permutations
Module Impl Comb Perm Comb w/rep Perm w/rep Derange Speed Order Comments
Algorithm::Combinatorics XS yes yes yes yes yes + Lexico Fast iterator or array
ntheory XS yes yes no no no ++ Lexico Fast block call
Math::Combinatorics Perl yes yes no no yes - - Impl Iterator or array
Algorithm::FastPermute XS no yes no no no +++ Impl Fast block call
Algorithm::Permute XS no yes no no no + Impl Iterator or fast block call
Algorithm::Loops Perl no yes no no no + Impl Iterator
List::Permutor Perl no yes no no no - Lexico Iterator
Iterator::Misc Perl no yes no no no - - Lexico Iterator
Math::Permute::Array Perl no yes no no no - - Impl Iterator or index
Math::Permute::List Perl no yes no no no Impl Block call
Math::GSL::Permutation XS no yes no no no - Lexico function interface
Math::Disarrange::List Perl no no no no yes Impl Block call
Math::GSL::Combination XS yes no no no no + Lexico iterator or by index

Partitions of an Integer

The subject of integer partitions comes up regularly, with multiple threads over the years at PerlMonks, a big chunk of Chapter 5 of Higher-Order Perl, and some pages from Knuth TAOCP volume 4A. Last year I added a partitions function to my ntheory Perl module, for counting integer partitions (OEIS A000041). A few months ago I added a partition iterator (forpart) since I liked the one Pari/GP added last year.

Integer partitions
Solution Impl
Max in 10s Count in 10s
ntheory 0.45 XS yes no yes yes 87 223,000
ntheory 0.45 Perl yes no yes yes 72 7,300
Integer::Partition 0.05 Perl yes yes no no 67 -
(unreleased, from Limbic 2004)
Perl no yes no no 62 6,000
MJD 2013 Perl no no no no 71 -
blokhead 2007 Perl yes no no no 63 -
kvale 2004 Perl yes no no no 62 -
sfink 2004 Perl yes no no no 58 -
tye 2001 Perl no no no no 58 -
(golfed, 73 chrs)
no (73)
no no no 21 -
Pari/GP 2.8.0
(not a Perl module!)
C/Pari no no yes yes 100 34,000,000

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.