I recently added some functionality for random number generation to my modules, which led me on a digression about rand(). This is a short look at some modules for getting random floating point values. A later one will look at random ints and bytes.
Modules for rand()
Module
Algorithm |
Stat
Quality |
Interval |
Bits in
output |
Auto
Seed |
Predictable |
Speed |
CORE::rand
drand48 |
Bad |
[0,1) |
48 |
OK |
Yes |
29000 k/s |
Math::Random::MTwist
MT XS |
OK |
[0,1) |
53 |
OK |
Yes |
14000 k/s |
ntheory
ChaCha20 XS |
Good |
[0,1) |
53-113 |
Full |
No |
12000 k/s |
Math::Prime::Util::GMP
ISAAC XS |
Good |
[0,1) |
53-64 |
Good |
No |
14000 k/s |
Crypt::PRNG
Fortuna XS |
Good |
[0,1) |
53 |
Good |
No |
700 k/s |
Math::Random::MT::Auto
MT XS |
OK |
[0,1) |
52 |
Full |
Yes |
5000 k/s |
Math::Random::MT
MT XS |
OK |
[0,1) |
32 |
rand() |
Yes |
2200 k/s |
Math::Random::Secure
Math::Random::ISAAC |
Good |
[0,1) |
32 |
Full |
No |
460 k/s |
Math::Random::ISAAC
ISAAC XS or PP |
Good |
[0,1] |
32 |
None |
No |
5700 k/s
480 k/s |
Math::Random::Xorshift
Xorshift XS |
OK |
[0,1] |
32 |
Time |
Yes |
16000 k/s |
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.
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.
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 |
Order anti-lex |
Order lexico |
Restrict count |
Restrict size |
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 |
- |
|
|
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) |
Perl |
no (73) yes(90) |
no |
no |
no |
21 |
- |
|
C/Pari |
no |
no |
yes |
yes |
100 |
34,000,000 |
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 |
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.