gap-packages / guava Goto Github PK

View Code? Open in Web Editor NEW

11.0 11.0 6.0 74.02 MB

GAP package guava - computations relative to error-correcting codes

Home Page: https://gap-packages.github.io/guava

License: Other

TeX 3.47% C 23.81% Shell 0.02% GAP 71.53% Makefile 1.16% M4 0.01%

guava's People

Contributors

Stargazers

Watchers

Forkers

dimpase olexandr-konovalov jgmbenoit markuspf esabo smtsjhr

guava's Issues

No way to turn off information printout in MinimumWeight (guava package)

Usually packages provide a way to turn off printing of information for eample using SetInfoLevel .
The guava package has a function "MinimumWeight" where there's no way to do that.
(Note the function works; just the extra information being printed is not needed; it clutters the screen and slows things down)

Observed behaviour

code:=BestKnownLinearCode(7,4,GF(2));;
mat:=GeneratorMat(code);;
dmin:=MinimumWeight(GeneratorMatCode(mat,"",GF(2)));;

[ "--out", "C:/WINDOWS/Temp/gaptempfile.27oHNm", "--mod", 2, "C:/WINDOWS/Temp/gaptempfile.qIzGoV" ]
[7,4] linear code over GF(2) - minimum weight evaluation
Known lower-bound: 1
There are 2 generator matrices, ranks : 4 3
The weight of the minimum weight codeword satisfies 1 mod 2 congruence
Enumerating codewords with information weight 1 (w=1)
Found new minimum weight 3
Number of matrices required for codeword enumeration 2
Completed w= 1, 8 codewords enumerated, lower-bound 3, upper-bound 3

Expected behaviour

code:=BestKnownLinearCode(7,4,GF(2));;
mat:=GeneratorMat(code);;
dmin:=MinimumWeight(GeneratorMatCode(mat,"",GF(2)));;
(nothing printed out)

Copy and paste GAP banner (to tell us about your setup)

┌───────┐ GAP 4.11.0 of 29-Feb-2020
│ GAP │ https://www.gap-system.org/
└───────┘ Architecture: x86_64-pc-cygwin-default64-kv7
Configuration: gmp 6.1.2, GASMAN, readline
Loading the library and packages ...
Packages: AClib 1.3.2, Alnuth 3.1.2, AtlasRep 2.1.0, AutoDoc 2019.09.04, AutPGrp 1.10.2, Browse 1.8.8,
CaratInterface 2.3.3, CRISP 1.4.5, Cryst 4.1.23, CrystCat 1.1.9, CTblLib 1.2.2, FactInt 1.6.3, FGA 1.4.0,
Forms 1.2.5, GAPDoc 1.6.3, genss 1.6.6, IO 4.7.0, IRREDSOL 1.4, LAGUNA 3.9.3, orb 4.8.3, Polenta 1.3.9,
Polycyclic 2.15.1, PrimGrp 3.4.0, RadiRoot 2.8, recog 1.3.2, ResClasses 4.7.2, SmallGrp 1.4.1,
Sophus 1.24, SpinSym 1.5.2, TomLib 1.2.9, TransGrp 2.0.5, utils 0.69
Try '??help' for help. See also '?copyright', '?cite' and '?authors'

Setup CI for Windows and macOS ?

Max Horn points out that Travis can be configured to test on MacOS and Windows as well as Linux

QCLDPCCodeFromGroup error (from gap-forum)

Date: Fri, 12 Aug 2016 05:52:33 +0000 (UTC)
From: "R.N. Tsai" [email protected]
as reported there:

To: GAP Forum [email protected]
Subject: [GAP Forum] Error using guava function QCLDPCCodeFromGroup

Dear Forum,
I tried to use the QCLDPCCodeFromGroup defined in the guava package :I used the example given in the documentation :

LoadPackage("guava","0",false);
C:=QCLDPCCodeFromGroup(7,2,3);

