Double factorial and primorial [Was: fac_ui rewrote]

bodrato at bodrato at
Sat Dec 17 22:38:33 CET 2011


Il Sab, 10 Dicembre 2011 9:19 pm, Torbjorn Granlund ha scritto:
> nisse at (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) ... (the product stopping at 1 for odd n and
>   2 for even n).

I implemented it, do you like the name mpz_fac2_ui?

> Aside from double factorial (Swedish semifakultet) we could supply
> either of the two common primorial definitions.  (One is: product of the
> first n primes, the other is: product of all primes below n.)

I implemented the second one: "primes below n (included, if prime)", I
called it mpz_primorial_ui. 50 lines of code recycling the structure built
for mpz_fac_ui.

Both code are asymptotically fast, and the implementation should be
reasonable for small sizes too.

I do not have a previous implementation to compare with, maybe I can put
size of the result and log(time) on the two axes, representing fac_ui,
fac2_ui, and primorial_ui (and bin_uiui(3n,n)?) on the same graph?

The current code can be found on the page:


PS: I'm working on the D&C bin_ui as Niels asked...


More information about the gmp-devel mailing list