This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.10 in repository libmath-prime-util-perl.
commit c05f032d97ee5866baa72f61d651d263b1b3ad9b Author: Dana Jacobsen <d...@acm.org> Date: Sun Jul 8 13:15:30 2012 -0600 Minor updates --- Changes | 2 +- lib/Math/Prime/Util.pm | 45 +++++++++------------------------------------ lib/Math/Prime/Util/PP.pm | 16 ++++++++++++---- 3 files changed, 22 insertions(+), 41 deletions(-) diff --git a/Changes b/Changes index fc27e1c..334e49c 100644 --- a/Changes +++ b/Changes @@ -29,7 +29,7 @@ Revision history for Perl extension Math::Prime::Util. Math::Prime::FastSieve Math::Prime::TiedArray (much faster) Math::Factor::XS (faster, missing multiplicity) - Math::Primality (more portable, fast for native, slow for bigint) + Math::Primality (more portable, fast for small, slow for big) Crypt::Primes (more portable, much slower, no fancy options) 0.09 25 June 2012 diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm index cccd6bb..df0010d 100644 --- a/lib/Math/Prime/Util.pm +++ b/lib/Math/Prime/Util.pm @@ -324,7 +324,10 @@ sub primes { $r; }; - # Returns a uniform number between [0,$range] inclusive. + # Returns a uniform number between [0,$range] inclusive. The straightforward + # method of getting a number of rand bits equal to the number of bits in the + # number, then repeatedly get a random number in the bit range until it + # falls within the desired range. my $get_rand_range = sub { my($range) = @_; my $rbits = 0; @@ -345,33 +348,6 @@ sub primes { return $U if $U <= $range; } }; - my $get_rand_range2 = sub { - my($range) = @_; - my $max = int($range) + 1; - my $offset = 0; - while ($max > 1) { - if ($max <= 31) { $offset += $irandf->($max); last; } - my $part = $max >> 1; - $part++ if ($max & 1) && $get_rand_bit->(); - $offset += $part if $get_rand_bit->(); - $max -= $part; - } - $offset; - }; - # The above routine isn't perfect, but it works pretty well. It's repeatedly - # partitioning the space into two pieces selected at random. For odd - # ranges the two edges are selected with slightly higher priority because - # we're approximating 1/r using powers of 2. The error rapidly reduces - # as r increases. By calling out to irandf when max is small enough we can - # mitigate it. - # - # The other implementation choice I can think of is to call irandf a bunch - # of times to get a random number R >= r. Let m = int(R/r). If R < m*r - # then return R % m. Repeat otherwise. This description isn't quite right - # in that we want to generate R with at least as many random bits as r, not - # necessarily greater, and m is related to the bits in each. - # - # Lastly I could do a recursive partition. # Sub to call with low and high already primes and verified range. @@ -559,7 +535,7 @@ sub primes { my $I = Math::BigInt->new(2)->bpow($k-1)->bdiv(2 * $q)->bfloor; #warn "I = $I\n"; - my @primes = @{primes(11,$B)}; + my @primes = @{primes(17,$B)}; while (1) { # R is a random number between $I+1 and 2*$I @@ -568,9 +544,7 @@ sub primes { # We constructed a promising looking $n. Now test it. # Trial divide up to $B - next if !($n % 3); - next if !($n % 5); - next if !($n % 7); + next if !($n % 3) || !($n % 5) || !($n % 7) || !($n % 11) || !($n % 13); my $looks_prime = 1; foreach my $p (@primes) { do { $looks_prime = 0; last; } if !($n % $p); @@ -1593,10 +1567,9 @@ in its current implementation when run on very large numbers of bits; (2) no external libraries are used for this module, while C::P uses L<Math::Pari>; (3) C::P uses a modified version of final acceptance criteria (C<q E<LT> n**(1/3)> without the rest of Lemma 2), while this module uses the -original set followed by a BPSW probable prime test to give some extra -assurance against code error; (4) C::P has some useful options for -cryptography, and (5) C::P is hardcoded to use Crypt::Random, while this -function will use whatever you set C<rand> to (this is both good and bad). +original set; (4) C::P has some useful options for cryptography, and (5) +C::P is hardcoded to use Crypt::Random, while this function will use whatever +you set C<rand> to (this is both good and bad). =head2 moebius diff --git a/lib/Math/Prime/Util/PP.pm b/lib/Math/Prime/Util/PP.pm index 72bb812..eaef23f 100644 --- a/lib/Math/Prime/Util/PP.pm +++ b/lib/Math/Prime/Util/PP.pm @@ -96,15 +96,23 @@ my @_prevwheel30 = (29,29,1,1,1,1,1,1,7,7,7,7,11,11,13,13,13,13,17,17,19,19,19,1 sub _is_prime7 { # n must not be divisible by 2, 3, or 5 my($n) = @_; - foreach my $i (qw/7 11 13 17 19 23 29/) { - return 2 if $i*$i > $n; - return 0 if !($n % $i); + if ($n < 61*61) { + foreach my $i (qw/7 11 13 17 19 23 29 31 37 41 43 47 53 59/) { + return 2 if $i*$i > $n; + return 0 if !($n % $i); + } + return 2; } + return 0 if !($n % 7) || !($n % 11) || !($n % 13) || !($n % 17) || + !($n % 19) || !($n % 23) || !($n % 29) || !($n % 31) || + !($n % 37) || !($n % 41) || !($n % 43) || !($n % 47) || + !($n % 53) || !($n % 59); + return Math::Prime::Util::is_prob_prime($n) if $n > 10_000_000; my $limit = int(sqrt($n)); - my $i = 31; + my $i = 61; while (($i+30) <= $limit) { return 0 if !($n % $i); $i += 6; return 0 if !($n % $i); $i += 4; -- 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