Ciao
Il Lun, 19 Dicembre 2011 6:47 pm, bodr...@mail.dm.unipi.it ha scritto:
> Il Lun, 19 Dicembre 2011 10:14 am, Niels Möller ha scritto:
>> Since the established name is "double factorial", I think one should
>> use some reasonable abbreviation of that term. _dblfac_ seems good
>> enough to me, i
Ciao,
Il Ven, 23 Dicembre 2011 3:55 pm, Torbjorn Granlund ha scritto:
> Do you have a timing point for your code on shell? My code now needs
> 0.9 s on shell for the limit 10^9. The siever is still somewhat slow, I
> have done nothing to improve it with unrolling or clever loop indexing.
I thi
bodr...@mail.dm.unipi.it writes:
When I wrote my sieve, I used to compute the sum of all primes up-to a
given limit to measure the time required for sieving and looping. As a
side effect, you also obtain a checksum, to avoid trivial mistakes :-)
Clever. :-) I pipe the result to the sha1
Ciao,
Il Gio, 22 Dicembre 2011 9:23 pm, Torbjorn Granlund ha scritto:
> ni...@lysator.liu.se (Niels Möller) writes:
>
> Then I imagine it would be good to use Marco's layout, with one bit for
> each number equal to ±1 (mod 6). (The Erathostenes code I wrote a while
> ago uses the easier repr
ni...@lysator.liu.se (Niels Möller) writes:
Then I imagine it would be good to use Marco's layout, with one bit for
each number equal to ±1 (mod 6). (The Erathostenes code I wrote a while
ago uses the easier representation of one bit per odd number).
It turned out my profiling data was in
Torbjorn Granlund writes:
> Sieving bits (not bytes) there would help, since the sieving accounts
> for 0% of the time.
[...]
> Even if bit fiddling would make that part 10 times slower, it will still
> be hard to measure.
Then I imagine it would be good to use Marco's layout, with one bit for
Joerg Arndt writes:
I think the data-dependent branches killed it for me
(a simple binary heap was used).
My heap removal code avoids branches; the ceil(log n) operations has no
data dependent branch.
The insertion code has an amortised running time of O(1), but the
termination branch is
* Torbjorn Granlund [Dec 22. 2011 07:21]:
> Joerg Arndt writes:
>
> * Niels Möller [Dec 20. 2011 16:05]:
> > Torbjorn Granlund writes:
> >
> > > then one could sort the indexes using a minheap.
> >
> > Clever!
> >
>
> A bit of a warning: I once used a heap to do essential
ni...@lysator.liu.se (Niels Möller) writes:
> 95% of the time is spent in heap_remove, unsurprisingly.
And to decrease the heap work, one could keep the small primes in an
array outside of the heap (as you suggested). Or use a larger sieving
table. Or use a more compact representation t
Torbjorn Granlund writes:
> I implemented a variant where all primes live in the heap, perhaps
> exactly what Niels suggested.
Interesting!
> 95% of the time is spent in heap_remove, unsurprisingly.
And to decrease the heap work, one could keep the small primes in an
array outside of the heap
I implemented a variant where all primes live in the heap, perhaps
exactly what Niels suggested.
It is just proof-of-concept code, and the initial prime table is made
naively using trial division. After that, there is no division or
multiplication.
This code computes all primes < 10^9 in 2s (on
Torbjorn Granlund writes:
A corrected version:
for i = 0 ... Pi(2*S)-1
p = primevec[i].p
s = primevec[i].off
while s < S
sieve[s] = 1;
primevec[i].off = s - 2*S
while true
= pop(heap)
if (off >= s0 + 2*S)
break
si
ni...@lysator.liu.se (Niels Möller) writes:
Torbjorn Granlund writes:
> For primes < 2*S, we sieve as usually, i.e., good old Eratosthenes. For
> primes > 2*S we insert the squares in a minheap.
One could do a kind of unified way. Use a current block (bitmap). Get
the smallest el
Il Mer, 21 Dicembre 2011 1:36 pm, Niels Möller ha scritto:
> bodr...@mail.dm.unipi.it writes:
> I imagine this interface is for efficiently generating a large number of
> small primes. For large primes, one would have to iterate over
> mpz_nextprime. Are there any large savings from storing additi
bodr...@mail.dm.unipi.it writes:
> A range delimited by? two unsigned long?
I imagine this interface is for efficiently generating a large number of
small primes. For large primes, one would have to iterate over
mpz_nextprime. Are there any large savings from storing additional state
between call
Il Mer, 21 Dicembre 2011 10:56 am, Niels Möller ha scritto:
> The simplest and *general* interface I can come up with takes a range as
A range delimited by? two unsigned long?
To be *general* we should allow two mpzs... but it looks too hard to
implement.
> input, and a callback function. And the
bodr...@mail.dm.unipi.it writes:
> It is hard to decide what a public interface should give as a result:
> a list of primes?
The simplest and *general* interface I can come up with takes a range as
input, and a callback function. And then that callback function is
invoked for each prime in the in
Torbjorn Granlund writes:
> For primes < 2*S, we sieve as usually, i.e., good old Eratosthenes. For
> primes > 2*S we insert the squares in a minheap.
One could do a kind of unified way. Use a current block (bitmap). Get
the smallest element from the heap (p and a multiple of p), mark it in
the
Ciao,
Il Lun, 19 Dicembre 2011 6:47 pm, bodr...@mail.dm.unipi.it ha scritto:
> Il Lun, 19 Dicembre 2011 10:14 am, Niels Möller ha scritto:
>> Maybe there's no better way to compute the number of primes than to
>> use the sieve of Erathostenes' to generate them all?
> To have the exact count, I be
Ciao,
Il Mar, 20 Dicembre 2011 12:23 pm, Torbjorn Granlund ha scritto:
> I agree we want a shared prime sieve, at least for internal use.
> It would be nice not to have two (as today).
>
> Perhaps it makes sense to have two, but then we should have a clear
> idea why both are really needed.
I ca
ni...@lysator.liu.se (Niels Möller) writes:
Torbjorn Granlund writes:
> then one could sort the indexes using a minheap.
Clever!
That would give the following algorithm for generating primes up to n:
1. Generate a list of all primes p_k up to sqrt(n).
2. Create a minhea
Joerg Arndt writes:
* Niels Möller [Dec 20. 2011 16:05]:
> Torbjorn Granlund writes:
>
> > then one could sort the indexes using a minheap.
>
> Clever!
>
A bit of a warning: I once used a heap to do essentially the same
thing, it turned that using a simple array was sign
* Niels Möller [Dec 20. 2011 16:05]:
> Torbjorn Granlund writes:
>
> > then one could sort the indexes using a minheap.
>
> Clever!
>
A bit of a warning: I once used a heap to do essentially the same
thing, it turned that using a simple array was significantly faster
(factor 20 or so). The a
Torbjorn Granlund writes:
> then one could sort the indexes using a minheap.
Clever!
That would give the following algorithm for generating primes up to n:
1. Generate a list of all primes p_k up to sqrt(n).
2. Create a minheap which for each k contains the smallest odd multiple
of p_k whi
I'd suggest that we add both primorial functions:
1. product of all primes <= n
2. product of the smalles n primes
I have no idea about which of them is most common, or what they should
be named.
--
Torbjörn
___
gmp-devel mailing list
gmp-devel@gmpli
ni...@lysator.liu.se (Niels Möller) writes:
I don't know how important that is. Long-term, I think gmp should at
least export some sieving functionality which us suitable as a building
block for that.
I agree we want a shared prime sieve, at least for internal use. It
would be nice not t
bodr...@mail.dm.unipi.it writes:
> If we really want a prime_count function in GMP I can write a more clever one
I don't know how important that is. Long-term, I think gmp should at
least export some sieving functionality which us suitable as a building
block for that.
>>> counting the primes in
Il Mar, 20 Dicembre 2011 8:03 am, bodr...@mail.dm.unipi.it ha scritto:
> Il Lun, 19 Dicembre 2011 9:15 pm, Niels Möller ha scritto:
>> primes up to n, you need to first create a list of primes up to sqrt(n),
>> and represent it in any convenient way which lets you iterate over it
>
>> Above sqrt(n
Ciao,
Il Lun, 19 Dicembre 2011 9:15 pm, Niels Möller ha scritto:
>> In fac_ui.c there already is a function for sieving: bitwise_primesieve.
>> It fills an mp_ptr "with the characteristic function of composite"s, and
>> it returns the count of "prime integers in the interval [4, n]".
>
> That's go
ni...@lysator.liu.se (Niels Möller) writes:
> In fac_ui.c there already is a function for sieving: bitwise_primesieve.
> It fills an mp_ptr "with the characteristic function of composite"s, and
> it returns the count of "prime integers in the interval [4, n]".
That's going to use a lot
bodr...@mail.dm.unipi.it writes:
> An asymptotically faster sieve than Erathosteses' exists, but I do not
> know if it is worth implementing it; as it is O(N/loglogN) compared to
> O(N)...
I see. So Erathostenes it is, then.
> In fac_ui.c there already is a function for sieving: bitwise_primesie
Ciao,
Il Lun, 19 Dicembre 2011 10:14 am, Niels Möller ha scritto:
> bodr...@mail.dm.unipi.it writes:
> Since the established name is "double factorial", I think one should
> use some reasonable abbreviation of that term. _dblfac_ seems good
> enough to me, if _double_fac_ is too long.
Finally I
bodr...@mail.dm.unipi.it writes:
> _facfac_ or _dblfac_ ?
Since the established name is "double factorial", I think one should use
some reasonable abbreviation of that term. _dblfac_ seems good enough to
me, if _double_fac_ is too long.
> I believe that it is worse than factoring. By the way I i
Ciao,
Il Dom, 18 Dicembre 2011 9:13 am, Niels Möller ha scritto:
> Nice! Maybe it would be good with a slightly longer name, "2" is used
> for many other things. Maybe "mpz_double_fac_ui" is better?
_facfac_ or _dblfac_ ?
> I wonder for how large n it is practical to count the number of primes
>
bodr...@mail.dm.unipi.it writes:
> I implemented it, do you like the name mpz_fac2_ui?
Nice! Maybe it would be good with a slightly longer name, "2" is used
for many other things. Maybe "mpz_double_fac_ui" is better?
> I implemented the second one: "primes below n (included, if prime)", I
> call
Ciao,
Il Sab, 10 Dicembre 2011 9:19 pm, Torbjorn Granlund ha scritto:
> ni...@lysator.liu.se (Niels M�ller) writes:
> If you are using such building blocks, maybe it would make sense to
> export a function for the "semi-factorial"? In my calculus course it was
> denoted n!! = n (n-2) (n-4)
36 matches
Mail list logo
