Double factorial and primorial

[bodrato at mail.dm.unipi.it]

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 think mine is somewhere around 1s I attach a source of it.
I do not remember how to compute times (I always use cycles...)
When run on shell it says:

The sieve uses: 5208334 (64-bit) limbs.
Cycles needed to sieve primes in [4,1000000000]: 3940715966 .
Cycles needed to loop on them: 2524448411 .
The sum of primes up to 1000000000 is : 24739512092254535 .

> I had had some fun night-hacking the new code, but I am not sure it will
> be useful for your binom code.  I *hope* to:

Sieving is not the most time-consuming portion either in fac_ui or in
bin_ui, but they will both benefit of a faster sieving.
Form the timings above, I can see that the time used for sieving and the
time used for looping is comparable... this means that a globally faster
sieving interface might reduce the need of a single sieving phase for many
loops.

The other bonus I get from the initial sieving phase is that, with a
popcount, I can count how many primes there are and estimate the space
needed for the next computations... but it can be worked around with
something like Stiring estimates or something like that...

> 1. Unify the two current prime sievers
> 2. Make a good prime sieving interface in GMP, possibly exported
> 3. Make gmp_nextprime (or its generalised offspring, as per (2)) run
>    much faster.

Great goals!

-- 
http://bodrato.it/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: sieve.c
Type: text/x-csrc
Size: 8997 bytes
Desc: not available
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20111223/edc0fdbd/attachment.bin>