Building GMP on Windows (MSYS)

I was recently trying to build the Prime95 Mersenne search software in Visual Studio 2022 when I got error messages about missing a gmp.h dependency.

1>C:\repos\gimps\p95v3019b13.source\common.h(23,10): error C1083: Cannot open include file: 'gmp.h': No such file or directory
...

This got me started trying to figure out how to build the GMP sources on Windows. It was easy to do in the MSYS MINGW64 shell. Use these steps:

cd /c/repos/gmp
curl -Lo gmp-6.3.0.tar.xz https://gmplib.org/download/gmp/gmp-6.3.0.tar.xz
unxz --keep gmp-6.3.0.tar.xz
tar xf gmp-6.3.0.tar
cd gmp-6.3.0
./configure
make

Background Investigation

Searching gmp.h not found windows – Google Search leads to makefile – How to install GMP Mp on windows? (C++) – Stack Overflow. Turns out I need the GNU MP Bignum Library (gmplib.org). The GMP developers’ corner (gmplib.org) points to the repo. It is a mercurial repo! Haven’t seen that in some time!

hg clone https://gmplib.org/repo/gmp/
hg clone https://gmplib.org/repo/gmp-6.3/

Such distractions aside, there is a link to download gmp-6.3.0.tar.xz:

cd /c/repos/gmp

curl -Lo gmp-6.3.0.tar.xz https://gmplib.org/download/gmp/gmp-6.3.0.tar.xz

file gmp-6.3.0.tar.xz

The file command outputs gmp-6.3.0.tar.xz: XZ compressed data, checksum CRC64. Thisrepresents XZ data compression, which is unfamiliar to me (haven’t run into this often). The unxz command can be used to decompress the file with the --keep option to avoid removing the source file.

unxz --keep gmp-6.3.0.tar.xz
tar xf gmp-6.3.0.tar

# Search for gmp.h
cd gmp-6.3.0
find . -name "gmp.h"

Ironically, xz is currently (as I write this post) making the rounds for having recently shipped a back door (All about the xz-utils backdoor | Kali Linux Blog) but I digress. There is no gmp.h file in the new gmp-6.3.0 directory though. The GNU MP Manual (gmplib.org) has a section with Notes for Particular Systems (GNU MP 6.3.0) (gmplib.org).

On an MS-DOS system DJGPP can be used to build GMP, and on an MS Windows system Cygwin, DJGPP and MINGW can be used. All three are excellent ports of GCC and the various GNU tools.

Notes for Particular Systems (GNU MP 6.3.0) (gmplib.org)

Let’s try in Cygwin. Looks like we just run configure then make.

cd /cygdrive/c/repos/gmp/gmp-6.3.0
./configure

Here is the final output from configure.

configure: summary of build options:

  Version:           GNU MP 6.3.0
  Host type:         x86_64-pc-cygwin
  ABI:               64
  Install prefix:    /usr/local
  Compiler:          gcc
  Static libraries:  yes
  Shared libraries:  no

The make command fails though:

Making all in mpn
make[2]: Entering directory '/cygdrive/c/repos/gmp/gmp-6.3.0/mpn'
/bin/sh ../libtool  --tag=CC   --mode=compile gcc -DHAVE_CONFIG_H -I. -I..  -D__GMP_WITHIN_GMP -I.. -DOPERATION_`echo fib_table | sed 's/_$//'`   -O2 -pedantic -fomit-frame-pointer -m64 -mtune=k8 -march=k8 -c -o fib_table.lo fib_table.c
libtool: compile:  gcc -DHAVE_CONFIG_H -I. -I.. -D__GMP_WITHIN_GMP -I.. -DOPERATION_fib_table -O2 -pedantic -fomit-frame-pointer -m64 -mtune=k8 -march=k8 -c fib_table.c -o fib_table.o
In file included from fib_table.c:4:
../gmp-impl.h:146:10: fatal error: ../gmp-mparam.h: Invalid argument
 #include "gmp-mparam.h"
          ^~~~~~~~~~~~~~
compilation terminated.
make[2]: *** [Makefile:492: fib_table.lo] Error 1
make[2]: Leaving directory '/cygdrive/c/repos/gmp/gmp-6.3.0/mpn'
make[1]: *** [Makefile:998: all-recursive] Error 1
make[1]: Leaving directory '/cygdrive/c/repos/gmp/gmp-6.3.0'
make: *** [Makefile:788: all] Error 2

This file exists in the repo! repo/gmp-6.3: 71011d1c130f mpn/x86_64/gmp-mparam.h (gmplib.org). It is linked to on disk.

saint@machine /cygdrive/c/repos/gmp/gmp-6.3.0
$ ls -l  gmp-mparam.h
lrwxrwxrwx 1 saint saint 26 Mar 26 17:14 gmp-mparam.h -> mpn/x86_64/k8/gmp-mparam.h

Search for “fatal error: ../gmp-mparam.h: Invalid argument“. Notice gmp.h in the ls output in this thread: I have a GMP problem. If this is the wrong forum I am sorry to post it here. (gmplib.org).

Trying building it in the MSYS MINGW64 Shell. The end of the ./configure output is shown below. The host type and install prefix are different from the Cygwin environment’s.

