[GAP Forum] Intersection bug?

[Thomas Breuer]

Dear GAP Forum,

Matthew Fayers had reported a bug in the `Intersection' routine for ranges,
and several Forum members have meanwhile confirmed the erroneous behaviour.
Thank you for these reports.

Whereas it may depend on the operating system
whether this bug shows up or not,
we found meanwhile another error in the same routine,
which occurs on any operating system.

Both bugs can cause wrong results.
They will be fixed in the next version of GAP.

A preliminary fix can be obtained by reading the following GAP code
into the GAP session, for example in your .gaprc file.
(See the section ``The .gaprc file'' in the GAP Reference Manual for this.)

Sorry for the inconveniences.

All the best,
Thomas

----------------------------------------------------------------------------

InstallMethod( IntersectSet,
    "for two ranges (preliminary library method)",
    [ IsRange and IsRangeRep and IsMutable, IsRange and IsRangeRep ], 1,
    function( r1, r2 )
    local low1, low2, len1, len2, inc1, inc2, t, g, offset, inci, lowi,
          dist1, dist2, disti, leni;

    # Objects in `IsRangeRep' cannot be empty.
    low1:= r1[1];
    low2:= r2[1];
    len1:= Length( r1 );
    len2:= Length( r2 );
    inc1:= 1;
    if 1 < len1 then
      inc1:= r1[2] - r1[1];
    fi;
    inc2:= 1;
    if 1 < len2 then
      inc2:= r2[2] - r2[1];
    fi;

    # Force the two ranges to be ascending. (The result will be a set.)
    if inc1 < 0 then
      low1:= low1 + (len1-1)*inc1;
      inc1:= -inc1;
    fi;
    if inc2 < 0 then
      low2:= low2 + (len2-1)*inc2;
      inc2:= -inc2;
    fi;

    # Force the first range to start not later than the second.
    if low1 > low2 then
      t:= low1;
      low1:= low2;
      low2:= t;
      t:= inc1;
      inc1:= inc2;
      inc2:= t;
      t:= len1;
      len1:= len2;
      len2:= t;
    fi;

    if low2 > low1 + (len1-1)*inc1 then
      CLONE_OBJ( r1, [] );
      return;
    fi;

    # Now low1 <= low2 <= low1 + (len1-1)*inc1 holds.
    # Compute the step width of the intersection, and the first point.
    g:= Gcdex( inc1, inc2 );
    offset:= low2 - low1;
    if offset mod g.gcd <> 0 then
      CLONE_OBJ( r1, [] );
      return;
    fi;
    inci:= inc1 * inc2 / g.gcd;
    lowi:= low2 + ( ( - g.coeff2 * offset ) mod inc1 ) * inc2 / g.gcd;

    # Compute the length of the intersection.
    dist1:= low1 + (len1-1)*inc1 - lowi;
    dist2:= low2 + (len2-1)*inc2 - lowi;
    if dist1 < dist2 then
      disti:= dist1;
    else
      disti:= dist2;
    fi;
    if disti < 0 then
      CLONE_OBJ( r1, [] );
      return;
    fi;
    leni:= Int( disti / inci );

    CLONE_OBJ( r1, [ lowi, lowi + inci .. lowi + leni * inci ] );
  end );