Provided by: libmath-prime-util-perl_0.73-2build2_amd64 bug

NAME

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

VERSION

       Version 0.73

SYNOPSIS

         # Use package and create a tied variable
         use Math::Prime::Util::PrimeArray;
         tie my @primes, 'Math::Prime::Util::PrimeArray';

         # or all in one (allowed: @primes, @prime, @pr, @p):
         use Math::Prime::Util::PrimeArray '@primes';

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

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

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

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

         # Use with shift:
         while ((my $p = shift @primes) < 1000) {
           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 will not shift past the beginning, so
       "unshift @primes, ~0" is a useful way to reset from any shifts.

       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 want sequential primes with low memory, I recommend using "forprimes" in
       Math::Prime::Util.  It is much faster, as the tied array functionality in Perl is not high
       performance.  It isn't as flexible as the prime array, but it is a very common pattern.

       If you prefer an iterator pattern, I would recommend using "prime_iterator" in
       Math::Prime::Util.  It will be a bit 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.

       Perl will mask all array arguments to 32-bit, making "2^32-1" the maximum prime through
       the standard array interface.  It will silently wrap after that.  The only way around this
       is using the object interface:

           use Math::Prime::Util::PrimeArray;
           my $o = tie my @primes, 'Math::Prime::Util::PrimeArray';
           say $o->FETCH(2**36);

       Here we store the object returned by tie, allowing us to call its FETCH method directly.
       This is actually faster than using the array.

       Some people 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

         sumprimes:      sum_primes(nth_prime(100_000))
         MPU forprimes:  forprimes { $sum += $_ } nth_prime(100_000);
         MPU iterator:   my $it = prime_iterator; $sum += $it->() for 1..100000;
         MPU array:      $sum = vecsum( @{primes(nth_prime(100_000))} );
         MPUPA:          tie my @prime, ...; $sum += $prime[$_] for 0..99999;
         MPUPA-FETCH:    my $o=tie my @pr, ...; $sum += $o->FETCH($_) for 0..99999;
         MNSP:           my $seq = Math::NumSeq::Primes->new;
                         $sum += ($seq->next)[1] for 1..100000;
         MPTA:           tie my @prime, ...; $sum += $prime[$_] for 0..99999;
         List::Gen       $sum = primes->take(100000)->sum

       Memory use is comparing the delta between just loading the module and running the test.
       Perl 5.20.0, Math::NumSeq v70, Math::Prime::TiedArray v0.04, List::Gen 0.974.

       Summing the first 0.1M primes via walking the array:

              .3ms    56k    Math::Prime::Util      sumprimes
              4ms     56k    Math::Prime::Util      forprimes
              4ms    4 MB    Math::Prime::Util      sum big array
             31ms      0     Math::Prime::Util      prime_iterator
             68ms    644k    MPU::PrimeArray        using FETCH
            101ms    644k    MPU::PrimeArray        array
             95ms   1476k    Math::NumSeq::Primes   sequence iterator
           4451ms   32 MB    List::Gen              sequence
           6954ms   61 MB    Math::Prime::TiedArray (extend 1k)

       Summing the first 1M primes via walking the array:

             0.005s  268k    Math::Prime::Util      sumprimes
             0.05s   268k    Math::Prime::Util      forprimes
             0.05s  41 MB    Math::Prime::Util      sum big array
             0.3s      0     Math::Prime::Util      prime_iterator
             0.7s    644k    MPU::PrimeArray        using FETCH
             1.0s    644k    MPU::PrimeArray        array
             6.1s   2428k    Math::NumSeq::Primes   sequence iterator
           106.0s   93 MB    List::Gen              sequence
            98.1s  760 MB    Math::Prime::TiedArray (extend 1k)

       Summing the first 10M primes via walking the array:

             0.07s   432k    Math::Prime::Util      sumprimes
             0.5s    432k    Math::Prime::Util      forprimes
             0.6s  394 MB    Math::Prime::Util      sum big array
             3.2s      0     Math::Prime::Util      prime_iterator
             6.8s    772k    MPU::PrimeArray        using FETCH
            10.2s    772k    MPU::PrimeArray        array
          1046  s  11.1MB    Math::NumSeq::Primes   sequence iterator
          6763  s  874 MB    List::Gen              sequence
                 >5000 MB    Math::Primes::TiedArray (extend 1k)

       Math::Prime::Util offers four obvious solutions: the "sum_primes" function, 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 both fast and low memory, but it isn't quite as
       flexible as the iterator (e.g. it doesn't lend itself to wrapping inside a filter).

       Math::NumSeq::Primes offers an iterator alternative, and works quite well as long as you
       don't need lots of primes.  It does not support random access.  It has reasonable
       performance for the first few hundred thousand, but each successive value takes much
       longer to generate, and once past 1 million it isn't very practical.  Internally it is
       sieving all primes up to "n" every time it makes a new segment which is why it slows down
       so much.

       List::Gen includes a built-in prime sequence.  It uses an inefficient Perl sieve for
       numbers below 10M, trial division past that.  It uses too much time and memory to be
       practical for anything but very small inputs.  It also gives incorrect results for large
       inputs (RT 105758).

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

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