purple-arithmetic

The purple-arithmetic library contains routines for arithmetic with integer coefficients.

This is an educational project with the purpose of learning and sharing algorithmic mathematics.

This library is defined in a C++26 module.

References:

• Donald E. Knuth, "The Art of Computer Programming", volume 2, "Seminumerical Algorithms", third edition, ISBN 0-201-89684-2

• MMIXmasters, "MIX to MMIX Conversion", https://mmix.cs.hm.edu/mmixmasters/index.html#MIXtoMMIX

• Alexander Stepanov, Paul McJones, "Elements of Programming", Addison-Wesley, 2009, ISBN 978-0-321-63537-2

• Alexander Stepanov, Daniel Rose, "From Mathematics to Generic Programming", Addison Wesley, 2015, ISBN 978-0-321-94204-3

• Niels Möller, Torbjörn Granlund, "Improved division by invariant integers"

Building the library requires these tools.

• clang 20+

• ninja 1.11+

• cmake 3.30+

To build the library:

cmake --preset default
cmake --build --preset default

To test the library:

cmake-build-default/purple-arithmetic-test

purple-arithmetic-test is a Google Test program containing unit tests for the library.

Fuzzying the library requires these tools.

• bc

To fuzz the square routine with an 8 degree "number" 1000 times:

cmake-build-default/purple-arithmetic-fuzz square 8 1000 | tee log | bc | cmake-build-default/purple-arithmetic-fuzz assert-zero

If successful, this pipeline prints nothing and returns 0. Else, it prints the index of the failed case, whose parameters can be found in the log file.

purple-arithmetic-fuzz square prints a program for bc whose expressions must always return 0. If any expression returns nonzero, that means bc disagrees with purple-arithmetic on the correct result.

purple-arithmetic-fuzz assert-zero consumes numbers from the standard input and tests for zero. If nonzero, it prints the index of this number and returns nonzero.

Available fuzzers:

• half degree iterations

• product degree iterations

• product-N-1 degree iterations

• ratio-2-1 iterations

• square degree iterations

• sum degree iterations

• twice degree iterations