This is an automated email from the git hooks/post-receive script.

ppm-guest pushed a commit to annotated tag v0.08
in repository libmath-prime-util-perl.

commit 1bcf403717edef5a1f904e293517d413384b49ac
Author: Dana Jacobsen <d...@acm.org>
Date:   Thu Jun 21 20:54:50 2012 -0600

    Add PrimeArray tied array
---
 Changes                           |   1 +
 MANIFEST                          |   3 +
 Makefile.PL                       |   6 +-
 TODO                              |   2 +-
 examples/sophie_germain.pl        |  18 +++
 examples/twin_primes.pl           |  21 ++++
 lib/Math/Prime/Util.pm            |   2 +
 lib/Math/Prime/Util/PrimeArray.pm | 240 ++++++++++++++++++++++++++++++++++++++
 8 files changed, 288 insertions(+), 5 deletions(-)

diff --git a/Changes b/Changes
index 5e4f3f4..0d48120 100644
--- a/Changes
+++ b/Changes
@@ -8,6 +8,7 @@ Revision history for Perl extension Math::Prime::Util.
     - Static presieve for 7, 11, and 13.  1k of ROM used for prefilling sieve
       memory, meaning we can skip the 7, 11, and 13 loops.  ~15% speedup.
     - Add all_factors function and added tests to t/50-factoring.t.
+    - Add tied array module Math::Prime::Util::PrimeArray.
 
 0.07  17 June 2012
     - Fixed a bug in next_prime found by Lou Godio (thank you VERY much!).
diff --git a/MANIFEST b/MANIFEST
index 89667bb..22f2963 100644
--- a/MANIFEST
+++ b/MANIFEST
@@ -1,5 +1,6 @@
 Changes
 lib/Math/Prime/Util.pm
+lib/Math/Prime/Util/PrimeArray.pm
 LICENSE
 Makefile.PL
 MANIFEST
@@ -32,6 +33,8 @@ examples/test-primes-yafu.pl
 examples/test-holf.pl
 examples/test-nthapprox.pl
 examples/test-pcapprox.pl
+examples/sophie_germain.pl
+examples/twin_primes.pl
 t/01-load.t
 t/02-can.t
 t/03-init.t
