Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help
Math::Prime::Util::PriUserrContributed Perl DoMath::Prime::Util::PrimeArray(3)

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.

perl v5.32.1			  2018-11-15  Math::Prime::Util::PrimeArray(3)

NAME | VERSION | SYNOPSIS | DESCRIPTION | LIMITATIONS | PERFORMANCE | SEE ALSO | AUTHORS | COPYRIGHT

Want to link to this manual page? Use this URL:
<https://www.freebsd.org/cgi/man.cgi?query=Math::Prime::Util::PrimeArray&sektion=3&manpath=FreeBSD+13.0-RELEASE+and+Ports>

home | help