idigit.h

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

/* DigitVecAddCarry and DigitVecSubCarry removed, RD, 14.7.93 */
/* Integer Version 2.1, RD, 13.7.93	idigit.h	*/
/* Changed definition of DigitMult, added DigitMultAdd, RD, 13.7.93	*/
/* Integer Version 2.0, RD, 15.1.93	idigit.h	*/
/* DigitMultAdd and DigitMultSub removed, RD, 11.2.93 */

#ifndef _IDIGIT_H
#define _IDIGIT_H

#include <iint.h>

/* iint.h defines DigitType, BitsPerDigit and
	the c-varieties macros:
	EXTERN_FUNCTION, _VOID_, (const)
*/
/* Remark: In this version BitsPerDigit==sizeof(DigitType)*8,
	idigit*.c and shifts depend on this.			*/

/*******************************
	First the Digit-operations
*********************************/

EXTERN_FUNCTION( DigitType  DigitAdd, 
	( DigitType *sum, DigitType a, DigitType b, DigitType carry) )
        /* *sum=LOW-DIGIT(a+b+carry);
	   return HIGH-DIGIT(a+b+carry); 
	*/
EXTERN_FUNCTION( DigitType  DigitSub, 
	( DigitType *diff, DigitType a, DigitType b, DigitType carry) )
        /* *diff=RESULT;
	   return CARRY;
	   where RESULT, CARRY are defined by: 
	   2^BitsPerDigit > 
		CARRY*2^BitsPerDigit + a - b - carry == RESULT >= 0
	*/
EXTERN_FUNCTION( DigitType  DigitMult, 
	( DigitType *prod, DigitType a, DigitType b) )
        /* *prod=LOW-DIGIT(a*b);
	   return HIGH-DIGIT(a*b); 
	*/
EXTERN_FUNCTION( DigitType  DigitMultAdd, 
	( DigitType *prod, DigitType a, DigitType b, DigitType carry) )
        /* *prod=LOW-DIGIT(a*b+carry);
	   return HIGH-DIGIT(a*b+carry); 
	*/
EXTERN_FUNCTION( DigitType  DigitDiv, 
	( DigitType *quot, DigitType h, DigitType l, DigitType d) )
	/* Suppose:	d>0 and h<d
	   *quot=QUOT;
	   return REM;
	   where QUOT, REM are defined by: 
	   h*2^BitsPerDigit + l == d*QUOT + REM,
	   2^BitsPerDigit > REM >= 0
	*/

/*******************************
	Now the standard DigitVec operations 
*********************************/

EXTERN_FUNCTION( DigitType  DigitVecAdd, 
	( DigitType *sum, DigitType *a, DigitType *b, int l) )
     /*	sum[0..l-1] = a[0..l-1] + b[0..l-1]; return CARRY;   */
     /* This notation means:
	Add the integers represented by the vectors a and b,
	write the lowest l digits of the result into the vector sum
	and return the carry of this operation.
     */
EXTERN_FUNCTION( DigitType  DigitVecSub, 
	( DigitType *diff, DigitType *a, DigitType *b, int l) )
     /*	diff[0..l-1] = a[0..l-1] - b[0..l-1]; return CARRY;   */

EXTERN_FUNCTION( DigitType  DigitVecMult, 
	( DigitType *res, DigitType *a, DigitType m, int l) )
     /*	res[0..l-1] = a[0..l-1]*m; return CARRY;   */
EXTERN_FUNCTION( DigitType  DigitVecMultAdd, 
	( DigitType *res, DigitType *a, DigitType m, int l) )
     /*	res[0..l-1] += a[0..l-1]*m; return CARRY;   */
     /* Special function for multiple digit multiplication */
EXTERN_FUNCTION( DigitType  DigitVecMultSub, 
	( DigitType *res, DigitType *a, DigitType m, int l) )
     /*	res[0..l] -= a[0..l-1]*m; return CARRY;   */
     /* Special function for multiple digit division */
EXTERN_FUNCTION( DigitType  DigitVecDiv, 
	( DigitType *quot, DigitType *a, DigitType d, int l) )
     /*	quot[0..l-1] = a[0..l-1]/m; 
	return a[0..l-1]%m;
     */

/*******************************
	Now some special critical DigitVec operations
	(at least for the needs of Integer 2.0)
*********************************/

EXTERN_FUNCTION(void DigitVecCsubto, 
	(DigitType *a, DigitType *b, int l))
        /* a[]-=b[l]; */
EXTERN_FUNCTION(int DigitVecCadd, 
	(DigitType *sum, DigitType *a, DigitType *b, int la, int lb))
	/* sum[]=a[la]+b[lb]; return sum->length */
EXTERN_FUNCTION(int DigitVecCsub, 
	(DigitType *diff, DigitType *a, DigitType *b, int la, int lb))
	/* diff[]=a[la]-b[lb]; return diff->length */
EXTERN_FUNCTION(BOOLEAN DigitVecSr1, (DigitType *u, int l))
	/* b=u[l]%2; u[l]/=2; return b; */
EXTERN_FUNCTION(void DigitVecSri, (DigitType *u, int l, int i))
	/* b=u[l]%2^i; u[l]/=2^i; 	0<i<BitsPerDigit  */

/*******************************
	Some general non-critical DigitVec operations 
*********************************/

EXTERN_FUNCTION(BOOLEAN DigitVecEq, (DigitType *a, DigitType *b, int l))
        /* return a[l]==b[l]; */
EXTERN_FUNCTION(BOOLEAN DigitVecGt, (DigitType *a, DigitType *b, int l))
        /* return a[l]>b[l] lexikographisch */

/*******************************
	At the end an internal function for DigitVec multiplication
		via Karatsubas method
*********************************/

EXTERN_FUNCTION(void DigitVecKaratsubaM, 
	(DigitType *prod, DigitType *a, DigitType *b, DigitType *tmp, int n2))


#endif