Skip Menu |
 

This queue is for tickets about the Math-Big CPAN distribution.

Report information
The Basics
Id: 81986
Status: open
Priority: 0/
Queue: Math-Big

People
Owner: Nobody in particular
Requestors: DANAJ [...] cpan.org
Cc:
AdminCc:

Bug Information
Severity: Normal
Broken in: 1.12
Fixed in: (no value)



Subject: The primes function is *very* slow and uses too much memory (patch included)
Download (untitled) / with headers
text/plain 2.6k
The primes function is far slower than it should be. The attached patch makes it run much faster and use much less memory, while also fixing incorrect prime count returns for N <= 2, and primes for N <= 1. I realize that this no longer really tests the functionality of Math::BigInt, and hence may not be acceptable as submitted. I have it returning all results as BigInts at the end, so the result is the same as it was before, even though there is really no reason for them to be BigInts (and the conversion takes more time than the sieving for most inputs). But for almost all cases, this is really not necessary. The case I can think of would be for a 32-bit machine with an argument larger than 2**32. The old code used more than 26GB of RAM getting to 800M, so I don't think anyone ever hit that limit. The new code would be able to get there, so maybe it deserves more thought. For BigInts, a segmented sieve might also be worthwhile, though the current interface (a single integer with an implied lower limit of 2) doesn't really make it useful. The patch uses a string sieve which is faster than array versions. It would be an easy change to instead use a more conventional vec() version that runs 2-4x slower than this patch but uses 1/8th the sieve memory. The memory savings when run in array context is dwarfed by the BigInt return values, so not really a factor there. Either one would run quite a bit faster than the existing code. time perl -MMath::Big=primes -E 'say scalar primes(10_000_000);' 664579 377.58s 1,510,336k used time perl -Iblib/lib -Iblib/arch -MMath::Big=primes -E 'say scalar primes(10_000_000);' 664579 0.81s 98,176k used time perl -MMath::Big=primes -E 'my @p = primes(700000); say $p[50000];' 611957 26.21s 244,528k used time perl -Iblib/lib -Iblib/arch -MMath::Big=primes -E 'my @p = primes(700000); say $p[50000];' 0.58s 150,096k used Memory use is from /usr/bin/time, so includes everything. I verified the prime count for small values using: perl -Iblib/lib -Iblib/arch -MMath::Big=primes -MMath::Prime::FastSieve -E 'my $sieve = Math::Prime::FastSieve::Sieve->new( 1_000_000 ); foreach my $n (1..100000) { die "$n" unless $sieve->count_le($n) == scalar primes($n); say "good through $n" if $n % 5000 == 0; }' and the primes array using: perl -Iblib/lib -Iblib/arch -MMath::Big=primes -MMath::Prime::FastSieve -E 'my $sieve = Math::Prime::FastSieve::Sieve->new( 1_000_000 ); foreach my $n (1..10000) { my @p1 = @{$sieve->primes($n)}; my @p2 = primes($n); die "$n" unless scalar @p1 == scalar @p2; foreach my $i (0..$#p1) { die "$n" unless $p1[$i] == $p2[$i]; } say "good through $n" if $n % 500 == 0; }'
Subject: Math-Big.patch
Download Math-Big.patch
text/x-diff 3.7k
--- lib/site_perl/5.17.6/Math/Big.pm 2007-04-16 08:27:54.000000000 -0700 +++ lib/Math/Big.pm 2012-12-14 13:34:05.429974839 -0800 @@ -29,64 +29,41 @@ my $five = Math::BigFloat->new(5); # for pi my $twothreenine = Math::BigFloat->new(239); # for pi -sub primes - { - my $amount = shift; $amount = 1000 if !defined $amount; - $amount = Math::BigInt->new($amount) unless ref $amount; - - return (Math::BigInt->new(2)) if $amount < $three; - - $amount++; - - # any not defined number is prime, 0,1 are not, but 2 is - my @primes = (1,1,0); - my $prime = $three->copy(); # start - my $r = 0; my $a = $amount->numify(); - for (my $i = 3; $i < $a; $i++) # int version - { - $primes[$i] = $r; $r = 1-$r; - } - my ($cur,$add); - # find primes - OUTER: - while ($prime <= $amount) - { - # find first unmarked, it is the next prime - $cur = $prime; - while ($primes[$cur]) - { - $cur += $two; last OUTER if $cur >= $amount; # no more to do - } - # $cur is now new prime - # now strike out all multiples of $cur - $add = $cur * $two; - $prime = $cur + $two; # next round start two higher - $cur += $add; - while ($cur <= $amount) - { - $primes[$cur] = 1; $cur += $add; - } - } - - if (!wantarray) - { - my $n = 0; - for my $p (@primes) - { - $n++ if $p == 0; - } - return Math::BigInt->new($n); - } - - my @real_primes; my $i = 0; - while ($i < scalar @primes) - { - push @real_primes, Math::BigInt->new($i) if $primes[$i] == 0; - $i ++; - } - - @real_primes; +# In scalar context this returns the prime count (# of primes <= N). +# In array context it returns a list of primes from 2 to N. +sub primes { + my $end = shift; + return unless defined $end; + $end = $end->numify() if ref($end) =~ /^Math::Big/; + if ($end < 2) { return !wantarray ? Math::BigInt->bzero() : (); } + if ($end < 3) { return !wantarray ? $one->copy : ($two->copy); } + if ($end < 5) { return !wantarray ? $two->copy : ($two->copy, $three->copy); } + + $end-- unless ($end & 1); + my $s_end = $end >> 1; + my $whole = int( ($end>>1) / 15); + # Be conservative. This would result in terabytes of array output. + die "Cannot return $end primes!" if $whole > 1_145_324_612; # ~32 GB string + my $sieve = "100010010010110" . "011010010010110" x $whole; + substr($sieve, $s_end+1) = ''; # Clip to the right number of entries + my ($n, $limit) = ( 7, int(sqrt($end)) ); + while ( $n <= $limit ) { + for (my $s = ($n*$n) >> 1; $s <= $s_end; $s += $n) { + substr($sieve, $s, 1) = '1'; + } + do { $n += 2 } while substr($sieve, $n>>1, 1); + } + + return Math::BigInt->new(1 + $sieve =~ tr/0//) if !wantarray; + + my @primes = (2, 3, 5); + $n = 7-2; + foreach my $s (split("0", substr($sieve, 3), -1)) { + $n += 2 + 2 * length($s); + push @primes, $n if $n <= $end; } + return map { Math::BigInt->new($_) } @primes; +} sub fibonacci { @@ -880,7 +857,7 @@ cos sin tan euler bernoulli arctan arcsin pi/; @primes = primes(100); # first 100 primes - $prime = primes(100); # 100th prime + $count = primes(100); # number of primes <= 100 @fib = fibonacci (100); # first 100 fibonacci numbers $fib_1000 = fibonacci (1000); # 1000th fibonacci number $hailstone = hailstone (1000); # length of sequence @@ -930,11 +907,10 @@ $primes = primes($n); Calculates all the primes below N and returns them as array. In scalar context -returns the number of primes below N. +returns the prime count of N (the number of primes less than or equal to N). This uses an optimized version of the B<Sieve of Eratosthenes>, which takes -half of the time and half of the space, but is still O(N). Or in other words, -quite slow. +half of the time and half of the space, but is still O(N). =head2 B<fibonacci()>
Download (untitled) / with headers
text/plain 471b
This also seems to fix floating point inputs: perl -MMath::Big=primes -E 'say scalar primes(14.99);' 1 perl -Iblib/lib -Iblib/arch -MMath::Big=primes -E 'say scalar primes(14.99);' 6 perl -MMath::Big=primes -E 'say join ",", primes(14.99);' 2 perl -Iblib/lib -Iblib/arch -MMath::Big=primes -E 'say join ",", primes(14.99);' 2,3,5,7,11,13 Arguably, new test cases for N = 0,1,2 in scalar and array context, with no input, and a floating point input should be added.
Subject: Re: [rt.cpan.org #81986] The primes function is *very* slow and uses too much memory (patch included)
Date: Sat, 15 Dec 2012 06:53:52 -0500
To: bug-Math-Big [...] rt.cpan.org
From: "Tels" <nospam-abuse [...] bloodgate.com>
Download (untitled) / with headers
text/plain 2.3k
Hi Dana, On Fri, December 14, 2012 4:41 pm, Dana Jacobsen via RT wrote: Show quoted text
> Fri Dec 14 16:40:59 2012: Request 81986 was acted upon. > Transaction: Ticket created by DANAJ > Queue: Math-Big > Subject: The primes function is *very* slow and uses too much memory > (patch included) > Broken in: 1.12 > Severity: Normal > Owner: Nobody > Requestors: DANAJ@cpan.org > Status: new > Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=81986 > > > > The primes function is far slower than it should be. The attached patch > makes it run much faster and use much less memory, while also fixing > incorrect prime count returns for N <= 2, and primes for N <= 1. > > I realize that this no longer really tests the functionality of > Math::BigInt, and hence may not be acceptable as submitted. I have it > returning all results as BigInts at the end, so the result is the same > as it was before, even though there is really no reason for them to be > BigInts (and the conversion takes more time than the sieving for most > inputs). But for almost all cases, this is really not necessary. The > case I can think of would be for a 32-bit machine with an argument > larger than 2**32. The old code used more than 26GB of RAM getting to > 800M, so I don't think anyone ever hit that limit. The new code would > be able to get there, so maybe it deserves more thought. > > For BigInts, a segmented sieve might also be worthwhile, though the > current interface (a single integer with an implied lower limit of 2) > doesn't really make it useful. > > The patch uses a string sieve which is faster than array versions. It > would be an easy change to instead use a more conventional vec() version > that runs 2-4x slower than this patch but uses 1/8th the sieve memory. > The memory savings when run in array context is dwarfed by the BigInt > return values, so not really a factor there. Either one would run quite > a bit faster than the existing code.
The results look fine to me, and I'd not object to replacing my code. The original code was more a proof-of-concept and not really something usable for large values - there exist much faster/better alternatives for it. But it's something for "Need it quickly and now and w/ lots of fuss like installing modules." all the best, tels -- http://bloodgate.com/galleries/
Download (untitled) / with headers
text/plain 2.9k
On Sat Dec 15 06:54:02 2012, nospam-abuse@bloodgate.com wrote: Show quoted text
> The results look fine to me, and I'd not object to replacing my code. The > original code was more a proof-of-concept and not really something usable > for large values - there exist much faster/better alternatives for it. But > it's something for "Need it quickly and now and w/ lots of fuss like > installing modules."
Tels, thanks for the reply. As part of developing Math::Prime::Util, one of the things I've been doing is comparing it to other solutions, both to verify my correctness and also performance. I was sadly lax in reporting issues I found until recently. Math::Big was quite an outlier in both time and space, with a slope that didn't resemble any of the other sieving methods I used. There are faster alternatives, and ones with many more features, but after this change, I think it runs at a reasonable speed. Some timings using Perl 5.17.6 on a pretty fast computer, prime count to 800M: 0.025s Math::Prime::Util 0.12 XS, Lehmer's method 0.36s Math::Prime::Util 0.09 XS, segmented mod-30 sieve 0.52s Math::Prime::Util:PP 0.14 Perl, Lehmer's method 2.90s Math::Prime::FastSieve 0.18 XS, good SoE 11.7s Math::Prime::XS 0.29 XS 15.0s Bit::Vector 7.2 XS 57.3s Math::Prime::Util::PP 0.14 Perl, string sieve "" Math::Big patched "" 169.5s Python mpmath primepi 0.17 Python, 25 GB RAM. 292.2s Python sympy primepi 0.7.1 Python 20000+ Math::Big 1.12 Perl, > 26GB RAM This is probably the best case for this Perl code: doing a count using Perl 5.16.0+. But importantly we've changed from being really slow with too much memory, to now being quite fast -- only 4x slower than one of the XS solutions. [Aside to be fair: there are much faster solutions in Python than the ones used in the standard modules -- RHW on StackOverflow provided some fast sieves, and modifying those to do prime counts yields a pure Python implementation that runs about 2x faster than this pure Perl code, albeit with 2x the memory. The version using numpy runs not much slower than Math::Prime::FastSieve -- in other words, pretty darn fast.] The Lehmer count method is ~100 lines of Perl including comments. Probably something better left for a module, though it's fine with me if someone wants to include it. Summing the first 1M primes "$sum += $_ for primes(1000000)" on a slightly slower machine: 38.1s old Math::Big 1.7s new Math::Big 0.2s new Math::Big returning @primes instead of mapping to BigInts ~0.02s the various XS modules Looks much more reasonable. A lot of the time difference between the non-BigInt and BigInt versions is the summation, which gets done as a BigInt calculation. At 10M, I get 402s for old Math::Big, 14s for new Math::Big, 1.2s for new Math::Big returning non-BigInts, and 0.13-0.18s for XS modules (which all return non-BigInts for this range).
Subject: Re: [rt.cpan.org #81986] The primes function is *very* slow and uses too much memory (patch included)
Date: Tue, 25 Dec 2012 11:56:34 -0500
To: bug-Math-Big [...] rt.cpan.org
From: "Tels" <nospam-abuse [...] bloodgate.com>
Download (untitled) / with headers
text/plain 3.7k
On Sat, December 15, 2012 6:50 pm, Dana Jacobsen via RT wrote: Show quoted text
> Queue: Math-Big > Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=81986 > > > On Sat Dec 15 06:54:02 2012, nospam-abuse@bloodgate.com wrote:
>> The results look fine to me, and I'd not object to replacing my code. >> The >> original code was more a proof-of-concept and not really something >> usable >> for large values - there exist much faster/better alternatives for it. >> But >> it's something for "Need it quickly and now and w/ lots of fuss like >> installing modules."
> > Tels, thanks for the reply. > > As part of developing Math::Prime::Util, one of the things I've been > doing is comparing it to other solutions, both to verify my correctness > and also performance. I was sadly lax in reporting issues I found until > recently. Math::Big was quite an outlier in both time and space, with a > slope that didn't resemble any of the other sieving methods I used. > > There are faster alternatives, and ones with many more features, but > after this change, I think it runs at a reasonable speed. Some timings > using Perl 5.17.6 on a pretty fast computer, prime count to 800M: > > 0.025s Math::Prime::Util 0.12 XS, Lehmer's method > 0.36s Math::Prime::Util 0.09 XS, segmented mod-30 sieve > 0.52s Math::Prime::Util:PP 0.14 Perl, Lehmer's method > 2.90s Math::Prime::FastSieve 0.18 XS, good SoE > 11.7s Math::Prime::XS 0.29 XS > 15.0s Bit::Vector 7.2 XS > 57.3s Math::Prime::Util::PP 0.14 Perl, string sieve > "" Math::Big patched "" > 169.5s Python mpmath primepi 0.17 Python, 25 GB RAM. > 292.2s Python sympy primepi 0.7.1 Python > 20000+ Math::Big 1.12 Perl, > 26GB RAM > > This is probably the best case for this Perl code: doing a count using > Perl 5.16.0+. But importantly we've changed from being really slow with > too much memory, to now being quite fast -- only 4x slower than one of > the XS solutions.
Hm, I think the actual times are missing? Show quoted text
> [Aside to be fair: there are much faster solutions in Python than the > ones used in the standard modules -- RHW on StackOverflow provided some > fast sieves, and modifying those to do prime counts yields a pure Python > implementation that runs about 2x faster than this pure Perl code, > albeit with 2x the memory. The version using numpy runs not much slower > than Math::Prime::FastSieve -- in other words, pretty darn fast.] > > The Lehmer count method is ~100 lines of Perl including comments. > Probably something better left for a module, though it's fine with me if > someone wants to include it. > > Summing the first 1M primes "$sum += $_ for primes(1000000)" on a > slightly slower machine: > 38.1s old Math::Big > 1.7s new Math::Big > 0.2s new Math::Big returning @primes instead of mapping to BigInts > ~0.02s the various XS modules > > Looks much more reasonable. A lot of the time difference between the > non-BigInt and BigInt versions is the summation, which gets done as a > BigInt calculation. At 10M, I get 402s for old Math::Big, 14s for new > Math::Big, 1.2s for new Math::Big returning non-BigInts, and 0.13-0.18s > for XS modules (which all return non-BigInts for this range).
Yeah, the Math::Big* math is very slow, part idea of this module was to show "it works" and part "it is still very slow, see if we can make it faster". Using a better algorithmn of course yields lot of improvements, but the main point should be actually to make the Math::Big* math faster. So in this light I think that it is justified to leave it at this point. Thank you for your work, even tho I'm no longer involved in the Perl core development, I still use it quite heavily. All the best, tels -- http://bloodgate.com/galleries/
On Tue Dec 25 11:56:51 2012, nospam-abuse@bloodgate.com wrote: Show quoted text
> > On Sat, December 15, 2012 6:50 pm, Dana Jacobsen via RT wrote:
> > [...] > > 0.025s Math::Prime::Util 0.12 XS, Lehmer's method > > 0.36s Math::Prime::Util 0.09 XS, segmented mod-30 sieve > > 0.52s Math::Prime::Util:PP 0.14 Perl, Lehmer's method > > 2.90s Math::Prime::FastSieve 0.18 XS, good SoE > > 11.7s Math::Prime::XS 0.29 XS > > 15.0s Bit::Vector 7.2 XS > > 57.3s Math::Prime::Util::PP 0.14 Perl, string sieve > > "" Math::Big patched "" > > 169.5s Python mpmath primepi 0.17 Python, 25 GB RAM. > > 292.2s Python sympy primepi 0.7.1 Python > > 20000+ Math::Big 1.12 Perl, > 26GB RAM > > [...]
> > Hm, I think the actual times are missing?
Sorry, I meant that it's identical to the line above (57.3s), since they're using the same code in this case. Show quoted text
> > Summing the first 1M primes "$sum += $_ for primes(1000000)" on a > > slightly slower machine: > > 38.1s old Math::Big > > 1.7s new Math::Big > > 0.2s new Math::Big returning @primes instead of mapping to BigInts > > ~0.02s the various XS modules > > > > Looks much more reasonable. A lot of the time difference between the > > non-BigInt and BigInt versions is the summation, which gets done as a > > BigInt calculation. At 10M, I get 402s for old Math::Big, 14s for new > > Math::Big, 1.2s for new Math::Big returning non-BigInts, and 0.13-0.18s > > for XS modules (which all return non-BigInts for this range).
> > Yeah, the Math::Big* math is very slow, part idea of this module was to > show "it works" and part "it is still very slow, see if we can make it > faster". > > Using a better algorithmn of course yields lot of improvements, but the > main point should be actually to make the Math::Big* math faster. So in > this light I think that it is justified to leave it at this point. > > Thank you for your work, even tho I'm no longer involved in the Perl core > development, I still use it quite heavily.
I agree, for what it's worth. Thanks again for the reply. Dana


This service is sponsored and maintained by Best Practical Solutions and runs on Perl.org infrastructure.

Please report any issues with rt.cpan.org to rt-cpan-admin@bestpractical.com.