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

/*
    Copyright 2009 William Hart
    Copyright 2010, 2021 Fredrik Johansson
    Copyright 2020 Daniel Schultz

    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 "profiler.h"
#include "nmod_mat.h"
#include "ulong_extras.h"
#include "thread_support.h"
#include "perm.h"

typedef struct
{
    slong n;
    ulong modulus;
    int algorithm;
} mat_lu_t;

void sample(void * arg, ulong count)
{
    mat_lu_t * params = (mat_lu_t *) arg;
    int algorithm = params->algorithm;
    slong * P;
    nmod_mat_t A, LU;
    ulong i;
    flint_rand_t state;

    flint_rand_init(state);

    nmod_mat_init(A, params->n, params->n, params->modulus);
    nmod_mat_init(LU, params->n, params->n, params->modulus);
    nmod_mat_randfull(A, state);
    P = _perm_init(params->n);

    prof_start();

    if (algorithm == 0)
        for (i = 0; i < count; i++)
        {
            nmod_mat_set(LU, A);
            nmod_mat_lu(P, LU, 0);
        }
    else if (algorithm == 1)
        for (i = 0; i < count; i++)
        {
            nmod_mat_set(LU, A);
            nmod_mat_lu_classical(P, LU, 0);
        }
    else if (algorithm == 2)
        for (i = 0; i < count; i++)
        {
            nmod_mat_set(LU, A);
            nmod_mat_lu_classical_delayed(P, LU, 0);
        }
    else
        for (i = 0; i < count; i++)
        {
            nmod_mat_set(LU, A);
            nmod_mat_lu_recursive(P, LU, 0);
        }

    prof_stop();

    nmod_mat_clear(A);
    nmod_mat_clear(LU);
    _perm_clear(P);

    flint_rand_clear(state);
}

slong bits_tab[] = { 5, 14, 15, 25, 30, 31, 32, 33, 60, 61, 62, 63, 64, 0 };

int main(void)
{
    double max;
    mat_lu_t params;
    slong i, bits, n;

    flint_printf("nmod_mat_lu:\n");

    flint_set_num_threads(1);
    flint_printf("threads = %wd\n", flint_get_num_threads());

    for (i = 0; (bits = bits_tab[i]) != 0; i++)
    {
        for (n = 4; n <= 1000; n += n/4 + 1)
        {
            double min_default = 0, min_classical = 0, min_delayed = 0, min_recursive = 0;

            params.n = n;
            params.modulus = n_nextprime(UWORD(1) << (bits - 1), 0);

            params.algorithm = 0;
            prof_repeat(&min_default, &max, sample, &params);

            params.algorithm = 1;
            prof_repeat(&min_classical, &max, sample, &params);

            params.algorithm = 2;
            prof_repeat(&min_delayed, &max, sample, &params);

            params.algorithm = 3;
            prof_repeat(&min_recursive, &max, sample, &params);

            flint_printf("b = %wd  n = %wd  default %.2f us  classical %.2f us  delayed %.2f us  recursive %.2f us\n",
                bits, n, min_default, min_classical, min_delayed, min_recursive);
        }
    }

    return 0;
}