overview

Arithmetic for integers of almost unlimited size for C and C++. Developed and copyrighted by Ra

			LibI  Version 2.1
			=================

Arithmetic for integers of almost unlimited size for C and C++.
Developed and copyrighted by

	Ralf Dentzer
	IWR
	Universitaet Heidelberg
	Im Neuenheimer Feld 368

	D-6900 Heidelberg

	[e-mail]

(For further details see the file COPYRIGHT)

Latest Version:		2.0, February 1993
			2.1, July 1993

Usage:	
	C++:	A class Int is implemented that behaves
		very similar to int. It is an almost trivial task
		to substitute Int for int or long in an existing
		program. Use
		#include "Int.h"
		in your sources and link with libI.a.
		There has to be access to "iint.h".

	C:	A type Integer is implemented that has to
		be created before usage and destroyed afterwards,
		the operations are performed by function calls.
		Use
		#include "iint.h"
		in your sources and link with libI.a.

Operations available:
	Besides the utility functions and the basic functions
	as comparisons, additions, multiplications and divisions
	(with remainder) the greatest common divisor including
	the extended form can be calculated.

Memory management:
	This is based on malloc/free, but destroyed integers
	are not returned via free but kept in an internal list.
	This reduces the malloc/free overhead and makes
	creation/destruction rather efficient.

General form of C-funtions:
	The names for the available functions follow a few rules.
	1. The arguments are all pointers to Integers,
	   i.e. Integer*.
	2. A name "IasIplI(sum, a, b)" means:
		sum = a + b;
	   (attention: here we have Integer *sum, *a, *b;)
	   And "IplasI(sum, a)" means:
		sum += a;
	3. Here are the possible parts of the names:
		I		Integer
		int		int
		uint		unsigned int
		long		long
		ulong		unsigned long
		D		Digit
		c		create
		d		destroy
		nc		new and create
		dd		destroy and delete
		as		assign
		is		test
		pl		plus
		mi		minus
		neg		negate
		inc		increment
		dec		decrement
		eq		equal
		gt		greater than
		ne		not equal
		ge		greater or equal
		lt		less than
		mu		multiply
		di		divide
		re		remainder
		sr		shift right
		sl		shift left
		and             bitweise and
		or              bitweise inclusive or
		xor             bitweise exclusive or
		and             bitweise and
		not             bitweise not

	Most of the functions in the header file "iint.h"
	are directly understandable with these rules. The
	others are explained below.

