1lrsarith(5)                      lrsarith 1.1                      lrsarith(5)
2
3
4
5   Name
6       lrsarith: library routines for exact precision integer and rational
7       arithmetic from lrslib with sample programs. 64bit integer, 128bit
8       integer, GMP, lrslib MP, and FLINT arithmetic packages are supported.
9       as well as hybrid arithmetic.  Overflow checking is done for 64bit and
10       128bit arithmetic.
11
12   Synopsis
13       lrslong.h lrslong.c [64bit and 128bit arithmetic]
14
15       lrsgmp.h lrsgmp.c [GMP and FLINT arithmetic]   (requires external
16                                                                                                                                                                                                                               library)
17
18       lrsmp.h lrsmp.c [lrslib MP arithmetic]
19
20   Description
21       This package was extracted from version 7.1 of lrslib which uses hybrid
22       arithmetic with overflow checking, starting in 64bit integers, moving
23       to 128bit (if available) and then GMP.  Overflow checking is
24       conservative to improve performance: eg. with 64 bit arithmetic, a*b
25       triggers overflow if either a or b is at least 2^31, and a+b triggers
26       an overflow if either a or b is at least 2^62.  Typically problems that
27       can be solved in 64bits run 3-4 times faster than with GMP and inputs
28       solvable in 128bits run twice as fast as GMP. A rational number is
29       represented by a pair of integers, however the user must keep track of
30       the numerator and denominators manually. Operations for rational
31       arithmetic are included.
32
33       Various test programs are available and can be built from the makefile:
34
35       % make fixed
36
37       Build the programs fixed1, fixed1n, fixed2, fixed2n, fixedmp, fixedgmp
38       that read an integer k and repeatedly square it 6 times.
39
40       % make hybrid    (% make mp   use internal MP arithmetic instead of
41       GMP)
42
43       Build the program hybrid (and fixed1, fixed2, fixedgmp) that runs
44       through the three arithmetic packages as needed.
45
46       % make coll          (% make flint   make FLINT arithmetic version)
47
48       Reverse search code for building a Collatz tree with largest value maxn
49       in all arithmetic versions.
50
51       % make test
52
53       Test the arithmetic constants used in overflow checking.
54
55   Initialization
56       lrs_mp_init(digits,fpin,fpout);
57
58       digits: maximum number of decimal digits in MP arithmetic else set
59       digits=0
60
61       fpin, fpout: input and output file pointers, eg,  stdin, stdout
62
63   Types
64       Fixed arithmetic is handled by defining a generic integer type and a
65       set of generic operations. A generic integer a, integer vector v and
66       integer matrix A are defined
67
68       lrs_mp a;     lrs_mp_vector v;    lrs_mp_matrix A;
69
70       allocated
71
72       lrs_alloc_mp(a);     v=lrs_alloc_mp_vector(n);
73       A=lrs_alloc_mp_matrix(m,n);
74
75       and freed
76
77       lrs_clear_mp(a);     lrs_clear_mp_vector(n);
78       lrs_clear_mp_matrix(m,n);
79
80       where m and n are the dimensions.
81
82   Operations
83       Operations using lrs_mp integers are written generically. The most
84       basic ones are below and a complete list is included in lrslong.h.
85       Operations may be implemented as macros which may evaluate their
86       arguments more than once.  Arguments should not be expressions with
87       potential side effects.  Here, a,b,c,d,e are lrs_mp integers, i is a
88       long long int and the equivalent C code is given in parenthesis.
89
90       addint(a,b,c)         (c=a+b)            /* a and b should be different
91       */
92
93       changesign(a)         (a = -a)
94
95       compare(a,b)          (a ? b and returns -1,0,1 for <,=,>)
96
97       copy(a,b)             (a=b)
98
99       decint(a,b)           (a=a-b)
100
101       divint(a,b,c)         (c=a/b a=a%b)
102
103       exactdivint(a,b,c)    (c=a/b)
104
105       itomp(i,a);           (a=i)
106
107       linint(a, ka, b, kb)  (a=a*ka+b*kb for ka, kb long long integers)
108
109       mp_greater(a, b)      (a>b)
110
111       mulint(a,b,c)         (c=a*b)              /* b and c may be the same
112       */
113
114       negative(a)           (a<0)
115
116       one(a)                (a == 1)
117
118       pmp("string",a)       (print "string" followed by a to lrs_ofp)
119
120       positive(a)           (a>0)
121
122       qpiv(a,b,c,d,e)       (a=(a*b-c*d)/e  where the division is exact )
123
124       sign(a)               (a < 0 ? NEG : POS)
125
126       storesign(a, i)        (a = labs(a) * i)
127
128       subint(a,b,c)         (c=a-b)
129
130       zero(a)               (a == 0)
131
132
133   Notes
134       User's guide for lrslib
135           http://cgm.cs.mcgill.ca/~avis/C/lrslib/USERGUIDE.html
136
137   Author
138       David Avis <avis at cs dot mcgill dot ca >
139
140   See also
141       lrslib(5),
142
143
144
145
146January 2022                       2022.1.19                       lrsarith(5)