.\" Automatically generated by Pod::Man 2.28 (Pod::Simple 3.28) .\" .\" Standard preamble: .\" ======================================================================== .de Sp \" Vertical space (when we can't use .PP) .if t .sp .5v .if n .sp .. .de Vb \" Begin verbatim text .ft CW .nf .ne \\$1 .. .de Ve \" End verbatim text .ft R .fi .. .\" Set up some character translations and predefined strings. \*(-- will .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left .\" double quote, and \*(R" will give a right double quote. \*(C+ will .\" give a nicer C++. Capital omega is used to do unbreakable dashes and .\" therefore won't be available. \*(C` and \*(C' expand to `' in nroff, .\" nothing in troff, for use with C<>. .tr \(*W- .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p' .ie n \{\ . ds -- \(*W- . ds PI pi . if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch . if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch . ds L" "" . ds R" "" . ds C` "" . ds C' "" 'br\} .el\{\ . ds -- \|\(em\| . ds PI \(*p . ds L" `` . ds R" '' . ds C` . ds C' 'br\} .\" .\" Escape single quotes in literal strings from groff's Unicode transform. .ie \n(.g .ds Aq \(aq .el .ds Aq ' .\" .\" If the F register is turned on, we'll generate index entries on stderr for .\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index .\" entries marked with X<> in POD. Of course, you'll have to process the .\" output yourself in some meaningful fashion. .\" .\" Avoid warning from groff about undefined register 'F'. .de IX .. .nr rF 0 .if \n(.g .if rF .nr rF 1 .if (\n(rF:(\n(.g==0)) \{ . if \nF \{ . de IX . tm Index:\\$1\t\\n%\t"\\$2" .. . if !\nF==2 \{ . nr % 0 . nr F 2 . \} . \} .\} .rr rF .\" .\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2). .\" Fear. Run. Save yourself. No user-serviceable parts. . \" fudge factors for nroff and troff .if n \{\ . ds #H 0 . ds #V .8m . ds #F .3m . ds #[ \f1 . ds #] \fP .\} .if t \{\ . ds #H ((1u-(\\\\n(.fu%2u))*.13m) . ds #V .6m . ds #F 0 . ds #[ \& . ds #] \& .\} . \" simple accents for nroff and troff .if n \{\ . ds ' \& . ds ` \& . ds ^ \& . ds , \& . ds ~ ~ . ds / .\} .if t \{\ . ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u" . ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u' . ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u' . ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u' . ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u' . ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u' .\} . \" troff and (daisy-wheel) nroff accents .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V' .ds 8 \h'\*(#H'\(*b\h'-\*(#H' .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#] .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H' .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u' .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#] .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#] .ds ae a\h'-(\w'a'u*4/10)'e .ds Ae A\h'-(\w'A'u*4/10)'E . \" corrections for vroff .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u' .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u' . \" for low resolution devices (crt and lpr) .if \n(.H>23 .if \n(.V>19 \ \{\ . ds : e . ds 8 ss . ds o a . ds d- d\h'-1'\(ga . ds D- D\h'-1'\(hy . ds th \o'bp' . ds Th \o'LP' . ds ae ae . ds Ae AE .\} .rm #[ #] #H #V #F C .\" ======================================================================== .\" .IX Title "Math::Prime::Util::PrimeArray 3pm" .TH Math::Prime::Util::PrimeArray 3pm "2014-10-17" "perl v5.20.1" "User Contributed Perl Documentation" .\" For nroff, turn off justification. Always turn off hyphenation; it makes .\" way too many mistakes in technical documents. .if n .ad l .nh .SH "NAME" Math::Prime::Util::PrimeArray \- A tied array for primes .SH "VERSION" .IX Header "VERSION" Version 0.46 .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 1 \& use Math::Prime::Util::PrimeArray; \& \& # Create: \& tie my @primes, \*(AqMath::Prime::Util::PrimeArray\*(Aq; \& \& # Use in a loop by index: \& for my $n (0..9) { \& print "prime $n = $primes[$n]\en"; \& } \& \& # Use in a loop over array: \& for my $p (@primes) { \& last if $p > 1000; # stop sometime \& print "$p\en"; \& } \& \& # Use via array slice: \& print join(",", @primes[0..49]), "\en"; \& \& # 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\en"; \& } \& \& # Use with shift: \& while ((my $p = shift @primes) < 1000) { \& print "$p\en"; \& } .Ve .SH "DESCRIPTION" .IX Header "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 \f(CW\*(C`next_prime\*(C'\fR and \f(CW\*(C`prev_prime\*(C'\fR. .PP 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 \f(CW\*(C`nth_prime\*(C'\fR is used. .PP Shifting acts like the array is losing elements at the front, so after two shifts, \f(CW\*(C`$primes[0] == 5\*(C'\fR. 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 \f(CW\*(C`unshift @primes, ~0\*(C'\fR is a useful way to reset from any shifts. .PP Example: .PP .Vb 8 \& 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 .Ve .PP If you want sequential primes with low memory, I recommend using \&\*(L"forprimes\*(R" 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. .PP If you prefer an iterator pattern, I would recommend using \&\*(L"prime_iterator\*(R" 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 \f(CW\*(C`shift\*(C'\fR operation, consider the iterator. .SH "LIMITATIONS" .IX Header "LIMITATIONS" The size of the array will always be shown as 2147483647 (\s-1IV32\s0 max), even in a 64\-bit environment where primes through \f(CW\*(C`2^64\*(C'\fR are available. .PP Some people find the idea of shifting a prime array abhorrent, as after two shifts, \*(L"the second prime is 7?!\*(R". If this bothers you, do not use \&\f(CW\*(C`shift\*(C'\fR on the tied array. .SH "PERFORMANCE" .IX Header "PERFORMANCE" .Vb 8 \& 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 @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; \& List::Gen $sum = primes\->take(100000)\->sum .Ve .PP 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. .PP Summing the first 0.1M primes via walking the array: .PP .Vb 7 \& 6ms 56k Math::Prime::Util forprimes \& 7ms 4 MB Math::Prime::Util sum big array \& 110ms 0 Math::Prime::Util prime_iterator \& 155ms 644k Math::Prime::Util::PrimeArray \& 120ms 1476k Math::NumSeq::Primes sequence iterator \& 4656ms 32 MB List::Gen sequence \& 7540ms 61 MB Math::Prime::TiedArray (extend 1k) .Ve .PP Summing the first 1M primes via walking the array: .PP .Vb 7 \& 0.07s 268k Math::Prime::Util forprimes \& 0.09s 41 MB Math::Prime::Util sum big array \& 1.4s 0 Math::Prime::Util prime_iterator \& 1.6s 644k Math::Prime::Util::PrimeArray \& 7.1s 2428k Math::NumSeq::Primes sequence iterator \& 91.3s 93 MB List::Gen sequence \& 108.4s 760 MB Math::Prime::TiedArray (extend 1k) .Ve .PP Summing the first 10M primes via walking the array: .PP .Vb 7 \& 0.7s 432k Math::Prime::Util forprimes \& 0.9s 394 MB Math::Prime::Util sum big array \& 16.9s 0 Math::Prime::Util prime_iterator \& 15.4s 772k Math::Prime::Util::PrimeArray \& 3680 s 11.1MB Math::NumSeq::Primes sequence iterator \& 5555 s 874 MB List::Gen sequence \& >5000 MB Math::Primes::TiedArray (extend 1k) .Ve .PP Math::Prime::Util offers three obvious solutions: a big array, an iterator, and the \f(CW\*(C`forprimes\*(C'\fR construct. The big array is fast but uses a \fBlot\fR 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 \f(CW\*(C`forprimes\*(C'\fR construct is both fast and low memory, 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). .PP 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. .PP Math::Primes::TiedArray is remarkably impractical for anything other than tiny numbers. .PP List::Gen includes a built-in prime sequence. It uses an inefficient Perl sieve for numbers below 10M and has some performance defects when getting large numbers of primes. .SH "SEE ALSO" .IX Header "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. .PP Similar functionality can be had from Math::NumSeq and Math::Prime::TiedArray. .SH "AUTHORS" .IX Header "AUTHORS" Dana Jacobsen .SH "COPYRIGHT" .IX Header "COPYRIGHT" Copyright 2012\-2013 by Dana Jacobsen .PP This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.