Special functions:
    Creation and Destruction
	void cI (Integer *a);
		This is the simplest form of a creator for
		Integers. It creates some internal memory space for
		the digits of *a and initializes it to zero.
	void cIasint (Integer *a, int i);
		The Integer *a is created and initialized with i.
	void cIasI (Integer *a, Integer *b);
		The Integer *a is created and initialized with
		the Integer *b.
	void cImaxlength (Integer *a, int l);
		The Integer *a is created with the internal maxlength==l,
		*a is initialized to zero.
	void dI (Integer *a);
		The Integer *a is destroyed, i.e. the memory space
		occupied by *a will be used for further calculations.
	Integer *ncI ();
		This function returns a pointer to a variable of type
		Integer. That is initializes to zero.
	void ddI (Integer *a);
		The Integer *a that was created by a call to ncI
		has to be destroyed this way.
    Conversion to integral types
	BOOLEAN Iisint (const Integer *a);
		Test if the Integer *a fits into an int, if it returns true,
		the Integer *a can be savely converted to an int using
	int intasI (const Integer *a);
    Various arithmetic
	int Ilog, (const Integer *a);
		Calculate the greatest integer less or equal to	
		the 2's logarithm of the absolute value of *a.
		If Ieq0(a) then return -1.
	BOOLEAN Isr1 (Integer *a);
		Take the lowest bit of the Integer *a, shift *a right
		by 1 and return this lowest bit.
	BOOLEAN Ieven (const Integer *a);
		Test if *a is even.
	void Idiv (Integer *q, Integer *r, const Integer *a, const Integer *b);
		Division with remainder of a by b. Computes q and r
		such that   a==q*b+r and 0<=r<b.
	void uIdiv (Integer *q, Integer *r, const Integer *a, const Integer *b);
 		Same as Idiv but treat take the absolute value of a and b.
	void Idgcd (Integer *d, const Integer *a, const Integer *b);
		Compute the greatest common divisor d of a and b
		by a sequence of divisions with remainder.
	void Ibgcd (Integer *d, const Integer *a, const Integer *b);
		Compute the greatest common divisor d of a and b
		with a binary algorithm.
	#define Igcd	Ibgcd
		On most systems the fastest algorithm to compute
		the gcd is the binary one.
	void Idxgcd (Integer*d,Integer*u,Integer*v,
			const Integer*a,const Integer*b);
		Compute the greatest common divisor d of a and b
		and Integer *u,*v such that d==u*a+v*b,
		i.e. the extended gcd of a and b,
		by a sequence of divisions with remainder.
	#define Ixgcd	Idxgcd
		On most systems the fastest algorithm to compute
		the extended gcd is the one above.
	void Ibxgcd (Integer*d,Integer*u,Integer*v,
			const Integer*a,const Integer*b));
		Compute the greatest common divisor d of a and b
		and Integer *u,*v such that d==u*a+v*b,
		i.e. the extended gcd of a and b,
		with a binary algorithm.
	void Ireduce (Integer *a, Integer *b);
		Reduce the gcd of a and b,
		i.e. d=gcd(a,b); a=a/d; b=b/d;
	void IasrandomI (Integer * a, const Integer * b);
		Randomgenerator: choose random a with 0<=|a|<|b|, 
			a->sign=b->sign.
		a and b have to be distinct.
    Input and Output
	int Itoa (const Integer * n, char s[]);
	int atoI (char s[], Integer * n);
		Convert to and from a decimal string s[].
		Return the length of the string.
	int fscanI (FILE *f, Integer *a);
	int fprintI (FILE *f, const Integer *a);
		Input from and output to a FILE *f in decimal notation.
		Returns the number of char's read or written.
	char *wIdata1 (const Integer * a, int *l);
	char *wIdata2 (const Integer * a, int *l);
	char *rIdata1 (const Integer * a, int *l);
	char *rIdata2 (Integer * a, int *l);
		These are some functions for fast writing and
		reading or sending and receiving Integers. The result
		of these functions are pointers to memory blocks 
		consisting of l bytes, that have to be sent/received
		by appropriate funtions.
		The calling sequences are:
		- sender:	p=wIdata1(a, &l);
				send(channel, p, l);
					(or write(file, p, l); ...)
				p=wIdata2(a, &l);
				send(channel, p, l);
		- receiver:	p=rIdata1(a, &l);
				receive(channel, p, l);
				p=rIdata2(a, &l);
				receive(channel, p, l);

Organization of the implementation:

	The lowest level is formed by a set of functions that
	deal with single digits and the carry of their operations.
	(idigit.c)
	Next come some important functions that work with
	vectors of digits, most of the computing time is
	spent in these functions.
	(idigitvec.c)
	For the karatsuba multiplication there are sum further
	functions to deal efficiently with several vectors
	of digits.
	(idigitkara.c)
	These functions are grouped together and should not be
	accessed in normal usage.
	(idigit.h)

	The memory management is concentrated in
	(imem.c)
	with the interface
	(imem.h).

	For non-BSD Unix systems the files
	(random.c) (random.h)
	from University of California are included to generate
	random numbers. Based on these functions
	(irandom.c)
	is used to generate Integers with random values.

	For time measurements the functions from
	(timing.c) (timing.h)
	are used.

	The basic functions are implemented in
	(iadd.c) (ibit.c) (idiv.c) (igcd.c) (imul.c) (iutil.c).
	Input and output are mainly based on the other
	functions and available in
	(iio.c).

	All functions of interest to the user are declared in
	(iint.h).

	The C++ version based on the C version is implemented in 
	(bigint.C) (bigint.h) (original: (Int.cc) (Int.h)).
	
	For random tests of the main functions
	(itest.c) (Itest.cc)
	are provided, they also serve as examples for the usage.

	For comparisons in execution speed there is
	(itimes.c)
	that inputs a loop counter and two integers from stdin,
	performs the main operations, and prints out a
	statistic of the running times.

Installation:
	The provided Makefile can be customized easily,
	there are some defaults provided and some standard targets.
	In the normal case just try "make" to build libI.a
	and "make test" to perform tests with random integers for
	the correctness of the operations.
	The optimized versions for some architectures are made by
	the command "make <arch>" where <arch> is one of:
	sparc7, sparc8, mips (at the moment).



Acknowledgements

I would like to thank the following people for their contributions to
LibI:

Raphael Nauheim with whom I had many discussions about the design
	of the complete package.
Martin Schoenert who initiated the change from version 1 to version 2,
	which consisted of a major rearrangement that provided
	better portability and functionality.
	Based on his ideas I also made a further optimisation to
	the division routines, incorporated in version 2.1,
	and he also gave me many valuable hints for the assembler
	optimisation for the Mips processors.
Various other people who send me bug reports and made suggestions
	that arose from their usage of LibI.