[GAP Forum] GAP behaviour for large integers

[Max Horn]

Dear Ruben,

first a general remark: GAP represents a permutation pi internally as a list, which at position i has the value for i^pi. That means that the memory used to store a permutation scalers linearly with the largest point moved by it. If this is less than 2^16, then 2 bytes are used per point, else 4 bytes. You can see this here:

gap> MemoryUsage( (1,2) );
36
gap> MemoryUsage( (1,20000) );
40032
gap> MemoryUsage( (1,200000) );
800032

So the third transposition takes 800 kb RAM. If you square it, GAP has to read all that memory -- that alone of course already will be much smaller than reading the memory for the transposition (1,2). In addition, depending on how much memory your system has resp. you gave GAP, it has now to perform many more garbage collections to make room for these humongous permutations.

So, following Dima's good suggestion to relabel is key (while there has been some talk about adding a "sparse" permutation representation, this does not yet exist, and I also kind of would consider it a band aid; it's better to fix the underlying problem, i.e. avoid needless use of gigantic point values).

Now to your specific problem:


> On 27 Mar 2018, at 15:24, Sanchez Garcia R. <R.Sanchez-Garcia at soton.ac.uk> wrote:
> 
> Thank you Dmitrii.
> 
> I tried your suggestion but the replacement of generators takes at least as long as computing the orbits in the original permutation group (code below). 
> 
> Listing all the integers before the permutation won’t help either, as most integers 1 to n appear at least once. 

That sentence confuses me. Your originally question sounded as if the set of moved points for your permutation groups was small; this sentence now sounds as if it was not (and in that case, things are hopeless).


> 
> 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);;

Don't do that! Remap the permutations directly:

gap> gens:=[(10000,20000),(30000,40000)];
gap> mp := MovedPoints(gens);;
gap> smallgens:=List(gens, g -> Permutation(g, mp));
[ (1,2), (3,4) ]

# perform orbit computation
gap> small_orbs:=Orbits(Group(smallgens));
[ [ 1, 2 ], [ 3, 4 ] ]

# map back to the original numbers
gap> orbs:=List(small_orbs, o->mp{o});
[ [ 10000, 20000 ], [ 30000, 40000 ] ]



Hope that helps,
Max