flint-sys 0.9.0

Bindings to the FLINT C library
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

/*
    Copyright (C) 2011 Fredrik Johansson

    This file is part of FLINT.

    FLINT is free software: you can redistribute it and/or modify it under
    the terms of the GNU Lesser General Public License (LGPL) as published
    by the Free Software Foundation; either version 3 of the License, or
    (at your option) any later version.  See <https://www.gnu.org/licenses/>.
*/

#include "ulong_extras.h"


static const ulong small_factorials[] =
{
    UWORD(1), UWORD(1), UWORD(2), UWORD(6), UWORD(24), UWORD(120), UWORD(720), UWORD(5040), UWORD(40320), UWORD(362880),
    UWORD(3628800), UWORD(39916800), UWORD(479001600),
#if FLINT64
    UWORD(6227020800), UWORD(87178291200),
    UWORD(1307674368000), UWORD(20922789888000), UWORD(355687428096000), UWORD(6402373705728000),
    UWORD(121645100408832000), UWORD(2432902008176640000),
#endif
};

#if FLINT64
#define MAX_SMALL_FACTORIAL 20
#else
#define MAX_SMALL_FACTORIAL 12
#endif


ulong n_factorial_mod2_preinv(ulong n, ulong p, ulong pinv)
{
    ulong prod, hi, lo;

    if (n <= MAX_SMALL_FACTORIAL)
        return n_mod2_preinv(small_factorials[n], p, pinv);

    if (n >= p)
        return UWORD(0);

    if (n >= UWORD(1000000))
        return n_factorial_fast_mod2_preinv(n, p, pinv);

    prod = small_factorials[MAX_SMALL_FACTORIAL];
    lo = n;
    n--;

    /* TODO: speedup for n in the range of sqrt(UWORD_MAX) */
    while (n > MAX_SMALL_FACTORIAL)
    {
        umul_ppmm(hi, lo, lo, n);

        if (hi)
        {
            lo = n_ll_mod_preinv(hi, lo, p, pinv);
            prod = n_mulmod2_preinv(prod, lo, p, pinv);
            lo = UWORD(1);
        }

        n--;
    }

    return n_mulmod2_preinv(prod, lo, p, pinv);
}