diff --git a/Makefile.PL b/Makefile.PL
index f3e2d28..f11bea2 100644
--- a/Makefile.PL
+++ b/Makefile.PL
@@ -7,9 +7,6 @@ WriteMakefile1(
     LICENSE      => 'perl',
     AUTHOR       => 'Dana A Jacobsen <d...@acm.org>',
 
-    LIBS         => [''],   # e.g., '-lm'
-    DEFINE       => '',     # e.g., '-DHAVE_SOMETHING'
-    INC          => '',     # e.g., '-I/usr/include/other'
     OBJECT       => 'cache.o ' .
                     'factor.o '  .
                     'sieve.o '  .
@@ -22,7 +19,8 @@ WriteMakefile1(
     PREREQ_PM    => {
                       'Exporter'         => '5.562',
                       'XSLoader'         => '0.01',
-                      'Carp'             => '0',
+                      'Carp'             => 0,
+                      'Tie::Array'       => 0,
                     },
 
     MIN_PERL_VERSION => 5.006002,
diff --git a/TODO b/TODO
index 8369292..683023d 100644
--- a/TODO
+++ b/TODO
@@ -25,4 +25,4 @@
 - Move .c / .h files into separate directory.
   version does it in a painful way.  Something simpler to be had?
 
-- Iterator or tie?
+- tests for tie
diff --git a/examples/sophie_germain.pl b/examples/sophie_germain.pl
new file mode 100755
index 0000000..ed7dde3
--- /dev/null
+++ b/examples/sophie_germain.pl
@@ -0,0 +1,18 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+
+use Math::Prime::Util qw/next_prime is_prime/;
+
+my $count = shift || 20;
+
+# Simple little loop looking for Sophie Germain primes (numbers where
+# p and 2p+1 are both prime).  Calculating the first 100k runs 17x faster than
+# Math::NumSeq::SophieGermainPrimes (about 3x faster if the latter's algorithm
+# is changed).
+my $prime = 2;
+for (1..$count) {
+  $prime = next_prime($prime) while (!is_prime(2*$prime+1));
+  print "$prime\n";
+  $prime = next_prime($prime);
+}
diff --git a/examples/twin_primes.pl b/examples/twin_primes.pl
new file mode 100755
index 0000000..2b3fbab
--- /dev/null
+++ b/examples/twin_primes.pl
@@ -0,0 +1,21 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+
+use Math::Prime::Util qw/next_prime is_prime/;
+
+my $count = shift || 20;
+
+# Simple little loop looking for twin primes (numbers where p and p+2 are
+# both prime).  Print them both.  About 3x faster than 
Math::NumSeq::TwinPrimes.
+my $prime = 2;
+my $next;
+for (1..$count) {
+  while (1) {
+    $next = next_prime($prime);
+    last if ($next-2) == $prime;
+    $prime = $next;
+  }
+  print $prime, ",", $prime+2, "\n";
+  $prime = $next;
+}
diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm
index dceb2ff..d3873f8 100644
--- a/lib/Math/Prime/Util.pm
+++ b/lib/Math/Prime/Util.pm
@@ -42,6 +42,8 @@ END {
 
 my $_maxparam  = (_maxbits == 32) ? 4294967295 : 18446744073709551615;
 my $_maxdigits = (_maxbits == 32) ? 10 : 20;
+my $_maxprime  = (_maxbits == 32) ? 4294967291 : 18446744073709551557;
+my $_maxprimeidx=(_maxbits == 32) ?  203280221 :   425656284035217743;
 
 sub primes {
   my $optref = {};  $optref = shift if ref $_[0] eq 'HASH';
diff --git a/lib/Math/Prime/Util/PrimeArray.pm 
b/lib/Math/Prime/Util/PrimeArray.pm
new file mode 100644
index 0000000..af57788
--- /dev/null
+++ b/lib/Math/Prime/Util/PrimeArray.pm
@@ -0,0 +1,240 @@
+package Math::Prime::Util::PrimeArray;
+use strict;
+use warnings;
+
+BEGIN {
+  $Math::Prime::Util::PrimeArray::AUTHORITY = 'cpan:DANAJ';
+  $Math::Prime::Util::PrimeArray::VERSION = '0.07';
+}
+
+# parent is cleaner, and in the Perl 5.10.1 / 5.12.0 core, but not earlier.
+# use parent qw( Exporter );
+use base qw( Exporter );
+our @EXPORT_OK = qw( );
+our %EXPORT_TAGS = (all => [ @EXPORT_OK ]);
+
+
+use Math::Prime::Util qw/nth_prime nth_prime_upper primes/;
+use Tie::Array;
+use Carp qw/carp croak confess/;
+
+sub TIEARRAY {
+  my $class = shift;
+  if (@_) {
+    croak "usage: tie ARRAY, '" . __PACKAGE__ . "";
+  }
+  return bless {
+    # used to keep track of shift
+    SHIFTINDEX => 0,
+    # Remove all extra prime memory when we go out of scope
+    MEMFREE    => Math::Prime::Util::MemFree->new,
+    # A chunk of primes
+    PRIMES     => [2, 3, 5, 7, 11, 13, 17],
+    # What's the index of the first one?
+    BEG_INDEX  => 0,
+    # What's the index of the last one?
+    END_INDEX  => 6,
+  }, $class;
+}
+sub STORE     { carp "You cannot write to the prime array"; }
+sub DELETE    { carp "You cannot write to the prime array"; }
+sub STORESIZE { carp "You cannot write to the prime array"; }
+sub EXISTS    { 1 }
+sub EXTEND    { 1 }
+sub FETCHSIZE { 0x7FFF_FFFF }   # Even on 64-bit
+# Simple FETCH:
+# sub FETCH { return nth_prime($_[1]+1); }
+sub FETCH {
+  my $self = shift;
+  my $index = shift;
+  # TODO: negative index?
+  $index += $self->{SHIFTINDEX};  # take into account any shifts
+  if ( ($index < $self->{BEG_INDEX}) || ($index > $self->{END_INDEX}) ) {
+    # We're going to get a chunk of primes starting 1000 before the one
+    # asked for, and extending at _least_ 1000 past it.  So given a number
+    # past index 1000, we would expect to have ~2000 primes with the one
+    # requested being about in the middle.  This should be reasonably fast
+    # for the siever and amortize the cost over a lot of calls if they're
+    # walking us.  Yes, we'll get well over 2000 primes as the numbers get
+    # very large, but that's ok (e.g. 80k primes at index 400M).  Calling
+    # nth_prime on indices that large is very time consuming.
+    my $start_idx = ($index < 1000) ? 0 : $index-1000;
+    my $start_prime = nth_prime($start_idx+1);       # This is exact
+    my $end_prime   = nth_prime_upper($index+5000);  # This is a bound
+    #print "calling primes from $start_idx/$start_prime to $end_prime\n";
+    $self->{PRIMES} = primes($start_prime, $end_prime);
+    $self->{BEG_INDEX} = $start_idx;
+    $self->{END_INDEX} = $start_idx + scalar @{$self->{PRIMES}} - 1;;
+  }
+  return $self->{PRIMES}->[ $index - $self->{BEG_INDEX} ];
+}
+
+# Fake out shift and unshift
+sub SHIFT {
+  my $self = shift;
+  my $head = $self->FETCH(0);
+  $self->{SHIFTINDEX}++;
+  $head;
+}
+sub UNSHIFT {
+  my $self = shift;
+  my $shiftamount = defined $_[0] ? shift : 1;
+  $self->{SHIFTINDEX} = ($shiftamount >= $self->{SHIFTINDEX})
+                        ? 0
+                        : $self->{SHIFTINDEX} - $shiftamount;
+  $self->FETCHSIZE;
+}
+# CLEAR this
+# PUSH this, LIST
+# POP this
+# SPLICE this, offset, len, LIST
+# DESTROY this
+# UNTIE this
+
+1;
+
+__END__
+
+
+# ABSTRACT: A tied array for primes
+
+=pod
+
+=head1 NAME
+
+Math::Prime::Util::PrimeArray - A tied array for primes
+
+
+=head1 VERSION
+
+Version 0.07
+
+
+=head1 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";
+  }
+
+
+=head1 DESCRIPTION
+
+An array that acts like the infinite set of primes.  This may be more
+convenient than using L<Math::Prime::Util> directly, and in some cases it can
+be faster than calling C<next_prime> and C<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 C<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, C<$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
+  
+
+=head1 LIMITATIONS
+
+The size of the array will always be shown as 2147483647 (IV32 max), even in
+a 64-bit environment where primes through C<2^64> are available.
+
+
+=head1 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
+           >2048 MB    Math::Primes::TiedArray (extend 1k)
+
+Using L<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 C<PrimeArray> tie is trying to do for you.
+
+L<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.
+
+L<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.
+
+
+=head1 SEE ALSO
+
+This module uses L<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 L<Math::NumSeq>
+and L<Math::Prime::TiedArray>.
+
+=head1 AUTHORS
+
+Dana Jacobsen E<lt>d...@acm.orge<gt>
+
+
+=head1 COPYRIGHT
+
+Copyright 2012 by Dana Jacobsen E<lt>d...@acm.orge<gt>
+
+This program is free software; you can redistribute it and/or modify it under 
the same terms as Perl itself.
+
+=cut

-- 
Alioth's /usr/local/bin/git-commit-notice on 
/srv/git.debian.org/git/pkg-perl/packages/libmath-prime-util-perl.git

_______________________________________________
Pkg-perl-cvs-commits mailing list
Pkg-perl-cvs-commits@lists.alioth.debian.org
http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-perl-cvs-commits

Reply via email to