gf2 focuses on efficient numerical work in bit-space, where mathematical entities such as vectors, matrices, and polynomial coefficients are limited to zeros and ones.It is available both as a C++ library and as a Rust crate with similar, though not identical, interfaces and features.
Even if you aren't involved in the mathematics of bit-space, you may find comparing the two implementations interesting.
Mathematicians refer to bit-space as GF(2)). It is the simplest Galois Field with just two elements, 0 and 1.
All arithmetic is modulo 2, so what starts in bit-space stays in bit-space. Addition/subtraction becomes the
XOR operation, and multiplication/division becomes the AND operation. gf2 uses those equivalences to efficiently perform most operations by simultaneously operating on entire blocks of bit elements at a time. We never have to worry about overflows or carries as we would with normal integer arithmetic. Moreover, these operations are highly optimised in modern CPUs, enabling fast computation even on large bit-matrices and bit-vectors.# Principal Classes & Types
The principal C++ classes and Rust types in the two versions of
gf2 are:|C++ Class|Rust Type|Description|
|:-|:-|:-|
|
BitArray|BitArray|A fixed-size vector of bits.||
BitVec|BitVec|A dynamically-sized vector of bits.||
BitSpan|BitSlice|A non-owning view into contiguous ranges of bits.||
BitPoly|BitPoly|A polynomial over GF(2).||
BitMat|BitMat|A dynamically-sized matrix of bits.|As you can see, there are is a name change to accommodate idioms in the languages; the C++
BitSpan class corresponds to the BitSlice type in Rust (C++ uses spans, Rust uses slices). There are other changes in the same vein elsewhere — C++ vectors have a size() method, Rust vectors have a len() method, and so on.The
BitArray, BitVec, and BitSpan/BitSlice classes and types share many methods. In C++, each satisfies the requirements of a BitStore concept. In Rust, they implement a BitStore trait. In either case, the BitStore core provides a rich common interface for manipulating collections of bits. Those functions include bit accessors, mutators, fills, queries, iterators, stringification methods, bit-wise operators on and between bit-stores, arithmetic operators, and more.There are other classes and types in
gf2 to support linear algebra operations, such as solving systems of linear equations, finding matrix inverses, and computing eigenvalues and eigenvectors. Among other things, the interface includes methods for examining the eigen-structure of large bit-matrices.The
BitPoly class provides methods to compute x^N mod p(x), where p(x) is a bit-polynomial and N is a potentially large integer.The classes and types are efficient and pack the individual bit elements into natural unsigned word blocks. There is a rich interface for setting up and manipulating instances, and for allowing them to interact with each other.
The C++ library has a comprehensive long-form documentation site, its code is available here.
The Rust crate is available on crates.io, its source code is available here, and there is documentation on docs.rs. The Rust documentation is complete but a little less comprehensive than the C++ version, mainly because
docs.rs does not support MathJax—a long-standing issue for scientific Rust.All the code is under a permissive MIT license.
The C++ version predates the Rust crate. We ported to Rust manually, as, at least for now, LLMs cannot handle this sort of translation task and produce anything that is at all readable or verifiable.
As you might expect with a rewrite, the new version considerably improved on the original. There were two beneficial
