MPI: Arbitrary Precision Integer Arithmetic
MPI: Arbitrary Precision Integer ArithmeticMPI is a simple ANSI C code library that performs arbitrary precision integer arithmetic functions. It is designed to be highly portable, is very easy to use, and is entirely free. It supports modular arithmetic, and the distribution includes code for probabilistic primality testing too, so you can use it for cryptographic purposes, if that's your interest.
The name "MPI" is short for "multiple precision integers". This is perhaps an unfortunate choice, since this acronym is also the name of a standard message-passing interface. (I learned this after I wrote the library). However, this is a sufficiently small project that I hope that minor name clash will not cause anyone much confusion.
The built-in integer types of most computer programming languages, such as C, are of a fixed and relatively small size. This restriction makes it difficult to work with very large numbers (such as you might encounter in public key cryptography, for example). Using MPI and other libraries like it, you can work with much larger numbers than would ordinarly be possible -- indeed, only processing time and available memory limit the use of arbitrary precision integers.
Of course, not every language needs to go through all this. Java and Perl both include arbitrary-precision integers in their standard library of extensions, and the Python language has them as a built-in type. The Gambit Scheme compiler and interpreter also support arbitrary precision integers, as does GNU bc. Nevertheless, if you are programming in C, and need to do computations with very large integers, this is the sort of code you need.
A gzipped tar file with the source code for the most recent release of the library can be downloaded here. The tar file includes documentation in text form for how to compile and use the library in your own programs, as well as a variety of example programs.
The library has been compiled and tested on a variety of platforms, including a plethora of Unix variants (including Linux on x86 and PowerPC, IRIX on MIPS, AIX on RS/6000 and POWER2, Digital Unix on Alpha), MacOS, and Windows 98. The current distribution and build scripts are obviously very Unix centered, but it should be quite simple to build the library on any of these systems, since, at its core, it is merely one single source file and one header file!
Detailed instructions can be found in the README file that accompanies the MPI distribution. However, here is a quick overview of how it works. You declare variables of type mp_int in your programs, and call functions in the MPI library to operate on them. Arbitrary precision integers require a bit more housekeeping than an ordinary int, but the general paradigm is pretty straightforward. Here is a very simple example:
#include <stdio.h>
#include <stdlib.h>
#include "mpi.h"
int main(int argc, char *argv[])
{
mp_int a, b;
char *buf;
int len;
/* Call mp_init() to initialize the mp_int structures */
mp_init(&a);
mp_init(&b);
/* mp_set() assigns a single-digit value to an mp_int */
mp_set(&a, 102);
/* mp_read_radix() reads in a string value in the given base */
mp_read_radix(&b, "4f923ac01ff0392155c2e98", 16);
/* Let's multiply these two together... */
mp_mul(&a, &b, &a);
/* Print it out in decimal notation */
len = mp_radix_size(&a, 10);
buf = calloc(len, sizeof(char));
mp_todecimal(&a, buf);
printf("result = %s\n", buf);
free(buf);
/* Call mp_clear() to clean up an mp_int you're done with */
mp_clear(&a); mp_clear(&b);
return 0;
}
As you can see, it's a bit more complex than using regular integers, but it's pretty simple once you get used to it. If you want, here are some some more examples.
You might be wondering why you would want to use this particular library, instead of one of the many others available. The principal virtues of MPI are that it is small, very portable, and entirely free. In particular, high performance was not one of the main design goals. I've made reasonable efforts to keep the performance as high as possible within the constraints of portability.
However, if you don't like it, I won't be offended; here are some alternatives you can try:
MPI was written by Michael J. Fromberger. He will be quite happy to answer e-mail queries about the library, as time permits.
Last modified