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

Math-Prime-Util-0.31.tar.gz

Dependencies

Annotate this POD

Website

# CPAN RT

 Open 1
View/Report Bugs
Module Version: 0.28   Source   Latest Release: Math-Prime-Util-0.58

# NAME

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

Version 0.28

# SYNOPSIS

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

# Create:
tie my @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`.

If the access pattern is ascending or descending, then a window is sieved and results returned from the window as needed. If the access pattern is random, then `nth_prime` is used.

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```

If you prefer the iterator pattern, I would recommend using "prime_iterator" in Math::Prime::Util. It will be faster than using this tied array, but of course you don't get random access. If you find yourself using the `shift` operation, consider the iterator.

# 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.

There are some people that find the idea of shifting a prime array abhorrent, as after two shifts, "the second prime is 7?!". If this bothers you, do not use `shift` on the tied array.

# PERFORMANCE

```  MPU forprimes:  forprimes { \$sum += \$_ } nth_prime(100_000);
MPU iterator:   my \$it = prime_iterator; \$sum += \$it->() for 1..100000;
MPU array:      \$sum += \$_ for @{primes(nth_prime(100_000))};
MPUPA:          tie my @primes, ...; \$sum += \$primes[\$_] for 0..99999;
MNSP:           my \$seq = Math::NumSeq::Primes->new;
\$sum += (\$seq->next)[1] for 1..100000;
MPTA:           tie my @primes, ...; \$sum += \$primes[\$_] for 0..99999;```

Memory use is comparing the delta between just loading the module and running the test. Math::NumSeq v58, Math::Prime::TiedArray v0.04.

Summing the first 0.1M primes via walking the array:

```       9ms     52k    Math::Prime::Util      forprimes
150ms      0     Math::Prime::Util      prime_iterator
15ms   4400k    Math::Prime::Util      sum big array
220ms    840k    Math::Prime::Util::PrimeArray
130ms    280k    Math::NumSeq::Primes   sequence iterator
33000ms   65 MB    Math::Prime::TiedArray (extend 1k)```

Summing the first 1M primes via walking the array:

```      0.1s    300k    Math::Prime::Util      forprimes
1.9s      0     Math::Prime::Util      prime_iterator
0.2s   40 MB    Math::Prime::Util      sum big array
2.2s   1.1MB    Math::Prime::Util::PrimeArray
7.1s   1.2MB    Math::NumSeq::Primes   sequence iterator
122.1s  785 MB    Math::Prime::TiedArray (extend 1k)```

Summing the first 10M primes via walking the array:

```      0.8s   5.9MB    Math::Prime::Util      forprimes
23.1s      0     Math::Prime::Util      prime_iterator
1.6s  368 MB    Math::Prime::Util      sum big array
21.2s   1.2MB    Math::Prime::Util::PrimeArray
3680  s  11.1MB    Math::NumSeq::Primes   sequence iterator
>5000 MB    Math::Primes::TiedArray (extend 1k)```

Math::Prime::Util offers three obvious solutions: a big array, an iterator, and the `forprimes` construct. The big array is fast but uses a lot of memory, forcing the user to start programming segments. Using the iterator avoids all the memory use, but isn't as fast (this may improve in a later release, as this is a new feature). The `forprimes` construct is by far the fastest, but it isn't quite as flexible as the iterator (most notably there is no way to exit early, and it doesn't lend itself to wrapping inside a filter).

Math::NumSeq::Primes offers an iterator alternative, and works quite well for reasonably small numbers. It does not support random access. It is very fast for small values, but is very slow with large counts.

Math::Primes::TiedArray is remarkably impractical for anything other than very small numbers.

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>