Dana Jacobsen > Math-Prime-Util-0.20 > Math::Prime::Util::PrimeArray

Math-Prime-Util-0.20.tar.gz

Dependencies

Annotate this POD

Website

# CPAN RT

 Open 0
View/Report Bugs
Module Version: 0.14   Source   Latest Release: Math-Prime-Util-0.39

# NAME

Math::Prime::Util::PrimeArray - A tied array for primes

Version 0.14

# SYNOPSIS

```  use Math::Prime::Util::PrimeArray;

# Create:
my @primes;  tie @primes, 'Math::Prime::Util::PrimeArray';

# Use in a loop by index:
for my \$n (1..10) {
print "prime \$n = \$primes[\$n]\n";
}

# Use in a loop over array:
for my \$p (@primes) {
print "\$p\n";
last if \$p > \$limit;   # stop sometime
}

# Use via array slice:
print join(",", @primes[0..50]), "\n";

# Use via each:
use 5.012;
while( my(\$index,\$value) = each @primes ) {
print "The \${index}th prime is \$value\n";
last if \$p > \$limit;   # stop sometime
}

# Use with shift:
while ((my \$p = shift @primes) < \$limit) {
print "\$p\n";
}```

# DESCRIPTION

An array that acts like the infinite set of primes. This may be more convenient than using Math::Prime::Util directly, and in some cases it can be faster than calling `next_prime` and `prev_prime`.

Internally when an index is accessed, an area surrounding the index is sieved if necessary, then the result returned. This means random access will be a little slower than using `nth_prime` directly, but not by very much. Random access in a small window (1000 or so primes in either direction) will be very fast, as will sequential access in either direction.

Shifting acts like the array is losing elements at the front, so after two shifts, `\$primes[0] == 5`. Unshift will move the internal shift index back one, unless given an argument which is the number to move back (it silently truncates so it does not shift past the beginning). Example:

```  say shift @primes;     # 2
say shift @primes;     # 3
say shift @primes;     # 5
say \$primes[0];        # 7
unshift @primes;       #     back up one
say \$primes[0];        # 5
unshift @primes, 2;    #     back up two
say \$primes[0];        # 2```

# LIMITATIONS

The size of the array will always be shown as 2147483647 (IV32 max), even in a 64-bit environment where primes through `2^64` are available.

# PERFORMANCE

Summing the first 0.1M primes via walking the array:

```      40ms   3.3 MB    \$sum += \$_ for @{primes(nth_prime(100_000))};
300ms   0.6 MB    Math::Prime::Util::PrimeArray
230ms   2.2 MB    Math::NumSeq::Primes
10300ms  36.2 MB    Math::Primes::TiedArray (extend 1k)```

Summing the first 1M primes via walking the array:

```     0.3s   35.5 MB    \$sum += \$_ for @{primes(nth_prime(1_000_000))};
3.9s    1.3 MB    Math::Prime::Util::PrimeArray
9.6s    2.2 MB    Math::NumSeq::Primes
146.7s  444.9 MB    Math::Primes::TiedArray (extend 1k)```

Summing the first 10M primes via walking the array:

```       4s    365 MB    \$sum += \$_ for @{primes(nth_prime(10_000_000))};
2m        2 MB    Math::Prime::Util::PrimeArray
85m        2 MB    Math::NumSeq::Primes
>5000 MB    Math::Primes::TiedArray (extend 1k)```

Using Math::Prime::Util directly in a naive fashion uses lots of memory, but is extremely fast. Sieving segments at a time would control the memory use, which is one thing the `PrimeArray` tie is trying to do for you (but adds more inefficiency than is ideal).

Math::NumSeq::Primes offers an iterator alternative, and works quite well for reasonably small numbers. It does not, however, support random access. There seems to be a 2MB fixed overhead, but after that the memory use is is well constrained. It is very fast for small values, but clearly is getting slower as we sum to 1 million, and takes well over an hour to count to 10 million.

Math::Primes::TiedArray is remarkably impractical for anything other than very small numbers. I believe the times and memory use in the above tables illustrate this.

This module uses Math::Prime::Util to do all the work. If you're doing anything but retrieving primes, you should examine that module to see if it has functionality you can use directly, as it may be a lot faster or easier.

Similar functionality can be had from Math::NumSeq and Math::Prime::TiedArray.

# AUTHORS

Dana Jacobsen <dana@acm.org>