Hi Hans,
These things are learning exercises for me too. I agree that PARI/GP (and
Gap)
are interesting. I copied some algorithms from PARI for PermutationsA.jl.
Still, I find it interesting that the nextprime functions from (your)
Numbers.jl, Mathematica,
and PARI are very close in speed for some large arguments. I tried
nextprime(10^1000)
in Numbers.jl and PARI/gp and they both took about 900ms (PARI was 10%
faster). No
tables used anywhere. Mathematica took about 500ms for the same calculation.
I don't know how to count primes in an interval in PARI, but it does have a
primepi(x)
function. The doc says "Uses checkpointing and a naive O(x) algorithm".
If you look, this means
it finds the closest value in a table and then uses, in essence, nextprime.
Maybe you are
right and they don't feel much need for something faster:
? primepi(10^9 + 10^8) # looks like this is getting a close table
value
time = 273 ms.
%29 = 55662470
? primepi(2*10^9) # looks like no close table value. But I think
the tables are configurable somehow
time = 2,407 ms.
%30 = 98222287
But, PrimeSieve.jl does not need to use tables:
julia> @time primepi(10^9 + 10^8 + 10^6) # It has rather dense tables in
this range of values. This is a table value.
elapsed time: 6.89e-6 seconds (168 bytes allocated)
55710422
julia> @time primepi(10^9 + 10^8 + 10^6; alg = :sieve) # This uses no
table, just the sieve.
elapsed time: 0.0700969 seconds (224 bytes allocated)
55710422
julia> @time primepi(10^9 + 10^8 + 10^6; alg = :dr) # This uses no table,
just a modern version of the Legendre formula
elapsed time: 0.002998701 seconds (224 bytes allocated)
55710422
Anyway, thanks for putting your code up. It's been useful for comparing and
understanding sieves and nextprime.
--John
On Sunday, December 28, 2014 10:22:59 PM UTC+1, Hans W Borchers wrote:
>
> John,
>
> please consider that my Numbers.jl package is something I did as my first
> trial
> in working with Julia -- and left it behind after a few days. It is
> certainly
> not in a state nor has the intention to be comparable in speed or
> completeness
> to other such systems.
>
> As I said in another thread, when number theoretic computations are
> involved,
> PARI/GP is another system to look at closely, not only Mathematica or
> Maple.
> For instance, returning the next prime for really large input values takes
> only
> milliseconds ("See Ma, no tables!"):
>
> gp> nextprime(10^100)
> time = 9 ms.
> %1 = 100000000000000000000000000000000000000000000000000\
> 00000000000000000000000000000000000000000000000267
>
> There is no prime counting function. Probably as there is no direct need
> for
> this functionality for mathematicians, as you have already suspected. So
> the
> following trick counts primes:
>
> gp> n = 0;
> gp> forprime (p = 1841378967856, 1850000000000, n++);
> time = 1min, 49,432 ms.
> gp> n
> %4 = 305232179
>
> Of course, a prime counting function based on tables cannot be beaten.
> That is
> why I'm quite glad you have provided this library for Julia.
>
> If someone is thinking about a more extended number theory module for
> Julia, I
> would be glad to join and be of help.
>
>
