[GAP Forum] GAP behaviour for large integers

[Frank Lübeck]

On Tue, Mar 27, 2018 at 01:24:08PM +0000, Sanchez Garcia R. wrote:
> This is what I tried:
> #produce small generators
> mp := MovedPoints(gens);;
> l := Length(mp);;
> p := ();;
> for i in [1..l] do
> 	if mp[i] > l then
> 		p := p * (i,mp[i]);;
> 	fi; 
> od;
> gens := OnTuples(gens,p);;
> 
> Is there a more computationally efficient way of finding small generators?
> If anyone knows it’d be grateful.

Dear Ruben, dear Forum,

The reason for the inefficiency of your example lies in the data structure
for permutations used by GAP. Although a permutation is printed in cycle
notation it is not stored like that. A permutation pi is represented
internally as list of images
    [1^pi, 2^pi, ..., m^pi] 
where m is at least the LargestMovedPoint(pi).

So, already generating transpositions on two large integers, like

  gap> off := 10^8;;
  gap> gens := [(off,off+1),(off+1,off+2)]; time; MemoryUsage(gens[1]);
  [ (100000000,100000001), (100000001,100000002) ]
  4420
  400000036

takes considerable time and memory (400 MB plus some overhead for the object).

When you multiply two such elements

  gap> one := gens[1] * gens[1]; time;
  ()
  612

GAP is not aware that only few points are moved, this is not much faster
than multiplying arbitrary permutations on 10^8 points.
Furthermore, the product will be stored as image list on [1..the maximum of
the largest moved point of the factors] (so, GAP does not try to find out 
if the largest moved point of the result is smaller).

  gap> MemoryUsage(one);
  400000036

In many practical applications this strategy (and the data structure used by
GAP) is very efficient, but obviously not in the example discussed here.

My advise would be to find out the moved points before generating gens and
to define gens directly as permutations of small numbers.

Best regards,
  Frank

-- 
///  Dr. Frank Lübeck, Lehrstuhl D für Mathematik, Pontdriesch 14/16,
\\\                    52062 Aachen, Germany
///  E-mail: Frank.Luebeck at Math.RWTH-Aachen.De
\\\  WWW:    http://www.math.rwth-aachen.de/~Frank.Luebeck/