flintlib
Polynomials/matrices/vectors mod n, random generation: add uniform random?
Currently, most objects (polynomials, vectors, matrices, ...) composed of nmod or fmpz_mod coefficients offer some functions for filling coefficients with random entries that have a special property (typically calling n_randtest, with the probability of special values or sparsity increased, see https://flintlib.org/doc/ulong_extras.html#c.n_randtest ).
Would there be any objections against adding functions for filling objects in a dense way and with uniformly random coefficients? I often such "uniformly random generation" e.g. for benchmarks or in the writing of randomized algorithms, and was wondering whether its absence from FLINT is deliberate.
No, I don't think it is deliberate. You can use n_randint for the backend, which generates a uniformly random integer in the given range.
I am working on the fmpz_mod_mat case: the randtest actually generates a uniform dense matrix and should be called randfull. An actual randtest should be added, and implementations should switch names.
Is there a reason why nmod_mat_randfull never generates a zero ?
nmod_mat_entry(mat, i, j) = FLINT_MAX(1, n_randint(state, mat->mod.n));
Is there a reason why nmod_mat_randfull never generates a zero ?
nmod_mat_entry(mat, i, j) = FLINT_MAX(1, n_randint(state, mat->mod.n));
The doc is saying that this is supposed to insert entries "close to the modulus" notably for overflow issues detection, so I suppose it is ok to have them nonzero (?).
I am working on the fmpz_mod_mat case: the randtest actually generates a uniform dense matrix and should be called randfull. An actual randtest should be added, and implementations should switch names.
I don't think it is uniform, there is some fmpz_randtest running in. But indeed I don't see some sparsity being introduced (unlike in nmod_mat_randtest).
Yes, randfull is not the same as uniformly random. It's specifically designed to detect overflow cases.
Places where a rand (and not randtest) has been implemented so far:
- [ ] nmod (base type, I guess that would be a unuseful wrapper around
n_randint) - [x] nmod_vec
- [x] nmod_mat
- [ ] nmod_poly
- [ ] nmod_poly_mat
- [ ] nmod_mpoly
- [ ] mpn_mod
- [ ] fmpz_mod (base type, unuseful?)
- [x] fmpz_mod_mat
- [ ] fmpz_mod_poly
- [ ] fmpz_mod_mpoly
- [ ] fmpz_mod_mpoly_q
fmpz_mod_poly uses randm as backend, which is the equivalent of n_randint for fmpz_t. It does generate uniform coefficients in a dense manner.
Should I add a rand function and change randtest to generate sparse polynomials for fmpz_mod_poly as well? Is there a need for a randfull (non-zero coefficients generated in an almost uniform manner) in all the above modules?
EDIT: random functions are sometimes spread in multiple source files, sometimes gathered in a single randtest.c. Should I put them all in a rand.c file or let them as they are ?
Should I add a rand function and change randtest to generate sparse polynomials for fmpz_mod_poly as well?
That would make sense.
Is there a need for a randfull (non-zero coefficients generated in an almost uniform manner) in all the above modules?
I don't think so. This is only really needed to test some specific algorithms.
Besides, I think randfull could be superseded by mat_randtest and vec_randtest functions that occasionally generate vectors of nearly full entries.