On 23 Jul 2014, at 22:54, Ha T. Lam <hat...@gmail.com> wrote:
Dear Alexander,
On Wed, Jul 23, 2014 at 5:40 PM, Alexander Konovalov
<al...@mcs.st-andrews.ac.uk> wrote:
Dear Ha,
On 23 Jul 2014, at 22:19, Ha T. Lam <hat...@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
Thank 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
_______________________________________________
Forum mailing list
Forum@mail.gap-system.org
http://mail.gap-system.org/mailman/listinfo/forum
