MPINT(3) BSD Library Functions Manual MPINT(3)
NAME
libmpint - multiple-precision integer arithmetic
SYNOPSIS
#include <mpint.h>
mp_t *
mp_add(mp_t *r, mp_t *a);
mp_t *
mp_add_d(mp_t *r, mp_digit_t d);
mp_t *
mp_and(mp_t *r, mp_t *a);
mp_t *
mp_clear(mp_t * r);
int
mp_cmp(mp_t *a, mp_t *b);
mp_t *
mp_copy(mp_t *r, mp_t *a);
char *
mp_cvt(mp_t *r, int base);
mp_digit_t
mp_digitAt(mp_t *r, mp_size_t i);
mp_digit_t
mp_digitAtPut(mp_t *r, mp_size_t i, mp_digit_t _d);
mp_t *
mp_div(mp_t *quo, mp_t *rem, mp_t *dend, mp_t *ds_or);
mp_digit_t
mp_div_d(mp_t *quo, mp_digit_t d);
mp_t *
mp_mul(mp_t *r, mp_t *a);
mp_t *
mp_mul_d(mp_t *r, mp_digit_t d);
mp_t *
mp_neg(mp_t *r);
mp_t *
mp_normalise(mp_t *r);
mp_t *
mp_not(mp_t *r);
mp_t *
mp_or(mp_t *r, mp_t *a);
mp_t *
mp_shift(mp_t *r, int n);
mp_t *
mp_shiftl(mp_t *r, mp_size_t n);
mp_t *
mp_shiftr(mp_t *r, mp_size_t n);
mp_digit_t
mp_sub(mp_t *r, mp_t *a);
mp_digit_t
mp_sub_d(mp_t *r, mp_digit_t d);
mp_digit_t
mp_subf_d(mp_t *r, mp_digit_t d);
mp_t *
mp_xor(mp_t *r, mp_t *a);
int
mp_zerop(mp_t *a);
DESCRIPTION
The mpint library provides operations on multiple-precision integers.
Each MP integer is stored as a mp_t structure containing at least the
following fields:
typedef struct
{
mp_size_t width;
mp_digit_t *bits;
} mp_t;
These members can be statically initialised (to zero) using the value of
the MP_INITIALISER macro.
mp_t my_mp = MP_INITIALISER;
When no longer needed, any resources associated with a mp_t object should
be released using mp_clear():
mp_clear(&my_mp);
OPERATORS
All operators work on pointers to objects of type mp_t. Most operators
return their first argument (the first operand of the operation and the
object into which the result is stored). In the descriptions below, the
return value will only be mentioned explicitly in cases where it does not
conform to this convention.
Some operators take an integer of type mp_digit_t as argument. This
integer represents a single "digit" within a multi-precision integer.
Digits are nominally 32 bits wide, but arguments of type mp_digit_t
should never exceed 31 bits to avoid risk of overflowing the single bit
of carry internallyt propagated between digits by certain operations.
mp_t * mp_add(mp_t *r, mp_t *a)
Computes the sum of r and a and stores the result in r.
mp_t * mp_add_d(mp_t *r, mp_digit_t d)
Computes the sum of r and the single digit d and stores the
result in r.
mp_t * mp_and(mp_t *r, mp_t *a)
Computes the bitwise "and" of r and a and stores the result in r.
mp_t * mp_clear(mp_t * r)
Frees any resources associated with r and resets it to zero.
int mp_cmp(mp_t *a, mp_t *b)
Compares a and b and returns -1, 0 or 1 if a is less than, equal
to, or greater than b respectively.
mp_t * mp_copy(mp_t *r, mp_t *a)
Copies the value of a into r. (Subsequent modifications to one
will be independe of the other.) Returns a pointer to the ascii
representation of r in the given base. (The contents of the
storage pointed to will be overwritten on subsequent calls. This
function is not reentrant.)
mp_digit_t mp_digitAt(mp_t *r, mp_size_t i)
Returns digit at index i (numbered from zero) in r.
mp_digit_t mp_digitAtPut(mp_t *r, mp_size_t i, _mp_digit_t d)
Sets the digit at index i (numbered from zero) in r to d and
returns d.
mp_t * mp_div(mp_t *quo, mp_t *rem, mp_t *dend, mp_t *dsor)
Divides dend by dsor and stores the quotient in quo and the
remainder in rem. Returns quo. If dsor is zero then no division
occurs (nor is any error signalled).
mp_digit_t mp_div_d(mp_t *quo, mp_digit_t d)
Divides quo by the single digit d, stores the result in quo, and
returns quo. If d is zero then no division occurs (nor is any
error signalled).
mp_t * mp_mul(mp_t *r, mp_t *a)
Multiplies r by a and stores the result in r.
mp_t * mp_mul_d(mp_t *r, mp_digit_t d)
Multiples r by the single digit d and stores the result in r.
mp_t * mp_neg(mp_t *r)
Negates (takes the two's complement of) r and stores it back into
r. Removes leading zeros from r. (This operator should not nor-
mally be used. It is called implicitly by the other operators
whenever appropriate.)
mp_t * mp_not(mp_t *r)
Inverts (takes the ones's complement of) r and stores the it back
into r.
mp_t * mp_or(mp_t *r, mp_t *a)
Computes the bitwise inclusive "or" of r and a and stores it in
r.
mp_t * mp_shift(mp_t *r, int n)
Shifts r left by n bits and stores the result in r. (If n is
negative then r is shifted right by n bits.)
mp_t * mp_shiftl(mp_t *r, mp_size_t n)
Shifts r left by n bits. (This operator has no effect if n is
negative.)
mp_t * mp_shiftr(mp_t *r, mp_size_t n)
Shifts r right by n bits. (This operator has no effect if n is
negative.)
mp_digit_t mp_sub(mp_t *r, mp_t *a)
Subtracts a from r and stores the result in r. Returns the carry
("not borrow") bit generated from the operation; i.e., 1 if there
was no borrow out of the most significant digit in r, 0 if there
was a borrow.
(The carry is useful when implementing "sign+magnitude" multi-
precision arithmetic as a wrapper around unsigned multi-precision
integers. If carry is generated during subtraction then bit-
inverting the result and adding one will yield the correct magni-
tude; the "sign" of the result will be the opposite of that of
the left hand operand. Similar pre- and post-processing will be
required for all signed binary operands and results. See any
decent introductory CS textbook for details.)
mp_digit_t mp_sub_d(mp_t *r, mp_digit_t d)
Subtracts the single digit d from r and stores the result in r.
Answers the carry ("not borrow") generated from the subtraction.
mp_digit_t mp_subf_d(mp_t *r, mp_digit_t d)
Subtracts r from the single digit d and stores the result in r.
Answers the carry ("not borrow") generated from the subtraction.
mp_t * mp_xor(mp_t *r, mp_t *a)
Computes the bitwise exclusive "or" of r and a and stores the
result in r.
int mp_zerop(mp_t *a)
Returns 1 if a is zero, otherwise 0.
RETURN VALUES
Most operators return their first argument, which is both the left hand
operand and the location into which the result of the operation is
stored. Predicates and comparison operators return an integer represent-
ing the result of the test. Subtraction operators return the single
digit carry ("not borrow") out of the most significant digit.
EXAMPLES
The following program prints the factorials of the first 50 non-zero pos-
itive integers on the standard output.
#include <mpint.h>
#include <stdio.h>
int main()
{
int i;
mp_t mp = MP_INITIALISER;
mp_digitAtPut(&mp, 0, 1);
for (i= 1; i <= 50; ++i)
puts(mp_cvt(mp_mul_d(&mp, i), 10));
mp_clear(&mp);
return 0;
}
COMPATIBILITY
The interface is similar to those provided by some other multi-precision
integer libraries (most notably LibTomMath by Tom St Denis).
AUTHORS
The software and manual pages were written by Ian Piumarta.
The software is provided as-is, with absolutely no warranty, in the hope
that you will enjoy and benefit from it. You may use (entirely at your
own risk) and redistribute it under the terms of a very liberal license
that does not threaten your project with infection by a debilitating
infectious disease. See the file COPYING for details.
BUGS
No checks are made for out-of-memory errors, nor for ridiculously large
arguments that might cause requests for larger amounts of memory than the
system could reasonably be expected to provide.
Division by zero is detected and then silently ignored.
The interface of mp_div() is incongruent with the other operators: a lone
three-address operator adrift in a sea of two-address operators.
The library was written to support the conversion of floating point num-
bers to ascii. Only those operators needed for that purpose have been
tested more than superficially. The other operators were added for com-
pleteness and probably still contain bugs.
The header file should be called "mp_int.h" rather than "mpint.h".
Please send bug reports (or suggestions for improvements) to the author
at: firstName (at) lastName (dot) com. (See AUTHORS above for suitable
values of firstName and lastName.)
BSD December 17, 2009 BSD