lrsarith - Man Page
Name
lrsarith: library routines for exact precision integer and rational arithmetic from lrslib with sample programs. 64bit integer, 128bit integer, GMP, lrslib MP, and FLINT arithmetic packages are supported. as well as hybrid arithmetic. Overflow checking is done for 64bit and 128bit arithmetic.
Synopsis
lrslong.h lrslong.c [64bit and 128bit arithmetic]
lrsgmp.h lrsgmp.c [GMP and FLINT arithmetic] (requires external library)
lrsmp.h lrsmp.c [lrslib MP arithmetic]
Description
This package was extracted from version 7.1 of lrslib which uses hybrid arithmetic with overflow checking, starting in 64bit integers, moving to 128bit (if available) and then GMP. Overflow checking is conservative to improve performance: eg. with 64 bit arithmetic, a*b triggers overflow if either a or b is at least 2^31, and a+b triggers an overflow if either a or b is at least 2^62. Typically problems that can be solved in 64bits run 3-4 times faster than with GMP and inputs solvable in 128bits run twice as fast as GMP. A rational number is represented by a pair of integers, however the user must keep track of the numerator and denominators manually. Operations for rational arithmetic are included.
Various test programs are available and can be built from the makefile:
% make fixed
Build the programs fixed1, fixed1n, fixed2, fixed2n, fixedmp, fixedgmp that read an integer k and repeatedly square it 6 times.
% make hybrid (% make mp use internal MP arithmetic instead of GMP)
Build the program hybrid (and fixed1, fixed2, fixedgmp) that runs through the three arithmetic packages as needed.
% make coll (% make flint make FLINT arithmetic version)
Reverse search code for building a Collatz tree with largest value maxn in all arithmetic versions.
% make test
Test the arithmetic constants used in overflow checking.
Initialization
lrs_mp_init(digits,fpin,fpout);
digits: maximum number of decimal digits in MP arithmetic else set digits=0
fpin, fpout: input and output file pointers, eg, stdin, stdout
Types
Fixed arithmetic is handled by defining a generic integer type and a set of generic operations. A generic integer a, integer vector v and integer matrix A are defined
lrs_mp a; lrs_mp_vector v; lrs_mp_matrix A;
allocated
lrs_alloc_mp(a); v=lrs_alloc_mp_vector(n); A=lrs_alloc_mp_matrix(m,n);
and freed
lrs_clear_mp(a); lrs_clear_mp_vector(n); lrs_clear_mp_matrix(m,n);
where m and n are the dimensions.
Operations
Operations using lrs_mp integers are written generically. The most basic ones are below and a complete list is included in lrslong.h. Operations may be implemented as macros which may evaluate their arguments more than once. Arguments should not be expressions with potential side effects. Here, a,b,c,d,e are lrs_mp integers, i is a long long int and the equivalent C code is given in parenthesis.
addint(a,b,c) (c=a+b) /* a and b should be different */
changesign(a) (a = -a)
compare(a,b) (a ? b and returns -1,0,1 for <,=,>)
copy(a,b) (a=b)
decint(a,b) (a=a-b)
divint(a,b,c) (c=a/b a=a%b)
exactdivint(a,b,c) (c=a/b)
itomp(i,a); (a=i)
linint(a, ka, b, kb) (a=a*ka+b*kb for ka, kb long long integers)
mp_greater(a, b) (a>b)
mulint(a,b,c) (c=a*b) /* b and c may be the same */
negative(a) (a<0)
one(a) (a == 1)
pmp("string",a) (print "string" followed by a to lrs_ofp)
positive(a) (a>0)
qpiv(a,b,c,d,e) (a=(a*b-c*d)/e where the division is exact )
sign(a) (a < 0 ? NEG : POS)
storesign(a, i) (a = labs(a) * i)
subint(a,b,c) (c=a-b)
zero(a) (a == 0)
Notes
User's guide for lrslib
Author
David Avis <avis at cs dot mcgill dot ca >