This is the file BIGNUMS.TXT from ripem.msu.edu, last updated May 1994.
In response to Email requests, I have assembled this list of
large-integer arithmetic packages of which I have heard.
Most of these are C function libraries, available in source form.
A few also deal with floating point numbers.
For your convenience, I have placed copies of
some of these on ripem.msu.edu (35.8.1.178). They are
available for anonymous FTP in the directory "pub/bignum".
However, what I have may not be the most current version in all cases.
The files at my site are marked "Filename:". I also, in most
cases, include the original source.
Here they are, in no particular order:
mp
Multiple Precision package that comes with some Unixes
Multiple precision package accessed via -lmp flag on your
compiler. Provides +, -, *, /, gcd, exponentiation,
sqrt. Comes with SunOS, NeXT Mach, BBN Mach 1000,
and probably a few others. See "man 3 mp".
Object code only, of course.
PARI
Henri Cohen, et al., Universite Bordeaux I, Paris, FRANCE
Multiple precision desk calculator and library routines.
Contains optimized assembly code for Motorola 68020,
semi-optimized code for SPARC, and apparently rather slow
generic C version. Does both integers and reals.
Does vectors and matrices as well as scalars.
Contains a number of advanced functions, some of which I've
never heard of. ("Weber's function"?)
Has a factorization function, primality test, & other related stuff.
Plenty of TEX documentation.
Public domain, but you can't distribute modified versions.
Available via anonymous FTP from ftp.inria.fr:lang/ and
math.ucla.edu. The ucla site has Mac, MSDOS, OS/2, and
NeXT-specific versions there. See also megrez.ceremab.u-bordeaux.fr.
Filename: pari-1.38.3.tar.gz
Arithmetic in Global Fields (Arith)
Kevin R. Coombes, David R. Grant
Package of routines for arbitrary precision integers or
polynomials over finite fields. Includes basic +, -, *, /
and a few others like gcd. Source code in C.
Distributed under the terms of the GNU public license.
Includes man pages and TEX documentation.
Filename: arith.tar.Z
Arbitrary Precision Math Library
Lloyd Zusman Los Gatos, CA
C package which supports basic +, -, *, /. Provides for radix
points (i.e., non-integers). Not as polished as the others here.
Posted to comp.sources.misc in October 1988.
Filename: apml.tar.Z
Also available on oak.oakland.edu:SimTel/msdos/c/apm.zip
BigNum
J. Vuillemin, INRIA, FRANCE, and others.
Distributed by Digital Equipment Paris Research Lab (DECPRL)
A "portable and efficient arbitrary-precision integer" package.
C code, with generic C "kernel", plus assembly "kernels" for
MC680x0, Intel i960, MIPS, NS32032, Pyramid, and of course VAX.
This is probably one of the better-known packages of this type.
Implements +, -, *, /, mod, plus logical operations OR, AND, XOR.
Both signed and unsigned arithmetic available.
Formerly available via email from librarian@decprl.dec.com.
You will receive 5 shell archives. Give your postal address
and you will also receive printed documentation from France.
Package includes TEX documentation.
Publicly available for non-commercial use.
I removed this from my archive when I heard a rumor that PRL
doesn't like others to distribute it. However, BIGNUM *is*
distributed as part of ecpp (see below).
Lenstra's LIP package
Arjen Lenstra Bellcore
Portable unsigned integer package written entirely in C.
Includes +, -, *, /, exponentiation, mod, primality testing,
sqrt, random number generator, and a few others.
An earlier version of this package is the only of these packages
I have actually used. It works well and is very portable.
I haven't done any benchmarks against the others, but the code
looks clever & Lenstra is an accomplished number theorist.
LIP replaces lenstra-3.1.c. The package now includes encrypted
source code; to obtain the decryption key, you must send a
signed license agreement to Bellcore. See the documentation.
Filename: lenstra-LIP-package.tar This is a collection of
all the files in flash.bellcore.com:/pub/lenstra
bmp (Brent's Multiple Precision?)
R. P. Brent
1981 vintage FORTRAN code to do extended precision floating &
fixed point arithmetic. Includes most of the mathematical
functions you'd find in a FORTRAN run-time library.
This code is an ACM algorithm, number 524.
To obtain, send a mail message to netlib@ornl.gov
containing the line "send mp.f from bmp" or better yet, perhaps
just start with "help".
SPX
Kannan Alagappan & Joseph Tardo, DEC
This is a huge prototype public key authentication system
based on RSA. I mention it here because those who have heard
of SPX have probably correctly guessed that it contains a large
integer package and I want to inform you that the large integer
package it contains is indeed DEC's BigNum from France.
You can get a beta test copy of SPX from crl.dec.com (192.58.206.2).
Use it only for testing, as it "may" expire on a certain date.
(I don't know whether this has expired yet.)
amp (Antti's Multiple Precision?)
Antti Louko alo@kampi.hut.fi
Multiple precision integer package in C. Includes +, -, *, /, %,
pow, mod, 1/x mod y, random, sqrt, gcd. Available for non-commercial
use. The package includes "share-secret", a public key system based
on the Diffie-Hellman algorithm.
This is normally part of the well-known "des-dist.tar.Z",
but I have removed the DES part to avoid having to deal with
cryptographic export laws, and have named the result:
Filename: amp.tar.Z
It's possible that without the DES stuff, the package
is missing some necessary routines.
gennum
Per Bothner U of Wisconsin-Madison
C++ routines and classes to do generic arithmetic, both
integer and rational. Part of the "Q" programming system.
Distributed under the terms of the GNU public license.
Obtained from cygnus.com.
Filename: gennum.tar.Z
MIRACL
(Shamus Software, Dublin, Ireland)
Integer and fractional multiple precision package.
MIRACL is a portable C library. Full C/C++ source code included
(In-line assembly support for 80x86). Number theoretic primitives
needed to support PK Cryptography are supplied.
C++ classes for Multiprecision Integers, Modular arithmetic, and
Chinese Remainder Thereom. Implementation in C/C++ of all modern
methods of Integer Factorisation, viz Brent-pollard, p-1, p+1,
Elliptic Curve, MPQS. Includes TEX manual and some DOS .EXEs.
Not public domain, but free for academic and non-commercial use.
Obtained from ftp.compapp.dcu.ie.
Filename: /pub/crypt/other/miracl-3.23.zip and miracl.tar.Z (older)
precision
Dave Barrett barrettd@tigger.colorado.edu
Multiple precision integer package in C with +,-,*,/, sqrt, rand,
mod, pow, log. Simple vector support. Does dynamic allocation of memory.
Free as long as you don't sell it or any program that uses it.
Filename: precision.tar.Z
UBASIC
Prof. Yuji Kida, Rikkyo University, Nishi-Ikebukuro 3, Tokyo 171, Japan
kida@rkmath.rikkyo.ac.jp
Multiple-precision version of the BASIC programming language,
for MS-DOS. Includes floating point. Said (by Keith Briggs)
to be pretty fast. Object only, I think. ervin@morekypr.bitnet
says: "This is the best package that I know of for
fast arithmetic. Has a version optimized for 386 machines. Includes
routines to do MPQS, the fastest currently known general factoring
algorithm. An additional file is at both sites to allow MPQS to use
hard drives so that it can factor up to 80 digits. Many number
theoretical functions are included in UBASIC. It allows over 2500
digits of precision."
Available via anonymous FTP from shape.mps.ohio-state.edu,
or simtel20.army.mil, or wuarchive.wustl.edu.
calc_v22
Unknown
MS-DOS C-like language that allows "infinite" precision.
Nice intrinsic functions. ervin@morekypr.bitnet reports problems
when changing precision on the fly.
See simtel20 or wuarchive.
briggs_arith
Keith Briggs (kbriggs@maths.adelaide.edu.au)
Turbo Pascal 5 source for routines that do multiple-precision
+, -, *, /, sqrt, gcd, factoring, rand for integers; also includes
+, -, *, / and rand for rational numbers.
Filename: briggs_arith.pas
Institute fur Experimentelle Mathematik
Dr Gerhard Schneider (?)
Fast C multiple-precision subroutine library.
I don't know anything about it; sl25@ely.cl.cam.ac.uk says
to contact MAT420@DE0HRZ1A.BITNET for more info.
Postal Address:
Institute fur Experimentelle Mathematik
EllernStr 29
D4300 Essen-12 GERMANY
LongInt
Markus Mueller (mueller@komsys.tik.ethz.ch)
"Multi precision arithmetic written in MODULA-2, with the most time critical
parts written in Assembler. Includes basic arithmetics (+, -, *, /, %) as
well as arithmetics MODULO a number. An additional module provides a
collection of procedures for primality testing, gcd, multiplicative
inverse and more. The package is part of a Privacy Enhanced Mail (PEM)
package which includes a PEM mailer, RSA key generator and Certificate
generation tools."
Source is in Modula-2, C, and assembler for Sun 3. LongInt has
also been ported to MS-DOS under Logitech Modula-2 and Turbo
Assembler. Availability: free for university use (research and
education); otherwise, a source license is required. To obtain,
write or email to:
Markus Mueller
Bertastrasse 7
CH-8953 Dietikon
Switzerland
email: mueller@komsys.tik.ethz.ch
bignum-1.2
Henrik.Johansson@Nexus.Comm.SE
Bignum package written in portable C. Will in the future
conform to the Common Lisp functions that handles integers.
Currently includes +, -, *, /, exponentiation, "exptmod",
comparison, random numbers, and gcd.
Filename: bignum-1.2
ACM algorithm 567
D.W. LOZIER and J.M. SMITH
FORTRAN subroutines to do extended-precision floating point
and normalized Legendre polynomials.
ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 7,1 (MARCH, 1981)
Obtained from research.att.com:netlib/toms/567.Z
Filename: acm-algorithm-567-floating-point.fortran.Z
range
O. Aberth and M. J. Schaefer
C++ package to do extended-precision floating point arithmetic
with programmer-defined precision. Uses decimal representations
internally. Contains basic +, -, *, /, relational operators,
++, and a few functions like sin, cos, sqrt, log. Documentation
a trifle confusing.
Obtained from math.tamu.edu:pub/range/range.tar.Z
Filename: range.tar.Z
MFLOAT
Friedrich Kaufmann (fkauf@fstgds06.tu-graz.ac.at) &
Walter Mueller (walter@piassun1.joanneum.ac.at)
Fast high-precision floating-point library for the IBM PC.
Written in C and assembler and therefore faster than many
of the other packages here (but platform-specific).
Includes sin, exp, log, etc. Includes most source code,
Turbo Pascal unit source, and C++ headers. Included
version is limited to 77 digits; higher available from author.
Shareware; $25 US. Friedrich Kaufmann, Schuetzenhofgasse 22,
A-8010 Graz, AUSTRIA, EUROPE.
Obtained from oak.oakland.edu:/pub/msdos/math
Filename: mfloat20.zip
bsint
Author unknown.
Pre-alpha release of C++ big integer package.
Implements basic math operators, exponentiation, and modular
exponentiation. Very skimpy documentation.
See milton.u.washington.edu:/pub/user-supported/tzs/bsint.tar.Z
GNU Multiple Precision (GMP)
GNU (Free Software Foundation) multiple precision package.
I haven't looked at it yet. This is current as of April 1992,
but there may be a more recent version by the time you read
this. This package is very widely available on FTP sites.
Filename: gmp-1.3.2.tar.Z
libg++ - GNU's C++ class library
Free Software Foundation
Includes Integer and Rational classes. Integer provides
the usual C++ operators, plus exponentiation, gcd, lcm.
Limited functionality, but documentation is better than most.
Look for libg++-2.4.tar.gz on an FTP server near you.
Elliptic Curve Primality Proving
Francois Morain, France.
Large package to prove the primality of any prime.
Includes Inria's BIGNUM package.
Obtained from ftp.inria.fr (128.93.1.26).
Filename: ecpp.V3.4.1.tar.Z
PGP (Pretty Good Privacy)
Philip Zimmermann prz@sage.cgd.ucar.EDU
Crypto package that includes bignum routines in C.
Assembly implementations available for several processors;
said to be quite fast for numbers around 1000 bits in size.
The crypto package violates RSA patents, but the bignum routines
can be used without fear of legal repercussions.
Bell's Arbitrary Precision Calculator
David I. Bell, Australia (dbell@pdact.pd.necisa.oz.au)
Arbitrary-precision calculator with good online help, C-like
language, many builtin functions, support for integers,
rational numbers (they work like floating point), complex numbers,
matrices, strings, lists, files, "objects". Includes
gcd, primality testing, even trig functions. Recommended.
(Large package, though.) Obtained from comp.sources.unix.
Filename: calc-1.24.7.tar.Z
Calc for GNU Emacs
Dave Gillespie (daveg@synaptics.com)
Advanced calculator written in Emacs Lisp. Includes arbitrary
precision integers and floating point, bitwise operations,
log and trig functions, financial functions, number theoretic
functions including prime factorization, symbolic calculus,
and an interface to GNUPLOT.
Filename: calc-2.02a.tar.Z
MPFUN: A Multiple Precision Floating Point Computation Package
David H. Bailey (dbailey@nas.nasa.gov)
Package of Fortran subroutines to perform multiprecision
floating point arithmetic. Also includes a program that
can automatically convert ordinary Fortran-77 code into code
that calls the MPFUN routines.
Keith Briggs says: "It's a masterpiece, and the state of the art
as far as Fortran goes."
Documentation in TeX format. Unrestricted distribution
allowed at no cost.
Filenames: mpfun_fortran.tar.Z & mpfun_tex_papers.tar.Z
Farb
Joseph H. Allen (jhallen@world.std.com)
Small C library to do arbitrary-precision floating-point
arithmetic on ASCII decimal strings. Only the basic
operations are supported. From alt.sources.
Filename: farb.shar
MPQS
Mark S. Manasse (msm@src.dec.com) and Arjen Lenstra
C program to factor numbers on a distributed network of
heterogeneous machines. June 1993 version.
Filename: mpqs-distributed-factoring.shar
Q
Per Bothner (bothner@cygnus.com)
A very high-level programming language written in C++.
Where APL uses arrays to avoid explicit looping, Q uses
generalized sequences (finite or infinite, stored or
calculated on demand). Q has lexical scoping, and some
support for logical and constraint programming. Q can
be compiled (into C++), or interpreted interactively.
Q contains a C++ hierarchical set of classes for representing
numbers (including infinite-precision rationals), functional
closures, collections, files, symbols, and so on. Uses GMP.
There are also functions that implement Common Lisp and
Scheme functionality.
Obtained from ftp.cygnus.com:/pub/Q
Filenames: Q-0.86.tar.gz, Q-misc.tar.gz, Q.doc.tar.gz
CLISP
Bruno Haible (haible@ma2s2.mathematik.uni-karlsruhe.de) & Michael Stoll
A Common Lisp implementation (high-level programming language),
with fast routines for long integer and long float arithmetic
(including assembly language support for m68k, i386, mips, sparc, vax,
Karatsuba multiplication, multiple-precision transcendental functions
in the real and complex domain). Free software under GNU GPL.
FTP ma2s2.mathematik.uni-karlsruhe.de:/pub/lisp/clisp/.
GNU bc
Author: Philip A. Nelson (phil@cs.wwu.edu)
GNU bc is an interactive algebraic language with arbitrary precision.
GNU bc is almost the same as bc & dc in some Unixes.
Filename: bc-1.02.tar.z (for example, in GNU prep.ai.mit.edu:pub/gnu/)
Bibliography
Author: Norbert Juffa (juffa@ira.uka.de) (??)
About 40 books and 500 articles are referenced in the bibliography. Topics
covered include: Floating-point units, floatin-point SW packages, elementary
functions, function approximation, CORDIC, BCD arithmetic, multiple precision
arithmetic, FP summation, test of FP software and hardware, etc...
filename: fpbibl18.zip from garbo.uwasa.fi:/pc/doc-soft
bc & dc
bc is an interactive processor for an arbitrary precision arithmetic
language or just compiler/preprocessor for dc calculator with arbitrary
precision; they comes with some Unixes.
Built-in support in other languages
Various
Multiple precision arithmetic is available in a number of
programming languages, such as Lisp and ABC (cf. mcsun.eu.net).
Version 8 of the programming language Icon (Griswold's successor
to SNOBOL4 available from cs.arizona.edu) has large integers.
Perl (by Larry Wall, available from devvax.jpl.nasa.gov)
includes source, in Perl, for such a package, but it's probably
not suitable for serious use.
For some of these, source code may be available. This list is
long enough, so I'm not going to pursue it aggressively.
Thanks to Keith Briggs and several others who contributed to this list.
See also other sites, such as nic.funet.fi:pub/sci/math/multiplePrecision/.
Mark Riordan mrr@ripem.msu.edu