config.status: linking mpn/x86_64/k8/gmp-mparam.h to gmp-mparam.h
config.status: executing libtool commands
configure: summary of build options:

  Version:           GNU MP 6.3.0
  Host type:         x86_64-w64-mingw32
  ABI:               64
  Install prefix:    /mingw64
  Compiler:          gcc
  Static libraries:  yes
  Shared libraries:  no

The make command succeeds in the MSYS MINGW64 Shell, running for 4 minutes. I can ignore Cygwin for now. Let’s try the Tutorial on GMP (colorado.edu). Copy the example into a file called mpz_simple1.c then use the command from the tutorial to compile it. Interestingly, I don’t need the -I and -L arguments from the tutorial. The gmp library must already be installed.

cd /c/repos/scratchpad/apps/gmp/tutorial
gcc -o mpz_simple1 mpz_simple1.c -lgmp

To see how gmp.h and the libraries are found, run these commands:

saint@machine MINGW64 /mingw64
$ find . -name "*gmp*"
./bin/libgmp-10.dll
./bin/libgmpxx-4.dll
./include/gmp.h
./include/gmpxx.h
./include/isl/val_gmp.h
./lib/libgmp.a
./lib/libgmp.dll.a
./lib/libgmpxx.a
./lib/libgmpxx.dll.a
./lib/libigmpagnt.a
./lib/pkgconfig/gmp.pc
./lib/pkgconfig/gmpxx.pc
./share/info/gmp.info-1.gz
./share/info/gmp.info-2.gz
./share/info/gmp.info.gz

$ cygpath -w /mingw64
C:\dev\software\msys64\mingw64

Poking around in file explorer shows 2022-01-05 timestamps for gmp.h and libgmp.*. Looks like these were indeed installed with MSYS. How do I automatically output the timestamps for each result of find? bash – How to loop through file names returned by find? – Stack Overflow suggests this command:

find . -name "*gmp*" | while IFS= read -r file; do ls -l $file; done

How do I check the loaded modules to see what is running when I execute this command? windbg – List loaded modules using gdb – Stack Overflow reminds me that process explorer can do this on Windows.

At this point, all we have seen is how to build GMP in the MSYS MINGW64 shell. We have also verified that we can build a sample GMP program, the Tutorial on GMP (colorado.edu). The Cygwin and Visual Studio environments can be investigated another time.


Graph Isomorphism

The Graph Isomorphism problem currently has a deterministic quasi-polynomial time algorithm. This time bound is a breakthrough from the previously best known upper bound of exponential time (in the size of the graph). I started looking at Babai’s paper on [1512.03547] Graph Isomorphism in Quasipolynomial Time (arxiv.org). Many of the key concepts involve abstract algebra, e.g. automorphism groups. This video is a great refresher on automorphisms.

Graph Theory FAQs: 02. Graph Automorphisms

I found it helpful to dig a little bit deeper into automorphisms via Visual Group Theory, Lecture 4.6: Automorphisms – YouTube. This video uses Cayley graphs, which I haven’t studied before but is still a good overview of the automorphism groups.

Visual Group Theory, Lecture 4.6: Automorphisms

The “Graph Isomorphism in Quasipolynomial Time” paper is quite involved. I was pleasantly surprised to find a University of Chicago lecture by Babai on this result few months ago. I still came away short of understanding the proof after watching the video.

The foundations of this line of research comes partially from the paper showing that Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time. I started looking into this paper to try to understand the fundamentals in the simpler case where the degree of the graph is bounded. There are many algebraic concepts that I still need a refresher on to get an intuitive feel for this old paper. However, [2011.01366] Recent Advances on the Graph Isomorphism Problem (arxiv.org) gives a higher level view of what is happening and is therefore my key aide at this point in shedding some light on these graph isomorphism algorithms. It has, for example, pointed me to the color refinement algorithm. Details about this algorithm are available in this Color Refinement and its Applications paper.


Categories: Mathematics

Review of Limit Inferior and Superior

I’m reading through Venkatesan Guruswami’s thesis titled List Decoding of Error-Correcting Codes and the definition of infinite families of codes uses lim inf. These videos are a good reminder of how the superior and inferior limits are defined.

Real Analysis 11 | Limit Superior and Limit Inferior
Real Analysis 12 | Examples for Limit Superior and Limit Inferior

While we’re at it, why not review vector spaces since they are used in the definition of linear error correcting codes?


Categories: Learning, Mathematics

Introduction to Generating Functions

I have been curious about generating functions and how they can be used to calculate the number of partitions of an integer. Fortunately, there are many videos available on this topic, e.g. generating functions in discrete mathematics – YouTube. I found Kimberly Brehm‘s videos quite informative, she has an amazing mathematics channel!

Generating Functions: Introductory Examples

Here are the other videos from that chapter on generating functions:

  1. Generating Functions: Calculational Techniques – Fundamental Identity
  2. Generating Functions: Calculational Techniques – Finite Geometric Series
  3. Generating Functions: Calculational Techniques – Fundamental Identity
  4. Generating Functions – Full Practice Questions
  5. Partitions of Integers