I get this error :
Error, no method found! For debugging hints type ?Recovery from NoMethodFoundError, no 1st choice method found for `QCLDPCCodeFromGroup' on 3 arguments called from<function "HANDLE_METHOD_NOT_FOUND">(
+)
?QCLDPCCodeFromGroup returns the expected information about it, so it seems that gapknows about the function and I do load the guava package.
I'm using this version of GAP under windows.GAP 4.8.3, 19-Mar-2016, build of 2016-03-20 23:48:47 (GMTST)
I got the same error with win32 and win64 versions and under linux.
Thanks for your help,R.N.

Forum mailing list
[email protected]
http://mail.gap-system.org/mailman/listinfo/forum

Obsoletes in GUAVA

If one starts GAP with -O option, this shows that GUAVA uses many obsolete names - please see http://www.gap-system.org/Manuals/doc/ref/chap77.html on how to replace them.

===========================================
%%% Loading guava 3.12
#I  You may wish to install the xgap package
#I  and enjoy the graphic capabilities of SONATA.
Syntax warning: Unbound global variable in /home/hudson/hudson/workspace/GAP-p\
kg-update-master-quicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/obsoletes/lab\
el/graupius/GAP-pkg-update-master-snapshot/pkg/guava-3.12/lib/codegen.gi line \
1042
    temp := MutableNullMat(n, n, F);
                          ^
Syntax warning: Unbound global variable in /home/hudson/hudson/workspace/GAP-p\
kg-update-master-quicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/obsoletes/lab\
el/graupius/GAP-pkg-update-master-snapshot/pkg/guava-3.12/lib/matrices.gi line\
 24
    res := MutableNullMat(n+1,n+1);
                         ^
Syntax warning: Unbound global variable in /home/hudson/hudson/workspace/GAP-p\
kg-update-master-quicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/obsoletes/lab\
el/graupius/GAP-pkg-update-master-snapshot/pkg/guava-3.12/lib/matrices.gi line\
 60
    result := MutableNullMat(M,n);
                            ^
Syntax warning: Unbound global variable in /home/hudson/hudson/workspace/GAP-p\
kg-update-master-quicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/obsoletes/lab\
el/graupius/GAP-pkg-update-master-snapshot/pkg/guava-3.12/lib/matrices.gi line\
 176
        result := List(MutableNullMat(n,n)+1, x->ShallowCopy(x));
                                     ^
Syntax warning: Unbound global variable in /home/hudson/hudson/workspace/GAP-p\
kg-update-master-quicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/obsoletes/lab\
el/graupius/GAP-pkg-update-master-snapshot/pkg/guava-3.12/lib/matrices.gi line\
 301
        res := MutableNullMat(q,q)+1;
                             ^
Syntax warning: Unbound global variable in /home/hudson/hudson/workspace/GAP-p\
kg-update-master-quicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/obsoletes/lab\
el/graupius/GAP-pkg-update-master-snapshot/pkg/guava-3.12/lib/matrices.gi line\
 315
        res:=List([1..n], x-> MutableNullMat(q,q,GF(q)));
                                            ^
Syntax warning: Unbound global variable in /home/hudson/hudson/workspace/GAP-p\
kg-update-master-quicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/obsoletes/lab\
el/graupius/GAP-pkg-update-master-snapshot/pkg/guava-3.12/lib/matrices.gi line\
 401
    res := MutableNullMat(r * m, n, Fq);
                         ^
Syntax warning: Unbound global variable in /home/hudson/hudson/workspace/GAP-p\
kg-update-master-quicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/obsoletes/lab\
el/graupius/GAP-pkg-update-master-snapshot/pkg/guava-3.12/lib/bounds.gi line 5\
24
                    ReadPkg( "guava",  
                           ^
Syntax warning: Unbound global variable in /home/hudson/hudson/workspace/GAP-p\
kg-update-master-quicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/obsoletes/lab\
el/graupius/GAP-pkg-update-master-snapshot/pkg/guava-3.12/lib/bounds.gi line 6\
76
        ReadPkg( "guava", "tbl/refs.g" );
               ^
Syntax warning: Unbound global variable in /home/hudson/hudson/workspace/GAP-p\
kg-update-master-quicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/obsoletes/lab\
el/graupius/GAP-pkg-update-master-snapshot/pkg/guava-3.12/lib/bounds.gi line 6\
97
        ReadPkg( "guava", Concatenation( "tbl/bdtable", String(q), ".g" ) );
               ^
Syntax warning: Unbound global variable in /home/hudson/hudson/workspace/GAP-p\
kg-update-master-quicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/obsoletes/lab\
el/graupius/GAP-pkg-update-master-snapshot/pkg/guava-3.12/lib/codecstr.gi line\
 576
    checkmat := MutableNullMat( 5 * 2^(m-2) - 1, 2 * m - 1, GF( 2 ) );
                              ^
Syntax warning: Unbound global variable in /home/hudson/hudson/workspace/GAP-p\
kg-update-master-quicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/obsoletes/lab\
el/graupius/GAP-pkg-update-master-snapshot/pkg/guava-3.12/lib/codecstr.gi line\
 714
    checkmat := MutableNullMat( 7 * 2^(m-2) - 2, 2 * m, GF( 2 ) );
                              ^
Syntax warning: Unbound global variable in /home/hudson/hudson/workspace/GAP-p\
kg-update-master-quicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/obsoletes/lab\
el/graupius/GAP-pkg-update-master-snapshot/pkg/guava-3.12/lib/codecstr.gi line\
 787
    checkmat := MutableNullMat( 2^v + 2^(r-v) - 3, r, GF( 2 ) );
                              ^
Syntax warning: Unbound global variable in /home/hudson/hudson/workspace/GAP-p\
kg-update-master-quicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/obsoletes/lab\
el/graupius/GAP-pkg-update-master-snapshot/pkg/guava-3.12/lib/codecstr.gi line\
 891
    checkmat := MutableNullMat( 15 * 2^(m-3) - 3, 2*m, GF( 2 ) );
                              ^
Syntax warning: Unbound global variable in /home/hudson/hudson/workspace/GAP-p\
kg-update-master-quicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/obsoletes/lab\
el/graupius/GAP-pkg-update-master-snapshot/pkg/guava-3.12/lib/codecstr.gi line\
 945
    theta := MutableNullMat( 4*size - 1, 2 * (m-3) + 2, GF( 2 ) );
                           ^
Syntax warning: Unbound global variable in /home/hudson/hudson/workspace/GAP-p\
kg-update-master-quicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/obsoletes/lab\
el/graupius/GAP-pkg-update-master-snapshot/pkg/guava-3.12/lib/codecstr.gi line\
 1085
    checkmat := MutableNullMat( 23 * 2^(m-4) - 3, 2 * m - 1, GF( 2 ) );
                              ^
Syntax warning: Unbound global variable in /home/hudson/hudson/workspace/GAP-p\
kg-update-master-quicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/obsoletes/lab\
el/graupius/GAP-pkg-update-master-snapshot/pkg/guava-3.12/lib/tblgener.gi line\
 100
            initialfile := Filename(LOADED_PACKAGES.guava, 
                                                   ^
Syntax warning: Unbound global variable in /home/hudson/hudson/workspace/GAP-p\
kg-update-master-quicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/obsoletes/lab\
el/graupius/GAP-pkg-update-master-snapshot/pkg/guava-3.12/lib/tblgener.gi line\
 104
            initialfile := Filename(LOADED_PACKAGES.guava, 
                                                   ^
Syntax warning: Unbound global variable in /home/hudson/hudson/workspace/GAP-p\
kg-update-master-quicktest/GAPCOPTS/64build/GAPGMP/gmp/GAPTARGET/obsoletes/lab\
el/graupius/GAP-pkg-update-master-snapshot/pkg/guava-3.12/lib/tblgener.gi line\
 419
    file := Filename(LOADED_PACKAGES.guava,
                                    ^
[ "NRI", "bit_flip", "checksetI", "checksetJ", "expmulnr_gd", "expmulnrnr_gi",
  "grptfms_gd", "grptfms_gi", "guava_version", "libnr_gi", "nr_gd", "nr_gi" ]
### Loaded guava 3.12
===========================================

Make a new release

... with the changes that accumulated (at least one bug fix, and the new License field).

PermutationGroup(C) deprecated

The function PermutationGroup() (with a code argument) computes the automorphism group of the code in GAP without using Leon's C programs. This form has been deprecated for a while. The new name
is PermutationAutomorphismGroup(). Is it time to delete the old form?

I/O streams for comm with external programs

Is there a significant speed-up to be had by talking to Leon's and Ctjhai's code via streams rather than using the file system for i/o?

Merge README.guava and README.md

When visiting this repository one is shown the almost empty README.md. I would suggest to delete the current README.md, then rename README.guava to either just README, or else convert it to proper Markdown and rename it to README.md.

In either case, README_URL in PackageInfo.g will need to be adjusted to match the new name, too.

possible bug in PutStandardForm

It looks like PutStandardForm(M,true) has a problem. This would transform a matrix M to a form {I|P}; "true" is the default for the second
argument. PutStandardFrom(M,false) is ok; this puts M into a form {P|I}. Both options used to work in older versions of gap/guava (a year or two ago...didn't keep track of when exactly this was broken).

┌───────┐ GAP 4.12.0 of 2022-08-18
│ GAP │ https://www.gap-system.org
└───────┘ Architecture: x86_64-pc-cygwin-default64-kv8
Configuration: gmp 6.2.1, GASMAN, readline
Loading the library and packages ...
Packages: AClib 1.3.2, Alnuth 3.2.1, AtlasRep 2.1.4, AutoDoc 2022.07.10, AutPGrp 1.11, Browse 1.8.14,
CaratInterface 2.3.4, CRISP 1.4.5, Cryst 4.1.25, CrystCat 1.1.10, CTblLib 1.3.4, FactInt 1.6.3,
FGA 1.4.0, Forms 1.2.8, GAPDoc 1.6.6, genss 1.6.7, IO 4.7.2, IRREDSOL 1.4.3, LAGUNA 3.9.5, orb 4.8.5,
Polenta 1.3.10, Polycyclic 2.16, PrimGrp 3.4.2, RadiRoot 2.9, recog 1.3.2, ResClasses 4.7.3,
SmallGrp 1.5, Sophus 1.27, SpinSym 1.5.2, TomLib 1.2.9, TransGrp 3.6.3, utils 0.76
Try '??help' for help. See also '?copyright', '?cite' and '?authors'

gap> LoadPackage("guava");
#I You may wish to install the xgap package
#I and enjoy the graphic capabilities of SONATA.

/ ___
|| / \ /\ Version 2.9.4
|| || || |\ | / \ /\ Erhard Aichinger
___ || || |\ | /___/\ Franz Binder
\ || || | \ | / \ || / \ Juergen Ecker
|| _/ | \ | / \ || / \ Peter Mayr
|| | \| / \ || Christof Noebauer
_/ | | ||

System Of Nearrings And Their Applications
Info: https://gap-packages.github.io/sonata/

____ |
/ \ / --+-- Version 3.16
/ | | |\ //| |
| _ | | | \ // | the GUAVA Group
| \ | | |--\ //--|
\ || | | \ // |
_/ _/ | \// |

true

gap> M:=[List([1..6],x->1)*Z(2)];
[ [ Z(2)^0, Z(2)^0, Z(2)^0, Z(2)^0, Z(2)^0, Z(2)^0 ] ]

#this works
gap> PutStandardForm(M,false);
()

#this doesn't
gap> PutStandardForm(M,true);
Error, Function Calls: must return a value in
TriangulizeMat( mat ) at /opt/gap-4.12.0/.libs/../pkg/guava/lib/matrices.gi:640 called from
PutStandardForm( Mat, F ) at /opt/gap-4.12.0/.libs/../pkg/guava/lib/matrices.gi:592 called from
PutStandardForm( M, idleft, DefaultField( Flat( M ) ) ) at /opt/gap-4.12.0/.libs/../pkg/guava/lib/matrices.gi:660 called from
<function "PutStandardForm method for matrix and idleft">( )
called from read-eval loop at stdin:6
type 'quit;' to quit to outer loop
brk> quit;

BCH decoding

see email from Alex K

Randomization related test failures

some of the tests in guava.tst use randomized inputs. The expected outputs can't necessarily be compared to previous results.

GeneralizedReedSolomonCode decoding is broken

gap> R:=PolynomialRing(GF(11),["t"]);
GF(11)[t]
gap> P:=List([1,3,4,5,7],i->Z(11)^i);
[ Z(11), Z(11)^3, Z(11)^4, Z(11)^5, Z(11)^7 ]
gap> C:=GeneralizedReedSolomonCode(P,3,R);
a linear [5,3,1..3]2  generalized Reed-Solomon code over GF(11)
gap> c := Random(C);
[ 5 4 5 4 2 ]
gap> i := InformationWord(C, c);
[ 2 1 3 ]
gap> Decode(C,c);  
[ 2 1 3 ]
gap> e := ErrorVector(Random([1..WordLength(C)]), C);
[ 0 0 0 1 0 ]
gap> r:=c+e;
[ 5 4 5 5 2 ]
gap> Decode(C,r);  
Error, ERROR: codeword must belong to code called from
InformationWord( C, SpecialDecoder( C )( C, c )
 ) at /usr/local/lib/gap4r8/pkg/guava/lib/decoders.gi:70 called from
<function "unknown">( <arguments> )
 called from read-eval loop at line 123 of *stdin*
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk>

Guava build fails on Mac

For version 3.15 I have

cc  -O2 -c   ./src/generate.c 
./src/generate.c:425:10: error: implicit declaration of function 'RmvRSG' is
      invalid in C99 [-Werror,-Wimplicit-function-declaration]
         removeRedunSGens( G, 1);
         ^
./src/extname.h:224:37: note: expanded from macro 'removeRedunSGens'
#define removeRedunSGens            RmvRSG
                                    ^
./src/generate.c:437:7: error: implicit declaration of function 'InfGrp' is
      invalid in C99 [-Werror,-Wimplicit-function-declaration]
      informGroup(G);
      ^
./src/extname.h:113:37: note: expanded from macro 'informGroup'
#define informGroup                 InfGrp
                                    ^
2 errors generated.
make[1]: *** [generate.o] Error 1
make: *** [desauto] Error 2

This is what gcc --version says:

Configured with: --prefix=/Library/Developer/CommandLineTools/usr --with-gxx-include-dir=/Library/Developer/CommandLineTools/SDKs/MacOSX10.15.sdk/usr/include/c++/4.2.1
Apple clang version 12.0.0 (clang-1200.0.32.29)
Target: x86_64-apple-darwin19.6.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin

src/wtdist.c:177: bad test

src/wtdist.c:177]: (warning) Logical conjunction always evaluates to false: EXPR < 1 && EXPR > 3.

Source code is

if ( argc - optionCountPlus1 < 1 && argc - optionCountPlus1 > 3 ) {

Suggest new code

if ( argc - optionCountPlus1 < 1 || argc - optionCountPlus1 > 3 ) {

CirculantMatrix and NegacirculantMatrix output behavior

Hi,

I am observing the below behavior in latest Guava library

gap>k:=3;L:=[1,2,3];;
gap>M:=CirculHantMatrix(k,L);;
gap>Display(M);
[ [1, 2, 3],
[2, 3, 1],
[3, 1, 2]]

gap>M:=NegacirculantMatrix(k,L);;
gap>Display(M);
[ [1, 2, 3],
[-3, 1, 2],
[-2, -3, 1]]

The definition of Negacirculantmatrix is as usual but the definition of Circulant Matrix is different from standard definition.

Please elaborate on this.

Any way to get the usual circulant?

Fix tests

https://travis-ci.org/gap-packages/guava/jobs/573983681 shows that tests fail because of the mismatch between double semicolon and displayed output - please adjust the test as you see appropriate.

Switching to releaseTools and releasing GUAVA 3.14

ReleaseTools for GAP packages by @fingolfin is a set of tools to help to release GAP packages hosted on GitHub. @osj1961 would you be interested in using it?

stale links in manual to old osj1961.github.io/guava site

Package banner should give information on how to contact / report issues

Loading Guava gives this banner:

   ____                          |
  /            \           /   --+--  Version 3.16
 /      |    | |\\        //|    |
|    _  |    | | \\      // |     the GUAVA Group
|     \ |    | |--\\    //--|
 \     ||    | |   \\  //   |
  \___/  \___/ |    \\//    |

Which looks nice, but sadly has very little information -- in particular, no information at all how to reach "the GUAVA Group", how to report issues, how to learn more about the package.

In contrast, this is what the default package banner would look like for Guava:

Loading  GUAVA 3.16 (GUAVA Coding Theory Package)
by Reinald Baart,
   Tom Boothby,
   Jasper Cramwinckel,
   Joe Fields (http://giam.southernct.edu/),
   David Joyner (https://sites.google.com/site/wdjoyner/),
   Robert Miller,
   Eric Minkes,
   Erik Roijackers,
   Lea Ruscio, and
   Cen Tjhai.
maintained by:
   Joe Fields (http://giam.southernct.edu/).
Homepage: https://gap-packages.github.io/guava
Report issues at https://github.com/gap-packages/guava/issues

Now I am not saying you should drop your custom banner; just that perhaps some more infromation (like the last two lines of the default banner?) would be useful...

PutStandardForm does not work as expected

I am using GAP 4.11.0 and GUAVA 3.15 (as distributed with GAP 4.11.0)

The function PutStandardForm does not work as expected.
Even the examples in the manual cannot be reproduced. When I tried, I got the following:

gap> M := Z(2)*[[1,0,0,1],[0,0,1,1]];; PrintArray(M);
[ [  Z(2)^0,  0*Z(2),  0*Z(2),  Z(2)^0 ],
  [  0*Z(2),  0*Z(2),  Z(2)^0,  Z(2)^0 ] ]
gap> PutStandardForm(M);
(2,3)
gap> PrintArray(M);
[ [  Z(2)^0,  0*Z(2),  0*Z(2),  Z(2)^0 ],
  [  0*Z(2),  0*Z(2),  Z(2)^0,  Z(2)^0 ] ]
gap> PutStandardForm(M, false);
()
gap> PrintArray(M);
[ [  Z(2)^0,  0*Z(2),  Z(2)^0,  0*Z(2) ],
  [  Z(2)^0,  0*Z(2),  0*Z(2),  Z(2)^0 ] ]
gap> C := BestKnownLinearCode( 23, 12, GF(2) );
a linear [23,12,7]3 punctured code
gap> G:=MutableCopyMat(GeneratorMat(C));;
gap> PutStandardForm(G);
()
gap> Display(G);
 . 1 . 1 1 1 . . . 1 1 . . . . . . . . . . . 1
 1 . 1 . 1 1 1 . . . 1 1 . . . . . . . . . . 1
 . . . . 1 . 1 1 . 1 1 1 1 . . . . . . . . . .
 . . 1 . . . . . 1 1 1 1 . 1 . . . . . . . . 1
 . . . 1 . 1 . 1 1 1 . . . 1 1 . . . . . . . 1
 . . . . . . . 1 1 . . 1 1 . 1 1 . . . . . . 1
 . . . . . 1 . . 1 1 1 . 1 . 1 . 1 . . . . . .
 . . . . . . 1 . 1 . 1 1 1 . . . 1 1 . . . . 1
 . . . . . . . . 1 1 . . . 1 1 1 . 1 1 . . . .
 . . . . . . . . . 1 1 . 1 . . 1 . 1 . 1 . . 1
 . . . . . . . . . . 1 1 1 1 1 . . 1 . . 1 . .
 . . . . . . . . . . . 1 . 1 . 1 1 1 . . . 1 1
gap>

Missing `CoefficientMultivariatePolynomial`

The manual has a section describing a function CoefficientMultivariatePolynomial which is also referenced in some examples.

But no such function is ever defined.

HadamardMat improvements

There is a paper, DISCOVERY OF AN HADAMARD MATRIX OF ORDER 92 by LEONARD BAUMERT, S. W. GOLOMB AND MARSHALL HALL, JR. describing a construction using a 4x4 block form

[  A  B  C  D ]
[ -B  A -D  C ]
[ -C  D  A -B ]
[ -D -C  B  A ]

where A,B,C & D are 23x23 (symmetric) circulant matrices.

They claim the method can be generalized to cover 92, 116, 156, and 188 (also 172 which was originally done by J. Williamson using "a special automorphism of order 3") The amount of computation involved was apparently prohibitive in 1961. The technique may have to do with finding multiple difference sets in
GF(m/4).

HadamardMat

According to MathWorld:

The values of n for which there are no Paley classes (and hence cannot be constructed using a Paley construction) are 92, 116, 156, 172, 184, 188, 232, 236, 260, 268, ...

But the HadamardMat function in GUAVA gives errors at n=52 and 100 (and probably others as well).

Version needs to be incremented again, otherwise this package won't be picked up

Hi there,

to quote a report by @alex-konovalov :

Package: GUAVA
changed components: [ "Dependencies", "PackageWWWHome", "ArchiveURL", "README_URL", "PackageInfoURL" ]
ERROR (GUAVA): There are changed components in the new info file from
http://www.southernct.edu/~fields/Guava/PackageInfo.g
but .Version remains the same. This is not allowed, so the info file will not be changed
PackageInfo.g is not accepted because of an error.

It seems you modified the PackageInfo.g at http://www.southernct.edu/~fields/Guava/PackageInfo.g without changing the version number in it. That is not allowed by the system (after all, you now assigned the same version to two clearly different things).

'cd leon make' in top Makefile

This is of course a typo. It is meant to be cd leon; make or even better cd leon && ./configure && $(MAKE). It is important that ./configure is invoked before make, as the Makefile must be generated.

While make -j1 would have Makefile ready (made in another target), it need not be the case for make -j10 or something like this.

See more here: https://trac.sagemath.org/ticket/22116

BestKnownLinearCode broken

BestKnownLinearCode(24,12,2); returns
a linear [24,12,6]4..8 U|U+V construction code
which is clearly inferior to the extended Golay code

code tables

Brouwer's online table of bounds for codes is defunct. It has been supplanted by
a new site by Markus Grassl ([email protected]), -- http://www.codetables.de/

Dangling "else" warnings in Leon's code

There are a lot of compiler warnings (mostly dangling else) that should be cleaned-up.
Need to first create a test suite for the functions in Leon's backtracking lib so that any inadvertent changes that effect functionality will get caught.

Build with -Werror=return-type

When -Werror=return-type is used, the following problem spots are identified:

cc  -Werror=return-type -O2 -c   ./src/cuprstab.c 
./src/cuprstab.c: In function ‘uPartnStabRefine’:
./src/cuprstab.c:304:1: error: no return statement in function returning non-void [-Werror=return-type]
  304 | }
      | ^
./src/cuprstab.c: In function ‘PaStbR’:
./src/cuprstab.c:495:1: error: no return statement in function returning non-void [-Werror=return-type]
  495 | }
      | ^
./src/cuprstab.c: In function ‘UprStb’:
./src/cuprstab.c:128:1: error: control reaches end of non-void function [-Werror=return-type]
  128 | }
      | ^
./src/cuprstab.c: In function ‘UPrImg’:
./src/cuprstab.c:186:1: error: control reaches end of non-void function [-Werror=return-type]
  186 | }
      | ^

WriteToFile does not do what it name suggests

In tblgener.gi, you can find this code snippet around line 420:

    ##LR - This trick is not yet working in GAP4.  Until it does, 
        ##  the tables will not be printed to the file.  
    if info then Print("\nSaving the bound tables...\n"); fi;
    #file := Filename(LOADED_PACKAGES.guava,
    #                    Concatenation("tbl/bdtable",String(q),".g") );
    # The LOADED_PACKAGES record is now defunct.  The following was suggested by Alex Konovalov. --JEF (1/18/2016)
    file := Filename( DirectoriesPackageLibrary("guava", "tbl"),
                         Concatenation("bdtable",String(q),".g") );
    PrintTo(file, "#A  BOUNDS FOR q = ", String(q), help,
            "\n\nGUAVA_BOUNDS_TABLE[1", WriteToFile(LBT),
            "\n\nGUAVA_BOUNDS_TABLE[2", WriteToFile(UBT) );

I am not quite sure which "trick" the first comment refers to. But what I can confirm is that this code won't print much to the given file -- indeed, I would suspect that it would run into an error, because WriteToFile returns nothing, yet its (non-existant) return value is passed to PrintTo.

Anyway, my guess is that the speed problem refered to using PrintTo(filename, ...) repeatedly, which is indeed very slow: Each such call opens the file, appends a line to it, then closes it again. That causes significant overhead.

If you want to fix this, you could open a stream, print to that, and finally close it, as in this example:

stream := OutputTextFile( name, true );
SetPrintFormattingStatus( stream, false ); # disable automatic line breaks
PrintTo( stream, "Hallo\n", "You\n" );
CloseStream(stream);

Then, change WriteToFile to take the stream as a parameter, and change its Print calls to PrintTo(stream, ...).

bug in Decodeword for a linear code over GF(4)

Consider the following, run on GAP 4.7.7, and latest Guava installed:

   M:=[ [ Z(2)^0, 0*Z(2), 0*Z(2), Z(2^2)^2, Z(2^2) ],
           [ 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0, Z(2)^0 ],
           [ 0*Z(2), 0*Z(2), Z(2)^0, Z(2^2), Z(2^2)^2 ] ];
   C:=GeneratorMatCode(M,GF(4));
   v:=[ Z(2)^0, 0*Z(2), 0*Z(2), Z(2^2), Z(2)^0 ];

Then one gets

   gap> Decodeword(C,Codeword(v));
   Error, List Element: <list>[2] must have an assigned value in
           repeat
              index := index + 1;
           until S[index][2] = syn; 
   called from <function "unknown">( <arguments> )
   called from read-eval loop at line 65 of *stdin*
   you can 'return;' after assigning a value
   brk>

(Inspecting S at the breakpoint reveals a list with gaps, in particular the position 2 is empty.)

This used to work with older Guava/GAP versions.

archiving

The archive of previous versions must be added to the gh-pages website

Makefile should not hardcode gcc as the compiler

Note every system has gcc; e.g. OSX "gcc" is actually not gcc, it's some other compiler, clang.
./configure should figure out whether CC should be cc, gcc...

FreeBSD has switched to clang as the default compiler, and does not have gcc (it can be installed, but, well, it's natural to build GAP and the packages with the default compiler, for various reasons)

some remarks on `\in` for codewords in codes

When dealing with gap-system/gap/issues/5334 (where test code from the guava package helped to fix a bug in GAP), I noticed a few problems with related code in the file lib/codeops.gi of the guava package.

There are \in methods that take a list of codewords or a code as the first argument (see the ApplicableMethod output shown below). The correct GAP operation for expressing this relation would be IsSubset (with reversed argument ordering). Note that methods installed with requirement IsList for the first argument are applicable also in the situation where the first argument is a codeword, and these methods return false in this case; in these situations, these methods do not cause problems only because other methods have higher ranks. I think it is confusing to "misuse" the operation \in for IsSubset questions.
The \in methods for an object in IsCodeword and a code with certain properties (IsCode, IsLinearCode) have lower rank than more general methods for a vector and a vector space, but the methods for IsCodeword seem to be more efficient. It would make sense to "rank up" these methods. Here is an example in GAP 4.12.2.

gap> V:= WholeSpaceCode( 5, GF(2) );;
gap> v:= GeneratorsOfVectorSpace( V )[1];;
gap> meth:= ApplicableMethod( \in, [ v, V ], 1, "all" );;
#I  Searching Method for in with 2 arguments:
#I  Total: 117 entries
#I  Method 65: ``in: for vector and free left module that is handled by a nice basis'' at /.../lib/basis.gi:1258 , value: 33
#I  Skipped:
#I  Method 66: ``in: for vector and fin. dim. free left module'' at /.../lib/modfree.gi:83 , value: 32
#I  Skipped:
#I  Method 69: ``in: method for codeword in cyclic code'' at /.../pkg/guava/lib/codeops.gi:1435 , value: 25
#I  Skipped:
#I  Method 73: ``in: method for codeword in linear code'' at /.../pkg/guava/lib/codeops.gi:1413 , value: 23
#I  Skipped:
#I  Method 80: ``in: method for codeword in unrestricted code'' at /.../pkg/guava/lib/codeops.gi:1389 , value: 17
#I  Skipped:
#I  Method 101: ``in: method for list of codewords in unrestricted code'' at /.../pkg/guava/lib/codeops.gi:1399 , value: 6
#I  Skipped:
#I  Method 107: ``in: for a domain, and an element'' at /.../lib/domain.gi:280 , value: 5
#I  Skipped:
gap> V:= WholeSpaceCode( 5, GF(2) );;
gap> v:= GeneratorsOfVectorSpace( V )[1];;
gap> i:= 4;; for x in [ 1 .. 10000 ] do meth[i]( v, V ); od; time;
33
gap> i:= 1;; for x in [ 1 .. 10000 ] do meth[i]( v, V ); od; time;
115

Potential Integer Overflow vulnerability in src/ctjhai/minimum-weight.c

Hi,
It seems that there exists a potential integer overflow. Please find the following description:

M->cols can be an arbitrary large number

guava/src/ctjhai/minimum-weight.c

Line 147 in 685d1d5

if ( fscanf(fptr, "%d %d %d\n", &M->rows, &M->cols, &M->q) < 0 ) {
Call to malloc with the large integer can cause a memory allocation with an overflowed size

guava/src/ctjhai/minimum-weight.c

Line 152 in 685d1d5

M->m[i] = (unsigned int *)malloc(M->cols * sizeof(unsigned int));

Minimum distance for long codes over GF(2) or GF(3) is incorrect

Guava's code for computing minimum distance of codes over GF(2) or GF(3) is broken when the code's block length is larger than 2**16. This happens because in the C code short type is used in many places (all the C code is in the folder src/ctjhai/). For example, see src/ctjhai/types.h.

I suggest to use unsigned long everywhere (maybe just the MATRIX struct should use unsigned char to save some memory, since only GF(2) and GF(3) are supported). Such replacement would also require appropriate changes in format strings. Moreover, many ints should be replaced too, as I think it's possible that larger codes are also analyzed, i.e. with length greater than 2**32. But I don't know if Guava itself can hold such large codes.

I can make a pull request with type changes if it's agreed.

Also there should be a check somewhere whether the block length is higher than possible to hold in the current architecture's word. Otherwise, an error should be thrown.

I arrived at this bug when using it from SageMath. See the following simple example, where the minimum distance is clearly 2, but Guava returns 0. Similar error happens on almost any other code with large block length.

from sage.all import *

G = matrix(GF(2), [
    [1]*2**16 + [1, 0, 0],
    [1]*2**16 + [0, 1, 0],
    [1]*2**16 + [0, 0, 1],
])
dist = min(sum(map(int, v)) for v in G.row_space() if v)
dist_guava = LinearCode(G).minimum_distance(algorithm="guava")
print "real minimum distance: %d, guava: %d" % (dist, dist_guava)

# real minimum distance: 2, guava: 0

For completeness, here are versions that I use:

SageMath version 8.7, Release Date: 2019-03-23 │Using Python 2.7.15
GAP 4.10.0 of 01-Nov-2018
Architecture: x86_64-pc-linux-gnu-default64
GUAVA Version 3.14

Small problem compiling in Fedora 26

I got an error when compiling the package; adding a ";" at the end of line 178 of src/leon/src/wtdist.c solves the issue

Some problematic compiler warnings in leon/

cd src/leon; CFLAGS="-O2 -Wall -Werror=return-type" make
./src/cuprstab.c: In function ‘uPartnStabRefine’:
./src/cuprstab.c:304:1: error: no return statement in function returning non-void [-Werror=return-type]
  304 | }
      | ^
./src/cuprstab.c: In function ‘PaStbR’:
./src/cuprstab.c:495:1: error: no return statement in function returning non-void [-Werror=return-type]
  495 | }
./src/cuprstab.c: In function ‘UprStb’:
./src/cuprstab.c:128:1: error: control reaches end of non-void function [-Werror=return-type]
  128 | }
      | ^
./src/cuprstab.c: In function ‘UPrImg’:
./src/cuprstab.c:186:1: error: control reaches end of non-void function [-Werror=return-type]
  186 | }

Decoding test failure in 3.13.1

I built the 3.13.1 release on an x86_64 machine running Linux, specifically Fedora 24. One decoding test sometimes fails, in two different ways. I've manage to catch both failure types while running the test manually:

gap> x:= Indeterminate( GF(2) );
x_1
gap> P:= x^3+x^2+1;
x_1^3+x_1^2+Z(2)^0
gap> C := GeneratorPolCode(P, 7, GF(2));
a cyclic [7,4,1..3]1 code defined by generator polynomial over GF(2)
gap> HasSpecialDecoder(C);
true
gap> c := Random(C);
[ 0 1 1 0 0 0 1 ]
gap> i := InformationWord(C, c);
[ 0 1 1 1 ]
gap> e := ErrorVector(Random([1..WordLength(C)]), C);
[ 0 0 0 1 0 0 0 ]
gap> j := Decode(C,c+e);
[ 0 1 1 0 ]
gap> (i=j);
false
gap> w := Decodeword(C,c+e);
[ 0 1 1 1 0 1 0 ]
gap> (c=w);
false

and:

gap> c := Random(C);
[ 1 0 0 0 1 0 1 ]
gap> i := InformationWord(C, c);
[ 1 0 1 1 ]
gap> e := ErrorVector(Random([1..WordLength(C)]), C);
[ 0 0 0 0 1 0 0 ]
gap> j := Decode(C,c+e);
Error, List Element: <list>[1] must have an assigned value in
  return 0 \* cc[1]; at /builddir/build/BUILD/pkg/guava/lib/decoders.gi:307 called from 
func( C[i] ) at /usr/lib/gap/lib/coll.gi:746 called from
List( [ 1 .. n - r ], function ( k )
      return 0 \* cc[1];
  end ) at /builddir/build/BUILD/pkg/guava/lib/decoders.gi:307 called from
SpecialDecoder( C )( C, c 
 ) at /builddir/build/BUILD/pkg/guava/lib/decoders.gi:70 called from
<function "unknown">( <arguments> )
 called from read-eval loop at line 45 of _stdin_
you can 'return;' after assigning a value

Joyner's website changed

new URL: https://www.usna.edu/Users/math/wdj/

Set up Travis and CodeCov integration

Me or @fingolfin could hopefully help with that.

release tarball with auxiliary material

The tarball https://github.com/gap-packages/guava/releases contains auxiliary material in the doc and src/leon folders.

ReedSolomon decoding is broken

I run GAP 4.8.8 with Guava 3.14 on Fedora 28. The ReedSolomon decoding seems to be broken in at least two ways.

The decoder crashes with some inputs:

gap> C := ReedSolomonCode(10,5);
a cyclic [10,6,5]3..4 Reed-Solomon code over GF(11)
gap> r := Codeword([7,10,3,2,4,9,5,7,5,9], C);
[ 7 10 3 2 4 9 5 7 5 9 ]
gap> Decodeword(C, r);
Error, FFE operations: <divisor> must not be zero in
  return Value( rnew, a ^ (- i) ) / Value( pol, a ^ (- i) )
 ; at /usr/lib/gap/pkg/guava/lib/decoders.gi:380 called from
func( C[i] ) at /usr/lib/gap/lib/coll.gi:746 called from
List( ErrorLocator, function ( i )
      return Value( rnew, a ^ (- i) ) / Value( pol, a ^ (- i) );
  end ) at /usr/lib/gap/pkg/guava/lib/decoders.gi:380 called from
SpecialDecoder( C )( C, c
 ) at /usr/lib/gap/pkg/guava/lib/decoders.gi:146 called from
<function "unknown">( <arguments> )
 called from read-eval loop at line 28 of *stdin*
you can replace <divisor> via 'return <divisor>;'
brk>

The same also happens with eg.

r := Codeword([ 10 7 3 1 8 1 8 7 4 8 ], C);
r := Codeword([ 4 0 0 6 5 0 0 0 0 0 ], C);
r := Codeword([ 5 1 1 7 2 6 4 6 1 5 ] , C);

Additionally, the decoder fails silently with some inputs:

gap> C := ReedSolomonCode(10,4);
a cyclic [10,7,4]2..3 Reed-Solomon code over GF(11)
gap> r := Codeword([2,7,8,3,7,10,3,4,3,4], C);
[ 2 7 8 3 7 10 3 4 3 4 ]
gap> c := Decodeword(C, r);
[ 2 7 8 3 3 10 3 4 3 4 ]
gap> c in C;
false

The distance from r to a closest codeword is 2, so r might not be uniquely decodable. Thus this could be considered a feature. On the other hand, we have:

gap> C:=ReedSolomonCode(10,5);
a cyclic [10,6,5]3..4 Reed-Solomon code over GF(11)
gap> r := Codeword([3,7,5,5,1,10,3,9,2,8], C);
[ 3 7 5 5 1 10 3 9 2 8 ]
gap> Decodeword(C, r);
Error, not decodable called from
SpecialDecoder( C )( C, c ) at /usr/lib/gap/pkg/guava/lib/decoders.gi:146 called from
<function "unknown">( <arguments> )
 called from read-eval loop at line 17 of *stdin*
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk>

and hence it seems logical to consider the silent failure a bug.

I am aware that the special decoder used for ReedSolomon codes is the BCH decoder. So maybe it would be more appropriate to say that the BCH decoder is broken. I have, however, only used the decoder with ReedSolomon codes, so I'm choosing the more conservative title.