LRSARITH(5)

📦 version 7.3a, in fedora 43, fedora 44

👑 LRSARITH — the lrsarith 1.0 manual, bestie edition 👑

okay so. this is LRSARITH(5) from the lrsarith 1.0 era, and it's literally the math-girlie bible for exact precision arithmetic. sit down, grab a strawberry 🍓, we're doing this.

✨ NAME ✨

lrsarith — library routines for exact precision integer and rational arithmetic from lrslib, plus sample programs to play with.

The arithmetic packages it serves, no cap:

  • 64bit integer
  • 128bit integer
  • GMP
  • lrslib MP
  • FLINT

…as well as hybrid arithmetic 💅. And bestie, overflow checking is done for 64bit and 128bit arithmetic. periodt.

🌸 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]
heads up: the lrsgmp.h / lrsgmp.c pair requires an external library. it's giving "bring your own dependency" 🙈.

🦋 DESCRIPTION 🦋

This package was extracted from version 7.1 of lrslib, which uses hybrid arithmetic with overflow checking — it starts in 64bit integers, moves up to 128bit (if available), and then lands on GMP. iconic ladder-climbing behavior honestly 👑

Overflow checking is conservative to improve performance, which sounds backwards but trust the process. eg. with 64 bit arithmetic:

  • a*b triggers overflow if either a or b is at least 2^31
  • a+b triggers an overflow if either a or b is at least 2^62

The speed payoff is real, fr fr: 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. ate. 💅

Now the important vibe check: a rational number is represented by a pair of integers, however the user must keep track of the numerator and denominators manually 😭. the library is not holding your hand on that one. But good news — 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. square it SIX times. the way that it just keeps squaring 😌

% 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. multi-package main character energy ✨

% make coll          (% make flint   make FLINT arithmetic version)

Reverse search code for building a Collatz tree with largest value maxn in all arithmetic versions. (yes, that Collatz. 3n+1. the chaotic queen 🌈)

% make test

Test the arithmetic constants used in overflow checking. short, sweet, doing her job 💖

🎀 INTIALIZATION 🎀

(keeping the original spelling, iykyk — we respect the source material here)

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 like:

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. allocate then free, that's the whole cycle bestie, balance 🧚

🔥 OPERATIONS 🔥

Operations using lrs_mp integers are written generically. The most basic ones are below, and a complete list is included in lrslong.h.

warning, lowkey important: operations may be implemented as macros which may evaluate their arguments more than once. So arguments should not be expressions with potential side effects. no sneaky i++ in there, bestie, she will bite you 💀

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)
note how addint wants a and b different, but mulint is chill with b and c being the same. different rules for different girls, we don't question it 🌸

⭐ NOTES ⭐

User's guide for lrslib:

http://cgm.cs.mcgill.ca/~avis/C/lrslib/USERGUIDE.html

(the lore. the deep dive. go read it 🦋)

👑 AUTHOR 👑

David Avis <avis at cs dot mcgill dot ca >

🌈 SEE ALSO 🌈

and that's the whole page, bestie. 💖

okay final sign-off, this one's from December 2020, dated 2020.12.07 — vintage but still serving, and she's still the lrsarith icon. slay, drink water, and don't forget to track your own numerators and denominators manually 😭✨ 🎀🦋💅

📦 where this page comes from