[GAP Forum] RandomMat with really random source

[Alexander Konovalov]

On 23 Jul 2014, at 22:54, Ha T. Lam <hatlam at gmail.com> wrote:

> Dear Alexander,
> 
> 
> On Wed, Jul 23, 2014 at 5:40 PM, Alexander Konovalov <alexk at mcs.st-andrews.ac.uk> wrote:
> Dear Ha,
> 
> On 23 Jul 2014, at 22:19, Ha T. Lam <hatlam at gmail.com> wrote:
> 
> > Dear GAP forum,
> >
> > I'm trying to generate random 2x2 matrices with entries from GF(947).
> > Normally, I would just use RandomMat(2,2,GF(947)), but I want to get
> > different results every time I start GAP. I found that RandomSource( r, dev
> > ) from the io package (
> > http://www.gap-system.org/Manuals/pkg/io/doc/chap6.html) allows randomness
> > from /dev/random, but I don't know how to use it as the random source for
> > RandomMat. Any advice?
> 
> This is doable - first you have to create a real random source:
> 
> gap> rs:=RandomSource(IsRealRandomSource,"random");
> <a real random source>
> 
> Then you may create a list of all elements of GF(947) and pick up
> elements from it using "Random":
> 
> ​​gap> gf:=AsList(GF(947));;
> gap> Random(rs,gf);
> Z(947)^42
> gap> Random(rs,gf);
> Z(947)^817
> 
> Now you may take the code for RandomMat from the library and adjust it to
> say ReallyRandomMat which will use the approach above instead of calling
> Random( GF(947) );
> 
> There is a warning, however. If it may be enough for you to use dev/urandom
> instead of dev/random, then it is advised to go for the 'urandom' option.
> I remember once we were very puzzled by the slow performance of GAP on the
> server where dev/random was used to generate some random strings. It was
> not possible to reproduce the slowdown at all while using GAP interactively.
> Then we figured out what happened: dev/random needs some noise in the
> entropy pool, and it may block when the pool is empty to wait for some more
> events to happen. There was a plenty of events when one was sitting in front
> of the keyboard; however, that was not the case on the server when GAP was
> running as a daemon. So please be aware of this feature.
> 
> Hope this helps,
> Alexander
> ​
> ​
> T​hank you very much for the quick reply and the warning. I was trying to use 'random' instead of 'urandom' and was indeed puzzled by the speed decrease. In my code, I used  ​List(GF(947)) instead of ​AsList(GF(947)). Do you know if this makes a difference? The manual only tells me that AsList gives roughly the same access time to elements. 

There is some difference: AsList is an attribute and is not recomputed next time you call it:

gap> f:=GF(947);
GF(947)
gap> AsList(f);;time;
4
gap> KnownAttributesOfObject(f);
[ "Size", "Representative", "Enumerator", "AsList", "OneImmutable", 
  "Characteristic", "GeneratorsOfDomain", "LeftActingDomain", 
  "MultiplicativeNeutralElement", "GeneratorsOfRing", 
  "GeneratorsOfRingWithOne", "Dimension", "DegreeOverPrimeField", 
  "GeneratorsOfDivisionRing", "PrimitiveRoot" ]
gap> AsList(f);;time;
0

OTOH, List is a function which will return new mutable list each time you call it. Just compare

gap> l:=AsList(f);;
gap> IsMutable(l);
false

with

gap> l:=List(f);;
gap> IsMutable(l);
true

It's not too expensive for GF(947) though, and I guess that next calls to List will somehow reuse existing AsList, but still is less efficient. My assumption is that "random vs urandom" contributes much more to the difference in performance in this case. With larger primes, keeping a list of all elements of GF(p) will became an obstacle, indeed. My suggestion would be to use Enumerator (see `?Enumerator'), which may return an element of the collection (the field in this case) by its position, for example:

gap> rs:=RandomSource(IsRealRandomSource,"random");
<a real random source>
gap> p:=NextPrimeInt(1000000);
1000003
gap> gf:=GF(p);
GF(1000003)
gap> enum:=Enumerator(gf);
<enumerator of GF(1000003)>
gap> n:=Random(rs,[1..Size(gf)]);
41332
gap> enum[n];
ZmodpZObj( 41331, 1000003 )
gap> n:=Random(rs,[1..Size(gf)]);
725956
gap> enum[n];
ZmodpZObj( 725955, 1000003 )

In this case you need to keep the range [1..Size(gf)] which is given just by the first and last elements instead of the whole list of elements of the field. Hope this will help.

Best wishes
Alexander



> I am also worried about working with a larger prime, would this method create an in-memory list of all the elements? Is there anyway to do a sort of "lazy evaluation"?
> 
> Thank you,
> 
> Ha
>