C++ factorial, primorial

[Marc Glisse]

On Tue, 24 Jun 2014, Torbjörn Granlund wrote:

> Marc Glisse <marc.glisse at inria.fr> writes:
>
>  I am trying to make a few more functions easily available from the C++
>  interface. mpz_fac_ui takes an unsigned long, so it would be natural
>  to have a factorial function that takes any of {signed,unsigned}
>  {char,short,int,long}. It would probably throw an out_of_range error
>  for negative values. But since it does not take a gmp type as
>  argument, I should not make it a free function in the global
>  namespace. The easiest seems to be a static member function, so we
>  would call:
>
>  mpz_class::factorial(42);
> 
> I don't understand what a "free function in the global namespace" might
> mean, which makes it tough for me to make a good answer.

Something like:
mpz_class factorial(unsigned long);

That would be bad because it would conflict with any other bignum library 
providing:
bigint factorial(unsigned long);

where calling factorial(42) wouldn't know which one to pick.

>  If we have an mpz_class that represents a small enough number, we
>  would probably like to be able to use factorial on it directly without
>  explicitly extracting an unsigned long. We could have
>  mpz_class::factorial(z); but since there is a GMP argument, this
>  versions could also be available as simply factorial(z);. Because of
>  the way it would be done with templates, factorial(42) would not
>  compile (it would not automatically convert 42 to mpz_class), which is
>  good. However, I think we could do without this global factorial for
>  now, and it can be added later if people want it.
> 
> I suppose I'd need to understand the alterantives, i.e., how user code
> would look as a result of these design decisions.

Let us look at the possible ways a user could call the function (z is an 
mpz_class).

1) factorial(42)
2) factorial(z)
3) mpz_class::factorial(42)
4) mpz_class::factorial(z)
5) gmpxx::factorial(42)
6) gmpxx::factorial(z)
7) z.factorial()

1 is bad, as said above. 7 is not so good because most of the time we want 
to compute factorial of an int and don't want to convert it to mpz_class 
first. All the others seem ok to me. Supporting both 3-4 and 5-6 seems 
unnecessary. 5-6 have the advantage that a user can write:
using gmpxx::factorial;
and then use 1 and 2.

Note that factorial(mpz_class) would actually be implemented with a 
template, so calling factorial(42) would not try to convert 42 to an 
mpz_class.

Implementing 2-3-4 seems easy. Implementing 2-5-6 in a way that lets 
"using gmpxx::factorial" work is a bit more fragile. What comes to mind 
is:
namespace gmpxx { mpz_class factorial(mpz_class); }
using gmpxx::factorial;
namespace gmpxx { mpz_class factorial(unsigned long); }
(hoping that all compilers implement this import properly)

Or maybe this would be easier on bad compilers:
mpz_class factorial(mpz_class);
namespace gmpxx { using ::factorial; mpz_class factorial(unsigned long); }

-- 
Marc Glisse