[GAP Forum] Intersection bug?
Thomas Breuer
thomas.breuer at math.rwth-aachen.de
Mon Jul 21 15:41:57 BST 2008
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 );
More information about the Forum
mailing list