NAME

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

VERSION

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.

SEE ALSO

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>

COPYRIGHT

Copyright 2012 by Dana Jacobsen <dana@acm.org>

This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

cpanm Math::Prime::Util

perl -MCPAN -e shell
install Math::Prime::Util