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/