Convert more Random methods to use InstallMethodWithRandomSource

[fingolfin]

In PR #810, the new InstallMethodWithRandomSource was introduced.

We should convert more Random methods in the library to use InstallMethodWithRandomSource, and, once a release of GAP supporting it has been made, we should also get packages to use it.

UPDATE: Also, once GAP 4.9 has been released (resp. a stable release of it is out, presumable 4.9.1 or 4.9.2), we should look into nudging package authors into using InstallMethodWithRandomSource resp. InstallOtherMethodWithRandomSource. Some relevant packages include:

• automgrp
• congruence
• corelg
• fining
• fr (merged, not yet released)
• genss (merged, not yet released)
• guarana
• hap
• img (see Use InstallMethodWithRandomSource gap-packages/img#13)
• io
• laguna
• LocalizeRingForHomalg
• lpres
• MatricesForHomalg
• polycyclic (merged, not yet released)
• rcwa
• Semigroups
• YangBaxter

[fingolfin]

This is a newcomer friendly issue in that it should be relatively easy to make some progress on it, and thus "wet your feet" in GAP development. To get an idea about the kind of changes that need to be done, see e.g. PR #1599.

To get an idea of places that need to be adapted, one can use the command git grep -w "InstallMethod( *Random" insider the GAP repository. Ignoring the matches in lib/random.gi, there are still a few dozen matches in lib and hpcgap/lib.

[grouptheoryenthusiast]

Hi @fingolfin ,
Before going off and changing a bunch of these, I wanted to confirm I had the correct idea.
Would

#M  Random( <A> ) . . . . . . . . . . . . . . . . . . . . for additive cosets
##
InstallMethodWithRandomSource( Random,
    "for a random source and an additive coset",
    true,
    [ IsRandomSource, IsAdditiveCoset ], 0,
    {rs, A} -> Representative( A ) + Random( rs, AdditivelyActingDomain( A ) ) );

be a suitable change, or am I overlooking something?

Thank you

[fingolfin]

@grouptheoryenthusiast that does seem plausible, however, be careful because this can lead to regressions if there are some values for AdditivelyActingDomain(A) where Random with a random source has not yet been implemented. Being uncertain about that is one of the reasons why I did not convert that particular function yet.

That said, we might be there already, so I don't mean to discourage you from submitting it via a PR, just wanted to make sure you are aware of this potential problem. In any case, if you make sure that this function is actually tested by some test case, ideally by adding some explicit tests triggering it to random.tst, then I am confident we can get somewhere with it.

[fingolfin]

A recent PR which did changes as described in this PR was PR #2115.

[ChrisJefferson]

Yes, in some cases I found my problem was I couldn't build a set of objects to test the code. While doing it, it's worth trying to build a bunch of different things to test with (much of this code is fairly untested), such as cosets of size 1, that kind of thing. Hopefully it's easy to slot into the tester, as in #2115, let us know if you have any problems with that.

[grouptheoryenthusiast]

Hi @fingolfin and @ChrisJefferson ,
As per your advice I have been testing on different things.
I think I have encountered the issue you predicted.
With

gap> R:=SmallRing(5,1);;
gap> Random(AdditiveCoset(R,R.1));
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `Random' on 2 arguments at /home/james/gap/lib/methsel2.g:250 called from
Random( rs, AdditivelyActingDomain( A ) ) at /home/james/gap/lib/addcoset.gi:149 called from
func( GlobalMersenneTwister, x ) at /home/james/gap/lib/random.gd:158 called from
<function "unknown">( <arguments> )
 called from read-eval loop at *stdin*:12

Please could you advise me what I should do to fix this.
Thank you
James

[ChrisJefferson]

Somewhere there will be the Random function for AdditivelyActingDomain(A), you need to find that function and fix it first.

If you can't figure out which other function needs improving first, one way of doing that would be to use the profiling package. While you don't care how much time is being spent, it will show you all the lines of code which are being executed when you call Random(AdditiveCoset(R,R.1)), so you can figure out the function that needs fixing.

[fingolfin]

ApplicableMethod should help with tracking down the relevant method.

[grouptheoryenthusiast]

Hi @fingolfin and @ChrisJefferson ,
I think that the method that needs changing is random for a finite collection.
If I make a change along the following lines:

##  an enumerator of <C> and selects a random element of this list using the
##  function `RandomList', which is a pseudo random number generator.
##
if IsHPCGAP then
    MakeThreadLocal( "GlobalMersenneTwister" );
else
    DeclareGlobalVariable( "GlobalMersenneTwister" );
fi;
InstallGlobalFunction( RandomList, function(rs,list)
  return list[Random(rs, 1, Length(list))];
end );
InstallMethodWithRandomSource( Random, 
    "for a random source and a (finite) collection",
    [ IsRandomSource, IsCollection and IsFinite ],
    {rs,C} -> RandomList(rs, Enumerator( C ) ) );

RedispatchOnCondition(Random,true,[IsCollection],[IsFinite],0);

I get errors including:

Error before error-handling is initialized: 
[ "Variable: 'InstallMethodWithRandomSource' must have a value" 
 ]

I wonder if this means that I am calling InstallMethodWithRandomSource , before it is defined and what to do about that.
If I am barking up the wrong tree please let me know :D
Thanks,
James

[ChrisJefferson]

No, you are barking up the right tree, but you've hit a fairly horrible case :) That copy of Random is defined really early, before InstallMethodWithRandomSource. Let me see if I can pick this particular one apart.

[grouptheoryenthusiast]

@ChrisJefferson
Okay phew! That's a relief :D

[ChrisJefferson]

Just to keep you up to date, I've made PR #2204 , which will hopefully clean this up. I had to move some methods around a little, but the patch isn't too big.

[grouptheoryenthusiast]

Thanks, I just read through your PR and it is a very useful learning tool because I can see exactly what you did to overcome the issues I was struggling with!

[grouptheoryenthusiast]

For completeness and in case it is useful in testing the other PR, I will add here the tests I am working with.

#
# additive cosets
#
gap> randomTestForSizeOneCollection(AdditiveCoset(ZmodnZ(1),Identity(ZmodnZ(1))),Random);
gap> randomTest(AdditiveCoset(Integers,2),Random);
gap> randomTest(AdditiveCoset(CF(5),-2/3*E(5)-1/2*E(5)^2+1/3*E(5)^4),Random);
gap> randomTest(AdditiveCoset(GF(17),Z(17)^9),Random);
gap> R := SmallRing(10,2);;
gap> randomTest(AdditiveCoset(R,5*R.1),Random);
gap> a:= Algebra( GF(2), [ [ [ Z(2) ] ] ] );;
gap> rm:= FreeMagmaRing( GF(2), a );;
gap> randomTest(AdditiveCoset(rm, rm.1), Random);

[fingolfin]

@grouptheoryenthusiast nice, looking forward to a PR!

[grouptheoryenthusiast]

@fingolfin thanks, I am not completely familiar with the git workflow, but as I am relying on PR #2204 I assume I wait for that to be merged until I submit this? Is that correct?
Thanks,

[fingolfin]

Yes!

[ChrisJefferson]

So just to say, what we are having problems with is specifically the Random(IsRandomSource, IsListOrCollection) overload. If you have any changes that don't require that to be fixed, then they should (I hope!) be mergable straight away.

[grouptheoryenthusiast]

@ChrisJefferson , I have been looking at random in oprt.gi too.
Things work fine there, except when the TryNextMethod is called for some external orbits, (for instance
orbs:=ExternalOrbits(SymmetricGroup(4),[1..4]);;, ). In that case the method GAP ends up using is Random for a (finite) collection and so the randomTest function then fails.

[grouptheoryenthusiast]

A quick update, I see that your pull request has now been merged. Over the next few days I will look at my proposed changes and submit a PR of my own.

[grouptheoryenthusiast]

Making the change as I proposed above, all the tests seem to pass except for one.

gap> R := SmallRing(10,2);;
gap> randomTest(AdditiveCoset(R,5*R.1),Random);
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `IsFinite' on 1 arguments at /home/james/gap/lib/methsel2.g:250 called from
<compiled statement>  called from
Random( rs, AdditivelyActingDomain( A ) ) at /home/james/gap/lib/addcoset.gi:149 called from
func( GlobalMersenneTwister, x ) at /home/james/gap/lib/random.gi:301 called from
randfunc( collection ); at /home/james/gap/tst/testrandom.g:34 called from
randchecker( IsMersenneTwister, GlobalMersenneTwister, function ( x )
      return randfunc( x );
  end, randfunc, collection, checkin ); at /home/james/gap/tst/testrandom.g:144 called from
...  at *stdin*:102
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> ShowArguments();
[ <RandomSource in IsMersenneTwister> ]
brk> ShowDetails();
--------------------------------------------
Information about a `No method found'-error:
--------------------------------------------
Operation           : IsFinite
Number of Arguments : 1
Operation traced    : false
IsConstructor       : false
Choice              : 1st

Please can you advise what is happening here?
It seems to me that the problem is with IsFinite being called on a random source, but I am not sure why is a problem here and not with other tests which seem to pass fine, for instance:
gap> randomTest(AdditiveCoset(ZmodnZ(1),Identity(ZmodnZ(1))),Random);

Thanks for your time and guidance with this.

James

[fingolfin]

I think the error message might be misleading, and likewise the output of ShowArguments(). Or else something is missing in that output... What is the value of AdditivelyActingDomain( A ) in your example? Is it just the ring R? Does this produce a sensible result with your code: Random(GlobalMersenneTwister, SmallRing(10,2)); ? If yes, can you show us the method you installed to make it work?

It would be easier to say if your code was available somewhere -- perhaps you can put it into a PR right now, even with the problem above. Then it's much easier to locate the error (e.g. I can then run the example directly, and try to analyze it).

[ChrisJefferson]

This might be me misunderstanding how RedispatchOnCondition works :) If you could push your code somewhere, I will try it out.

[ChrisJefferson]

If you want to try a quick fix, I think line 270 of coll.gi has to be:

RedispatchOnCondition(Random,true,[IsRandomSource,IsCollection],[,IsFinite],0);

Notice the extra comma before IsFinite.

[fingolfin]

Ahhh, indeed :-)

A pity this was not noticed during code review :-(. I guess it's good that the upcoming tests by @grouptheoryenthusiast will ensure we test the redispatch.

If this fix works, I suggest @grouptheoryenthusiast just puts it into their upcoming PR

[grouptheoryenthusiast]

@fingolfin and @ChrisJefferson thank you for your replies.
The quick fix suggested by Chris did work.
I have put these things together in a small PR.