On Saturday, April 23, 2016 at 3:20:32 PM UTC-7, Volker Braun wrote:
>
> I'm guessing that its not a coincidence that Mersenne twister has a period
> of 2^19937 ;-)
>
> Probably not!
> The relevant code is
> in sage.matrix.matrix_mod2_dense.Matrix_mod2_dense.randomize
>
> Not sure exactly whats wrong but taking rstate.c_random() % (number of
> columns) at the very least leads to modulo bias
>
>
I've created ticket #20493 for this issue. One observation I made there is
that when density != 1 this problem seems to go away, probably because
randomize is running different code in that case. The key snippet seems to
be:
{{{
mask = __M4RI_LEFT_BITMASK(self._entries.ncols % m4ri_radix)
for i from 0 <= i < self._nrows:
for j from 0 <= j < self._entries.width:
# for portability we get 32-bit twice rather than
64-bit once
low = gmp_urandomb_ui(rstate.gmp_state, 32)
high = gmp_urandomb_ui(rstate.gmp_state, 32)
self._entries.rows[i][j] = m4ri_swap_bits(
((<unsigned long long>high)<<32) | (<unsigned long long>low) )
self._entries.rows[i][self._entries.width - 1] &= mask
}}}
This seems to be filling out each row using successive random 32-bit words
from gmp, lopping off the extra bits at the end. Is that a bad idea for
some reason?
Kiran
>
> On Saturday, April 23, 2016 at 11:16:33 PM UTC+2, Kiran Kedlaya wrote:
>>
>> I just tried the following experiment on several different machines;
>> several different recent versions of Sage; algorithm = ple, m4ri; and n =
>> 20000, 25000, 30000. In all cases, the result is identical:
>>
>> sage: M = MatrixSpace(GF(2), n)
>> sage: for i in range(10):
>> ...: print M.random_element().rank()
>> 19937
>> 19937
>> 19937
>> 19937
>> 19937
>> 19937
>> 19937
>> 19937
>> 19937
>> 19937
>>
>> Using the Internet, I also retroactively tested this in Sage 4.0.1.
>> (Search in the page for "19937".)
>>
>> https://wiki.sagemath.org/sagebeatsmagma
>>
>> By contrast, I just tried a whole bunch of sparse examples coming from
>> Cremona modular symbols that gave more plausible answers, e.g.:
>> sage: S = CremonaModularSymbols(300001, sign=-1)
>> sage: T =
>> hecke_matrix(2).sage_matrix_over_ZZ().change_ring(GF(2)).dense_matrix()
>> sage: T.dimensions()
>> (27549, 27549)
>> sage: T.rank()
>> 27461
>>
>> I'm not sure if this rank is correct, but at least it's not 19937.
>>
>> Kiran
>>
>>
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
