This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.36 in repository libmath-prime-util-perl.
commit 94aeed29fa68ace4951c3a166cebb15c361387d0 Author: Dana Jacobsen <d...@acm.org> Date: Fri Jan 10 20:00:26 2014 -0800 Remove the old -nobigint flag. Better random ndigit for some old examples. --- examples/bench-factor.pl | 103 +++++++++++++---------------------------- examples/bench-miller-rabin.pl | 19 +++++--- examples/find_mr_bases.pl | 2 +- examples/sophie_germain.pl | 3 +- xt/pari-totient-moebius.pl | 2 +- xt/test-factor-mpxs.pl | 2 +- 6 files changed, 49 insertions(+), 82 deletions(-) diff --git a/examples/bench-factor.pl b/examples/bench-factor.pl index aa3a8d7..0a0f4c7 100755 --- a/examples/bench-factor.pl +++ b/examples/bench-factor.pl @@ -1,41 +1,18 @@ #!/usr/bin/env perl use strict; use warnings; - -# One of the things this test shows is the impact of the '-nobigint' option. -# "MPU" results are the timings without the '-nobigint' option -# "MPUxs" results are the timings _with_ the '-nobigint' option use Math::Prime::Util qw/factor/; - # Compare to Math::Factor::XS, which uses trial division. use Math::Factor::XS qw/prime_factors/; use Benchmark qw/:all/; use List::Util qw/min max reduce/; -use Config; my $count = shift || -2; my $is64bit = (~0 > 4294967295); my $maxdigits = ($is64bit) ? 20 : 10; # Noting the range is limited for max. my $semiprimes = 0; my $howmany = 1000; -my $rgen = sub { - my $range = shift; - return 0 if $range <= 0; - my $rbits = 0; { my $t = $range; while ($t) { $rbits++; $t >>= 1; } } - while (1) { - my $rbitsleft = $rbits; - my $U = 0; - while ($rbitsleft > 0) { - my $usebits = ($rbitsleft > $Config{randbits}) ? $Config{randbits} : $rbitsleft; - $U = ($U << $usebits) + int(rand(1 << $usebits)); - $rbitsleft -= $usebits; - } - return $U if $U <= $range; - } -}; -srand(29); - for my $d ( 3 .. $maxdigits ) { print "Factor $howmany $d-digit numbers\n"; test_at_digits($d, $howmany); @@ -47,17 +24,15 @@ sub test_at_digits { die "Digits has to be <= $maxdigits" if $digits > $maxdigits; my $quantity = shift; - my @rnd = genrand($digits, $quantity); - my @smp = gensemi($digits, $quantity); + my @rnd = ndigit_rand($digits, $quantity); + my @smp = genrough($digits, $quantity); # verify (can be _really_ slow for 18+ digits) foreach my $p (@rnd, @smp) { - my @mpxs = prime_factors($p); push @mpxs, $p if $p < 2; - - verify_factor($p, \@mpxs, [factor($p)], "Math::Prime::Util $Math::Prime::Util::VERSION"); + next if $p < 2; + verify_factor($p, [prime_factors($p)], [factor($p)], "Math::Prime::Util $Math::Prime::Util::VERSION"); } - #my $min_num = min @nums; #my $max_num = max @nums; #my $whatstr = "$digits-digit ", $semiprimes ? "semiprime" : "random"; @@ -66,24 +41,21 @@ sub test_at_digits { # " ($min_num - $max_num)\n"; my $lref = { - "MPUxs rand" => sub { Math::Prime::Util::_XS_factor($_) for @rnd }, - "MPUxs semi" => sub { Math::Prime::Util::_XS_factor($_) for @smp }, - "MPU rand" => sub { factor($_) for @rnd }, - "MPU semi" => sub { factor($_) for @smp }, - "MFXS rand" => sub { prime_factors($_) for @rnd }, - "MFXS semi" => sub { prime_factors($_) for @smp }, + "MPU random" => sub { my@a=factor($_) for @rnd }, + "MPU nonsmooth" => sub { my@a=factor($_) for @smp }, + "MFXS random" => sub { my@a=prime_factors($_) for @rnd }, + "MFXS nonsmooth" => sub { my@a=prime_factors($_) for @smp }, }; cmpthese($count, $lref); } sub verify_factor { - my $n = shift; - my $aref_master = shift; - my $aref_check = shift; - my $name = shift; + my ($n, $aref1, $aref2, $name) = @_; - my @master = sort {$a<=>$b} @{$aref_master}; - my @check = sort {$a<=>$b} @{$aref_check}; + return 1 if "@$aref1" eq "@$aref2"; + + my @master = @$aref1; + my @check = @$aref2; die "Factor $n master fail!" unless $n == reduce { $a * $b } @master; die "Factor $n fail: $name" unless $#check == $#master; die "Factor $n fail: $name" unless $n == reduce { $a * $b } @check; @@ -93,45 +65,34 @@ sub verify_factor { 1; } -sub genrand { - my $digits = shift; - my $num = shift; - - my $base = ($digits == 1) ? 0 : int(10 ** ($digits-1)); - my $max = int(10 ** $digits); - $max = ~0 if $max > ~0; - my @nums = map { $base + $rgen->($max-$base) } (1 .. $num); - return @nums; -} - -sub gensemi { - my $digits = shift; - my $num = shift; +sub genrough { + my ($digits, $num) = @_; my @min_factors_by_digit = (2,2,3,5,7,13,23,47,97); my $smallest_factor = $min_factors_by_digit[$digits]; $smallest_factor = $min_factors_by_digit[-1] unless defined $smallest_factor; - my $base = ($digits == 1) ? 0 : int(10 ** ($digits-1)); - my $max = int(10 ** $digits); - $max = (~0-4) if $max > (~0-4); my @semiprimes; - foreach my $i (1 .. $num) { - my @factors; my $n; - while (1) { - $n = $base + $rgen->($max-$base); - # Skip past all multiples of 2, 3, and 5. - $n += (1,0,5,4,3,2,1,0,3,2,1,0,1,0,3,2,1,0,1,0,3,2,1,0,5,4,3,2,1,0)[$n%30]; - @factors = Math::Prime::Util::factor($n); - next if scalar @factors != 2; - next if $factors[0] < $smallest_factor; - next if $factors[1] < $smallest_factor; - last if scalar @factors == 2; - } - die "ummm... $n != $factors[0] * $factors[1]\n" unless $n == $factors[0] * $factors[1]; + my @facn; + do { + $n = ndigit_rand($digits, 1); + @facn = Math::Prime::Util::trial_factor($n,$smallest_factor); + } while scalar(@facn) > 1; push @semiprimes, $n; } return @semiprimes; } + +use Bytes::Random::Secure qw/random_string_from/; +sub ndigit_rand { + my($digits, $howmany) = @_; + die "digits must be > 0" if $digits < 1; + $howmany = 1 unless defined $howmany; + # TODO: need to skip things larger than ~0 for this module + my @nums = map { random_string_from("123456789",1) . random_string_from("0123456789",$digits-1) } 1 .. $howmany; + if (10**$digits > ~0) { @nums = map { Math::BigInt->new($_) } @nums; } + else { @nums = map { int($_) } @nums; } + return wantarray ? @nums : $nums[0]; +} diff --git a/examples/bench-miller-rabin.pl b/examples/bench-miller-rabin.pl index ec11aab..3db5731 100755 --- a/examples/bench-miller-rabin.pl +++ b/examples/bench-miller-rabin.pl @@ -3,7 +3,7 @@ use strict; use warnings; use Math::Primality; use Math::Prime::XS; -use Math::Prime::Util '-nobigint'; +use Math::Prime::Util; use Math::Prime::Util::GMP; #use Math::Prime::FastSieve; use Benchmark qw/:all/; @@ -11,17 +11,14 @@ use List::Util qw/min max/; my $count = shift || -5; srand(29); -test_at_digits($_) for (5..10); +test_at_digits($_) for (5..18); sub test_at_digits { my $digits = shift; die "Digits must be > 0" unless $digits > 0; - my $base = ($digits == 1) ? 0 : int(10 ** ($digits-1)); - my $max = int(10 ** $digits); - $max = ~0 if $max > ~0; - my @nums = map { $base+int(rand($max-$base)) } (1 .. 1000); + my @nums = ndigit_rand($digits, 1000); my $min_num = min @nums; my $max_num = max @nums; @@ -44,3 +41,13 @@ sub test_at_digits { }); print "\n"; } + +use Bytes::Random::Secure qw/random_string_from/; +sub ndigit_rand { + my($digits, $howmany) = @_; + die "digits must be > 0" if $digits < 1; + $howmany = 1 unless defined $howmany; + my @nums = map { random_string_from("123456789",1) . random_string_from("0123456789",$digits-1) } 1 .. $howmany; + @nums = map { Math::BigInt->new($_) } @nums if 10**$digits > ~0; + return @nums; +} diff --git a/examples/find_mr_bases.pl b/examples/find_mr_bases.pl index 2d1e078..8f78173 100755 --- a/examples/find_mr_bases.pl +++ b/examples/find_mr_bases.pl @@ -3,7 +3,7 @@ use warnings; use strict; use threads; use threads::shared; -use Math::Prime::Util qw/-nobigint is_prime is_strong_pseudoprime/; +use Math::Prime::Util qw/is_prime is_strong_pseudoprime/; my $nthreads = 12; # Single base. diff --git a/examples/sophie_germain.pl b/examples/sophie_germain.pl index 84b04cc..0fec4b1 100755 --- a/examples/sophie_germain.pl +++ b/examples/sophie_germain.pl @@ -2,8 +2,7 @@ use strict; use warnings; -use Math::Prime::Util qw/-nobigint - prime_iterator is_prime +use Math::Prime::Util qw/prime_iterator is_prime next_prime nth_prime_upper prime_precalc forprimes/; my $count = shift || 20; diff --git a/xt/pari-totient-moebius.pl b/xt/pari-totient-moebius.pl index 2c073af..a737754 100755 --- a/xt/pari-totient-moebius.pl +++ b/xt/pari-totient-moebius.pl @@ -3,7 +3,7 @@ use strict; use warnings; $| = 1; # fast pipes -use Math::Prime::Util qw/-nobigint/; +use Math::Prime::Util; use Math::Pari; my $nlinear = 100000; diff --git a/xt/test-factor-mpxs.pl b/xt/test-factor-mpxs.pl index 331d9ea..b418288 100755 --- a/xt/test-factor-mpxs.pl +++ b/xt/test-factor-mpxs.pl @@ -3,7 +3,7 @@ use strict; use warnings; $| = 1; # fast pipes -use Math::Prime::Util qw/factor -nobigint/; +use Math::Prime::Util qw/factor/; use Math::Factor::XS qw/prime_factors/; use Config; -- 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