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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

/*
    Copyright (C) 2025 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"
#include "mpn_extras.h"
#include "profiler.h"

int main(void)
{
    slong N = 1000;
    slong maxn = 20;
    double t0, t1, FLINT_SET_BUT_UNUSED(tt);

    ulong d, dinv, norm;
    mp_ptr A, Q, R;
    slong n, i;

    A = flint_malloc(sizeof(mp_limb_t) * maxn * N);
    Q = flint_malloc(sizeof(mp_limb_t) * maxn * N);
    R = flint_malloc(sizeof(mp_limb_t) * N);

    mpn_random(A, maxn * N);

    for (norm = 0; norm <= 4; norm += 4)
    {
        flint_printf("n          mpn_divrem_1    preinv    speedup\n");

        d = n_nextprime(UWORD(1) << (FLINT_BITS - 1 - norm), 1);
        norm = flint_clz(d);
        dinv = n_preinvert_limb_prenorm(d << norm);
        flint_printf("\nd = %wu\n\n", d);

        for (n = 1; n <= maxn; n++)
        {
            TIMEIT_START;
            for (i = 0; i < N; i++)
                R[i] = mpn_divrem_1(Q + n * i, 0, A + n * i, n, d);
            TIMEIT_STOP_VALUES(tt, t0);
            TIMEIT_START;
            for (i = 0; i < N; i++)
            {
                R[i] = flint_mpn_divrem_1_preinv(Q + n * i, A + n * i, n, d, dinv, norm);
            }
            TIMEIT_STOP_VALUES(tt, t1);
            t0 /= N; t1 /= N;
            flint_printf("%10wd    %8g    %8g    %.3f\n", n, t0, t1, t0  / t1);
        }

        if (norm == 0)
        {
            TIMEIT_START;
            for (i = 0; i < N; i++)
                R[i] = mpn_divrem_1(Q + 2 * i, 0, A + 2 * i, 2, d);
            TIMEIT_STOP_VALUES(tt, t0);
            TIMEIT_START;
            for (i = 0; i < N; i++)
                R[i] = flint_mpn_divrem_2_1_preinv_norm(Q + 2 * i, A + 2 * i, d, dinv);
            TIMEIT_STOP_VALUES(tt, t1);
            t0 /= N; t1 /= N;
            flint_printf("    2_norm    %8g    %8g    %.3f\n", t0, t1, t0  / t1);

            TIMEIT_START;
            for (i = 0; i < N; i++)
                R[i] = mpn_divrem_1(Q + 3 * i, 0, A + 3 * i, 3, d);
            TIMEIT_STOP_VALUES(tt, t0);
            TIMEIT_START;
            for (i = 0; i < N; i++)
                R[i] = flint_mpn_divrem_3_1_preinv_norm(Q + 3 * i, A + 3 * i, d, dinv);
            TIMEIT_STOP_VALUES(tt, t1);
            t0 /= N; t1 /= N;
            flint_printf("    3_norm    %8g    %8g    %.3f\n", t0, t1, t0  / t1);
        }
        else
        {
            TIMEIT_START;
            for (i = 0; i < N; i++)
                R[i] = mpn_divrem_1(Q + i, 0, A + i, 1, d);
            TIMEIT_STOP_VALUES(tt, t0);
            TIMEIT_START;
            for (i = 0; i < N; i++)
            {
                R[i] = n_divrem_preinv_unnorm(Q + i, A[i], d, dinv, norm);
            }
            TIMEIT_STOP_VALUES(tt, t1);
            t0 /= N; t1 /= N;
            flint_printf("  1_unnorm    %8g    %8g    %.3f\n", t0, t1, t0  / t1);

            TIMEIT_START;
            for (i = 0; i < N; i++)
                R[i] = mpn_divrem_1(Q + 2 * i, 0, A + 2 * i, 2, d);
            TIMEIT_STOP_VALUES(tt, t0);
            TIMEIT_START;
            for (i = 0; i < N; i++)
                R[i] = flint_mpn_divrem_2_1_preinv_unnorm(Q + 2 * i, A + 2 * i, d, dinv, norm);
            TIMEIT_STOP_VALUES(tt, t1);
            t0 /= N; t1 /= N;
            flint_printf("  2_unnorm    %8g    %8g    %.3f\n", t0, t1, t0  / t1);

            TIMEIT_START;
            for (i = 0; i < N; i++)
                R[i] = mpn_divrem_1(Q + 3 * i, 0, A + 3 * i, 3, d);
            TIMEIT_STOP_VALUES(tt, t0);
            TIMEIT_START;
            for (i = 0; i < N; i++)
                R[i] = flint_mpn_divrem_3_1_preinv_unnorm(Q + 3 * i, A + 3 * i, d, dinv, norm);
            TIMEIT_STOP_VALUES(tt, t1);
            t0 /= N; t1 /= N;
            flint_printf("  3_unnorm    %8g    %8g    %.3f\n", t0, t1, t0  / t1);
        }

        flint_printf("\n");
    }

    flint_free(A);
    flint_free(Q);
    flint_free(R);

    flint_cleanup_master();
    return 0;
}